Coded TeraSort

By Songze Li, Sucha Supittayapornpong, Mohammad Ali Maddah-Ali, Amir Salman Avestimehr. 2017

54 citations recorded by the source corpus.

We focus on sorting, which is the building block of many machine learning algorithms, and propose a novel distributed sorting algorithm, named CodedTeraSort, which substantially improves the execution time of the TeraSort benchmark in Hadoop MapReduce. The key idea of CodedTeraSort is to impose structured redundancy in data, in order to enable in-network coding opportunities that overcome the data shuffling bottleneck of TeraSort. We empirically evaluate the performance of CodedTeraSort algorithm on Amazon EC2 clusters, and demonstrate that it achieves 1.97× - 3.39× speedup, compared with TeraSort, for typical settings of interest.

Subfields: Computer Networks and Communications, Information Systems

How researchers see this paper

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

In Computer Networks and Communications

1. Amir Salman Avestimehr
2. Qian Yu
3. Mohammad Ali Maddah-Ali
4. Ramtin Pedarsani
5. Songze Li
6. Amirhossein Reisizadeh
7. Saurav Prakash
8. M. Soltanolkotabi

In Information Systems

1. Amir Salman Avestimehr
2. Songze Li
3. Mohammad Ali Maddah-Ali
4. Jinhyun So
5. Amirhossein Reisizadeh
6. Qian Yu
7. Ramtin Pedarsani
8. Saurav Prakash

Citations in the corpus

• Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy (2018, background): “, [33]–[36]), and secure and private computing (e.”
• A Fundamental Tradeoff Between Computation and Communication in Distributed Computing (2016, methodology): “Here we give high-lever descriptions of these operations, and we refer the interested readers to [3] for more detailed descriptions.”
• Coded computation over heterogeneous clusters (2017, background): “The first coding concept introduced in [6]–[8] enables an inverse-linear tradeoff between computation load and communication load in distributed computing.”
• Coded Computation Over Heterogeneous Clusters (2019, background): “The first coding concept introduced in [6]–[8] enables an inverse-linear tradeoff between computation load and communication load in distributed computing.”
• Near-Optimal Straggler Mitigation for Distributed Gradient Methods (2017, methodology): “This tradeoff was empirically demonstrated to provide significant speedup for distributed computing benchmarks like TeraSort [12].”