Name
Abstract | ||
|---|---|---|
Large-scale parallel programming environments and algorithms require efficient group-communication on computing systems with failing nodes. Existing reliable broadcast algorithms either cannot guarantee that all nodes are reached or are very expensive in terms of the number of messages and latency. This paper proposes Corrected-Gossip, a method that combines Monte Carlo style gossiping with a deterministic correction phase, to construct a Las Vegas style reliable broadcast that guarantees reaching all the nodes at low cost. We analyze the performance of this method both analytically and by simulations and show how it reduces the latency and network load compared to existing algorithms. Our method improves the latency by 20% and the network load by 53% compared to the fastest known algorithm on 4,096 nodes. We believe that the principle of corrected-gossip opens an avenue for many other reliable group communication operations. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/IPDPS.2017.36 | 2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS) |
Keywords | Field | DocType |
gossip algorithms,reliable broadcast | Broadcasting,Monte Carlo method,Algorithm design,Gossip algorithms,Latency (engineering),Computer science,Parallel computing,Communication in small groups,Gossip,Computer network,Computing systems,Distributed computing | Conference |
ISSN | ISBN | Citations |
1530-2075 | 978-1-5386-3915-3 | 2 |
PageRank | References | Authors |
0.36 | 16 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Torsten Hoefler | 1 | 2197 | 163.64 |
| Amnon Barak | 2 | 590 | 119.00 |
| Amnon Shiloh | 3 | 105 | 24.32 |
| Zvi Drezner | 4 | 1195 | 140.69 |