Fetching the paper…

Reading the bibliography…

Latency Analysis of Coded Computation Schemes over Wireless Networks · Around

2017

Latency Analysis of Coded Computation Schemes over Wireless Networks

Reisizadeh, Amirhossein, Pedarsani, Ramtin

Original
PDF
Post on X

Understand

Large-scale distributed computing systems face two major bottlenecks that limit their scalability: straggler delay caused by the variability of computation times at different worker nodes and communication bottlenecks caused by shuffling data across many nodes in the network.

Recently, it has been shown that codes can provide significant gains in overcoming these bottlenecks.
In particular, optimal coding schemes for minimizing latency in distributed computation of linear functions and mitigating the effect of stragglers was proposed for a wired network, where the workers can simultaneously transmit messages to a master node without interference.
In this paper, we focus on the problem of coded computation over a wireless master-worker setup with straggling workers, where only one worker can transmit the result of its local computation back to the master at a time.

Built on

L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE transactions on automatic control
1992
Earlier work this paper cites.
M. Zaharia, A. Konwinski, A. D. Joseph, R. H. Katz, and I. Stoica, “Improving mapreduce performance in heterogeneous environments.,” in OSDI
2008
Earlier work this paper cites.
D. Datla, X. Chen, T. Tsou, S. Raghunandan, S. S. Hasan, J. H. Reed, C. B. Dietrich, T. Bose, B. Fette, and J.-H. Kim, “Wireless distributed computing: a survey of research challenges,” IEEE Communications Magazine
2012
Earlier work this paper cites.
U. Drolia, R. Martins, J. Tan, A. Chheda, M. Sanghavi, R. Gandhi, and P. Narasimhan, “The case for mobile edge-clouds,” in Ubiquitous Intelligence and Computing, 2013 IEEE 10th International Conference on and 10th International Conference on Autonomic and Trusted Computing (UIC/ATC)
2013
Earlier work this paper cites.
G. Liang and U. C. Kozat, “TOFEC: achieving optimal throughput-delay trade-off of cloud storage using erasure codes,” in Proc. of IEEE Conference on Computer Communications (INFOCOM)
2014
Earlier work this paper cites.
S. Li, M. A. Maddah-ali, and S. Avestimehr, “Coded MapReduce.” Presented at the 53rd Annual Allerton conference on Communication, Control, and Computing, Monticello, IL, 2015
2015
Earlier work this paper cites.
K. Lee, M. Lam, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Speeding up distributed machine learning using codes,” in Information Theory (ISIT), 2016 IEEE International Symposium on
2016
Earlier work this paper cites.

Similar

S. Dutta, V. Cadambe, and P. Grover, “Short-dot: Computing large linear transforms distributedly using coded short dot products,” in Advances In Neural Information Processing Systems
2016
Cited alongside, same era.
K. Lee, R. Pedarsani, D. Papailiopoulos, and K. Ramchandran, “Coded computation for multicore setups,” in Information Theory (ISIT), 2017 IEEE International Symposium on
2016
Cited alongside, same era.
R. Tandon, Q. Lei, A. G. Dimakis, and N. Karampatziakis, “Gradient coding,” arXiv preprint arXiv:1612.03301
Original
2016
Cited alongside, same era.
S. Li, M. A. Maddah-Ali, Q. Yu, and A. S. Avestimehr, “A fundamental tradeoff between computation and communication in distributed computing,” arXiv preprint arXiv:1604.07086
Original
2016
Cited alongside, same era.
S. Li, M. A. Maddah-Ali, and A. S. Avestimehr, “A unified coding framework for distributed computing with straggling servers,” arXiv preprint arXiv:1609.01690

Then

A. Reisizadeh, S. Prakash, R. Pedarsani, and S. Avestimehr, “Coded computation over heterogeneous clusters,” in Information Theory (ISIT), 2017 IEEE International Symposium on
2017
Closest in time.
K. Lee, C. Suh, and K. Ramchandran, “High-dimensional coded matrix multiplication,” IEEE International Symposium on Information Theory (ISIT)
2017
Closest in time.
Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “Polynomial codes: an optimal design for high-dimensional coded matrix multiplication,” arXiv preprint arXiv:1705.10464
Original
2017
Closest in time.
S. Dutta, V. Cadambe, and P. Grover, “Coded convolution for parallel and distributed computing within a deadline,” arXiv preprint arXiv:1705.03875
Original
2017
Closest in time.
Y. Yang, P. Grover, and S. Kar, “Coding method for parallel iterative linear solver,” arXiv preprint arXiv:1706.00163

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

2016

Cited alongside, same era.

M. Attia and R. Tandon, “Information theoretic limits of data shuffling for distributed learning,” arXiv preprint arXiv:1609.05181

2016

Cited alongside, same era.

“Federated learning: Collaborative machine learning without centralized training data.” https://research.googleblog.com/2017/04/federated-learning-collaborative.html

2017

Cited alongside, same era.

2017

Closest in time.

S. Li, Q. Yu, M. A. Maddah-Ali, and A. S. Avestimehr, “A scalable framework for wireless distributed computing,” IEEE/ACM Transactions on Networking

2017

Closest in time.

L. Song and C. Fragouli, “A pliable index coding approach to data shuffling,” arXiv preprint arXiv:1701.05540

2017

Closest in time.