TY - GEN
T1 - On the complexity of asynchronous gossip
AU - Georgiou, Chryssis
AU - Gilbert, Seth
AU - Guerraoui, Rachid
AU - Kowalski, Dariusz R.
PY - 2008
Y1 - 2008
N2 - In this paper, we study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. In short, we show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. This latter fact implies that there exist message-efficient asynchronous (randomized) consensus protocols, in the context of an oblivious adversary. In more detail, we summarize our results as follows. If the adversary is adaptive, we show that a randomized asynchronous gossip algorithm cannot terminate in fewer than O(f{d + δ)) time steps unless Ω(n + f2) messages are exchanged, where n is the total number of processes, f is the number of tolerated crash failures, d is the maximum communication delay for the specific execution in question, and δ is the bound on relative process speeds in the specific execution. The lower bound result is to be contrasted with deterministic synchronous gossip algorithms that, even against an adaptive adversary, require only O(polylog(n)) time steps and O(n polylog(n)) messages. In the case of an oblivious adversary, we present three different randomized, asynchronous algorithms that provide different trade-offs between time complexity and message complexity. The first algorithm is based on the epidemic paradigm, and completes in O(n/n-f log2 n(d + δ)) time steps using O(n log3 n(d+δ)) messages, with high probability. The second algorithm relies on more rapid dissemination of the rumors, yielding a constant-time (w.r.t. n) gossip protocol: for every constant ε < 1, and for f ≤ n/2, there is a variant with time complexity O(1/ε(d +δ)) and message complexity
AB - In this paper, we study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. In short, we show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. This latter fact implies that there exist message-efficient asynchronous (randomized) consensus protocols, in the context of an oblivious adversary. In more detail, we summarize our results as follows. If the adversary is adaptive, we show that a randomized asynchronous gossip algorithm cannot terminate in fewer than O(f{d + δ)) time steps unless Ω(n + f2) messages are exchanged, where n is the total number of processes, f is the number of tolerated crash failures, d is the maximum communication delay for the specific execution in question, and δ is the bound on relative process speeds in the specific execution. The lower bound result is to be contrasted with deterministic synchronous gossip algorithms that, even against an adaptive adversary, require only O(polylog(n)) time steps and O(n polylog(n)) messages. In the case of an oblivious adversary, we present three different randomized, asynchronous algorithms that provide different trade-offs between time complexity and message complexity. The first algorithm is based on the epidemic paradigm, and completes in O(n/n-f log2 n(d + δ)) time steps using O(n log3 n(d+δ)) messages, with high probability. The second algorithm relies on more rapid dissemination of the rumors, yielding a constant-time (w.r.t. n) gossip protocol: for every constant ε < 1, and for f ≤ n/2, there is a variant with time complexity O(1/ε(d +δ)) and message complexity
KW - Adaptive versus oblivious adversary
KW - Asynchrony
KW - Complexity
KW - Consensus
KW - Epidemic
KW - Gossip
KW - Randomization
UR - http://www.scopus.com/inward/record.url?scp=57549085187&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=57549085187&partnerID=8YFLogxK
U2 - 10.1145/1400751.1400771
DO - 10.1145/1400751.1400771
M3 - Conference contribution
AN - SCOPUS:57549085187
SN - 9781595939890
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 135
EP - 144
BT - PODC'08
PB - Association for Computing Machinery (ACM)
T2 - 27th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
Y2 - 18 August 2008 through 21 August 2008
ER -