Solving the Straggler Problem with Bounded Staleness

By James Cipar, Qirong Ho, Jin Kyu Kim, Seunghak Lee, G. R. Ganger, Garth A. Gibson, K. Keeton, Eric P. Xing. 2013

149 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Eric P. Xing
2. Aaron Harlap
3. Henggang Cui
4. Wei Dai
5. Martín Abadi
6. Qirong Ho
7. G. R. Ganger
8. Aurick Qiao

Citations in the corpus

• Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD (2018, neutral): “Asynchronous variants of existing SGD algorithms have also been proposed and implemented in systems [Cipar et al., 2013, Dean et al., 2012, Gupta et al., 2016].”
• More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server (2013, background): “[8] gives an informal definition of the SSP model, motivated by the need to reduce straggler effects in large compute clusters.”
• Naiad: a timely dataflow system (2013, background): “Notifications with tg < tc can also be useful to constrain otherwise asynchronous execution, for example by providing “bounded staleness” [11], which guarantees that the system does not proceed more than a defined number of iterations beyond any incomplete iteration.”
• Fault Tolerance in Iterative-Convergent Machine Learning (2018, methodology): “…a cluster resource allocator (Vavilapalli et al., 2013; Hindman et al., 2011), parameter synchronization can be bottlenecked on a slow or congested network (Li et al., 2014b; Zhang et al., 2017b), and stragglers can severely impact overall job throughput (Cipar et al., 2013; Harlap et al., 2016).”
• CPR: Understanding and Improving Failure Tolerant Training for Deep Learning Recommendation with Partial Recovery (2020, unknown): “Several distributed training systems implement checkpointing (Chilimbi et al., 2014; Narayanan et al., 2019; Cipar et al., 2013).”
• Exploiting Bounded Staleness to Speed Up Big Data Analytics (2014, methodology): “The client library also maintains a hierarchy of caches and operation logs in order to reduce network traffic.”
• Efficient and Robust Parallel DNN Training through Model Parallelism on Multi-GPU Platform (2018, background): “A variant of data parallelism is called asynchronous data parallelism [11, 12, 13, 15, 16].”
• Exploiting iterative-ness for parallel ML computations (2014, methodology): “…in this paper focus on the traditional BSP execution model, the same optimizations apply to the more flexible Stale Synchronous Parallel (SSP) [13, 24] model supported by LazyTable, and we observe approximately the same relative improvements; that is, the benefits of exploiting iterative-ness…”
• High-Performance Distributed ML at Scale through Parameter Server Consistency Models (2014, background): “One of the primary challenges in data parallelism is designing software systems to share the ML model across a cluster of commodity machines, in a manner that is theoretically well-justified, empirically highperformance, and easy-to-program all at the same time — and a highly promising solution is t”
• Addressing the straggler problem for iterative convergent parallel ML (2016, methodology): “FlexRR uses flexible consistency bounds, which has been recently proposed and studied under two different names: “Stale Synchronous Parallel” (SSP) [13, 31] and “Bounded Delay consistency” [35].”