Abstract
We consider the problem of gossiping when dynamic node crashes are controlled by adaptive adversaries. We develop gossiping algorithms which are efficient with respect to both the time and communication measured as the number of point-to-point messages. If the adversary is allowed to fail up to t nodes, among the total of n, where additionally n-t = Ω(n/polylog n), then one among our algorithms completes gossiping in time O(log2 t) and with O(n polylog t) messages. We prove a lower bound which states that the time has to be at least Ω(log(n log n)-log t/log n) if the communication is restricted to be O(n polylog n). We also show that one can solve efficiently a more demanding consensus problem with crash failures by resorting to one of our gossiping algorithms. If the adversary is allowed to fail t nodes, where n - t = Ω(n/polylog n), we obtain a time-optimal solution that is away from the communication optimality by at most a polylogarithmic factor.
Original language | English (US) |
---|---|
Pages | 220-229 |
Number of pages | 10 |
DOIs | |
State | Published - 2002 |
Externally published | Yes |
Event | Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures - Winnipeg, MAN., Canada Duration: Aug 10 2002 → Aug 13 2002 |
Conference
Conference | Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures |
---|---|
Country/Territory | Canada |
City | Winnipeg, MAN. |
Period | 8/10/02 → 8/13/02 |
Keywords
- Adaptive adversary
- Consensus
- Distributed algorithm
- Gossiping
- Lower bound
- Processor failures
ASJC Scopus subject areas
- Software
- Safety, Risk, Reliability and Quality