Tighter Worst-Case Bounds on Algebraic Gossip

• Published in: IEEE communications letters 2012-08, Vol.16 (8), p.1274-1276
• Main Author: Haeupler, Bernhard
• Format: Article
• Language: English
• Subjects: Applied sciences; Coding, codes; Encoding; Exact sciences and technology; Information, signal and communications theory; Network coding; Network topology; Protocols; Round robin; Routing; Signal and communications theory; Systems, networks and services of telecommunications; Telecommunications; Telecommunications and information theory; Teletraffic; Transmission and modulation (techniques and equipments); Vectors
• ISSN: 1089-7798; 1558-2558
• DOI: 10.1109/LCOMM.2012.060112.120632

Gossip and in particular network coded algebraic gossip have recently attracted attention as a fast, bandwidth-efficient, reliable and distributed way to broadcast or multicast multiple messages. While the algorithms are simple, involved queuing approaches are used to study their performance. The most recent result in this direction shows that uniform algebraic gossip disseminates k messages in O(Δ(D + k + log n)) rounds where D is the diameter, n the size of the network and Δ the maximum degree. In this paper we give a simpler, short and self-contained proof for this worst-case guarantee. Our approach also allows to reduce the quadratic Δ D term to min{3n, Δ D}. We furthermore show that a simple round robin routing scheme also achieves min{3n, Δ D} + Δ k rounds, eliminating both randomization and coding. Lastly, we combine a recent non-uniform gossip algorithm with a simple routing scheme to get a O(D + k + log^{O(1)}) gossip information dissemination algorithm. This is order optimal as long as D and k are not both polylogarithmically small.