Efficient task replication for fast response times in parallel computation

ABSTRACT

Large-scale distributed computing systems divide a job into many independent tasks and run them in parallel on different machines. A challenge in such parallel computing is that the time taken by a machine to execute a task is inherently variable, and thus the slowest machine becomes the bottleneck in the completion of the job. One way to combat the variability in machine response is to replicate tasks on multiple machines and waiting for the machine that finishes first. While task replication reduces response time, it generally increases resource usage. In this work, we propose a theoretical framework to analyze the trade-off between response time and resource usage. Given an execution time distribution for machines, our analysis gives insights on when and why replication helps. We also propose efficient scheduling algorithms for large-scale distributed computing systems.

References

1. Ananthanarayanan, G., Ghodsi, A., Shenker, S., and Stoica, I. Effective straggler mitigation: Attack of the clones. NSDI'13, USENIX, pp. 185--198.
2. Ananthanarayanan, G., Kandula, S., Greenberg, A., Stoica, I., Lu, Y., Saha, B., and Harris, E. Reining in the outliers in map-reduce clusters using mantri. OSDI'10, USENIX, pp. 1--16.
3. Cirne, W., Brasileiro, F., Paranhos, D., Luís Fabrício W. Góes, and Voorsluys, W. On the efficacy, efficiency and emergent behavior of task replication in large distributed systems. Parallel Computing 33, 3 (2007), 213--234.
4. Dean, J., and Barroso, L. A. The tail at scale. Commun. ACM 56, 2 (2013), 74--80.
5. Dean, J., and Ghemawat, S. MapReduce: simplified data processing on large clusters. Commun. ACM 51, 1 (2008), 107--113.
6. Ghare, G. D., and Leutenegger, S. T. Improving speedup and response times by replicating parallel programs on a SNOW. In Job Scheduling Strategies for Parallel Processing. Springer Berlin Heidelberg, Jan. 2005, pp. 264--287.
7. Joshi, G., Liu, Y., and Soljanin, E. Coding for fast content download. In Proc. Annu. Allerton Conf. on Commu. Control. & Comput. (Oct. 2012), pp. 326--333.
8. Joshi, G., Liu, Y., and Soljanin, E. On the Delay-Storage trade-off in content download from coded distributed storage systems. arXiv:1305.3945 {cs, math} (May 2013).
9. Shah, N. B., Lee, K., and Ramachandran, K. When do redundant requests reduce latency? arXiv:1311.2851 {cs} (Nov. 2013).
10. Vulimiri, A., Godfrey, P. B., Mittal, R., Sherry, J., Ratnasamy, S., and Shenker, S. Low latency via redundancy. arXiv:1306.3707 {cs} (June 2013).
11. Wang, D., Joshi, G., and Wornell, G. Efficient job replication for fast response times in parallel computation. arXiv:1404.1328 {cs.DC} (Apr. 2014).
12. Zaharia, M., Konwinski, A., Joseph, A. D., Katz, R., and Stoica, I. Improving MapReduce performance in heterogeneous environments. OSDI'08, USENIX, pp. 29--42.

Index Terms

• Computer systems organization

  • Dependable and fault-tolerant systems and networks

    • Availability

    • Maintainability and maintenance

    • Reliability

• General and reference

  • Cross-computing tools and techniques

    • Reliability

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making