Corrected Gossip Algorithms for Fast Reliable Broadcast on Unreliable Systems
| Autor: | Torsten Hoefler, Amnon Barak, Amnon Shiloh, Zvi Drezner |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Las vegas
Computer science Gossip algorithms business.industry Distributed computing 02 engineering and technology Gossip 020204 information systems Communication in small groups 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Algorithm design business Computer network |
| Zdroj: | IPDPS |
| DOI: | 10.1109/ipdps.2017.36 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|