On the complexity of asynchronous gossip

ABSTRACT

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 + delta)) time steps unless Omega(n+f²) 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 delta 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) log² n (d + δ)) time steps using O(n log³ 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 epsilon < 1, and for f ≤ n/2, there is a variant with time complexity O((1 / ε)(d+δ)) and message complexity O((1/ε)n^1+εlog n (d+δ)). The third algorithm solves a weaker version of the gossip problem in which each process receives at least a majority of the rumors. This algorithm achieves constant O(d+δ) time complexity and message complexity O(n^7/4 log² n).

As an application of these message-efficient gossip protocols, we present three randomized consensus protocols. Our consensus algorithms derive from combining each of our gossip protocols with the Canetti-Rabin framework, resulting in message-efficient consensus algorithms. The resulting protocols have time and message-complexity asymptotically equal to our gossip protocols. We particularly highlight the third consensus protocol, a result that is interesting in its own right: the first asynchronous randomized consensus algorithm with strictly subquadradic message-complexity, i.e., O(n^7/4 log² n).

REFERENCES

• 1: James Aspnes, Randomized protocols for asynchronous consensus, Distributed Computing, v.16 n.2-3, p.165-175, September 2003 [doi>10.1007/s00446-002-0081-5]
• 2: Hagit Attiya , Jennifer Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics, John Wiley & Sons, 2004
• 3: Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
• 4: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 5: Stephen Boyd , Arpita Ghosh , Balaji Prabhakar , Devavrat Shah, Randomized gossip algorithms, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2508-2530, June 2006 [doi>10.1109/TIT.2006.874516]
• 6: Ran Canetti , Tal Rabin, Fast asynchronous Byzantine agreement with optimal resilience, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.42-51, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167105]
• 7: Bogdan S. Chlebus , Leszek Gasieniec , Dariusz R. Kowalski , Alexander A. Shvartsman, Bounding Work and Communication in Robust Cooperative Computation, Proceedings of the 16th International Conference on Distributed Computing, p.295-310, October 28-30, 2002
• 8: Bogdan S. Chlebus , Dariusz R. Kowalski, Robust gossiping with an application to consensus, Journal of Computer and System Sciences, v.72 n.8, p.1262-1281, December, 2006 [doi>10.1016/j.jcss.2006.08.001]
• 9: B.S. Chlebus and D.R. Kowalski, Time and communication efficient consensus for crash failures, in Proc. of 20th International Symposium on Distributed Computing (DISC), 2006, pp. 314--328.
• 10: B. Chor and C. Dwork, Randomization in Byzantine agreement, Advances in Computing Research 5: Randomness and Computation, (1989) pp. 443--497.
• 11: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 12: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 13: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 14: P. Th. Eugster , R. Guerraoui , S. B. Handurukande , P. Kouznetsov , A.-M. Kermarrec, Lightweight probabilistic broadcast, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.341-374, November 2003 [doi>10.1145/945506.945507]
• 15: C. Georgiou, S. Gilbert, R. Guerraoui, and D.R. Kowalski, On the complexity of asynchronous gossip, Technical Report, 2008.
• 16: Chryssis Georgiou , Dariusz R. Kowalski , Alexander A. Shvartsman, Efficient gossip and robust distributed computation, Theoretical Computer Science, v.347 n.1-2, p.130-166, 30 November 2005 [doi>10.1016/j.tcs.2005.05.019]
• 17: Indranil Gupta , Anne-Marie Kermarrec , Ayalvadi J. Ganesh, Efficient Epidemic-Style Protocols for Reliable and Scalable Multicast, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), p.180, October 13-16, 2002
• 18: J. Hromkovic , R. Klasing , A. Pelc , P. Ruzicka , W. Unger, Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 19: R. Karp , C. Schindelhauer , S. Shenker , B. Vocking, Randomized rumor spreading, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.565, November 12-14, 2000
• 20: David Kempe , Jon Kleinberg , Alan Demers, Spatial gossip and resource location protocols, Journal of the ACM (JACM), v.51 n.6, p.943-967, November 2004 [doi>10.1145/1039488.1039491]
• 21: Anne-Marie Kermarrec , Laurent Massoulié , Ayalvadi J. Ganesh, Probabilistic Reliable Dissemination in Large-Scale Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.248-258, March 2003 [doi>10.1109/TPDS.2003.1189583]
• 22: J. Luo, P. Eugster, and J.P. Hubaux, Route driven gossip: Probabilistic reliable multicast in ad hoc networks, in Proc. of 21st IEEE Conference on Computer Communications (INFOCOM), 2003.
• 23: M. Mitzenmacher and E. Upfal, 'Probability and Computing, Cambridge University Press, 2005.
• 24: A. Pelc, Fault-tolerant broadcasting and gossiping in communication networks, Networks, 28 (1996) 143--156.
• 25: R. van Renesse, Y. Minsky, and M. Hayden, A gossip-style failure detection service, in Proc. of IFIP Int-l Conference on Distributed Systems Platforms and Open Distributed Processing, 1998, pp. 55--70.
• 26: Satish Verma , Wei Tsang Ooi, Controlling Gossip Protocol Infection Pattern Using Adaptive Fanout, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, p.665-674, June 06-10, 2005 [doi>10.1109/ICDCS.2005.20]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory

Keywords:
adaptive versus oblivious adversary, asynchrony, complexity, consensus, epidemic, gossip, randomization