Optimal Gossip with Direct Addressing

Bernhard Haeupler and Dahlia Malkhi

July 2014

Gossip algorithms spread information in distributed networks by having nodes repeatedly forward information to a few random contacts. By their very nature, gossip algorithms tend to be **distributed** and **fault tolerant**. If done right, they can also be **fast** and **message-efficient**. A common model for gossip communication is the random phone call model, in which in each synchronous round each node can PUSH or PULL information to or from a random other node. For example, Karp et al. [FOCS 2000] gave algorithms in this model that spread a message to all nodes in *Θ(log n)* rounds while sending only *O(log log n)* messages per node on average. They also showed that at least *Θ(log n)* rounds are necessary in this model and that algorithms achieving this round-complexity need to send *ω(1)* messages per node on average.

Recently, Avin and Elsässer [DISC 2013], studied the random phone call model with the natural and commonly used assumption of **direct addressing**. Direct addressing allows nodes to directly contact nodes whose ID (e.g., IP address) was learned before. They show that in this setting, one can “break the *log n* barrier” and achieve a gossip algorithm running in *O(√log n)* rounds, albeit while using *O(√log n)* messages per node.

In this paper we study the same model and give a simple gossip algorithm which spreads a message in only *O(log log n)* rounds. We furthermore prove a matching *Ω(log log n)* lower bound which shows that this running time is best possible. In particular we show that any gossip algorithm takes with high probability at least *0.99 log log n* rounds to terminate. Lastly, our algorithm can be tweaked to send only *O(1)* messages per node on average with only *O(log n)* bits per message. Our algorithm therefore simultaneously achieves the optimal round-, message-, and bit-complexity for this setting. As all prior gossip algorithms, our algorithm is also robust against failures. In particular, if in the beginning an oblivious adversary fails any *F* nodes our algorithm still, with high probability, informs all but *o(F)* surviving nodes.

Publication type | Inproceedings |

Published in | PODC 2014 |

Publisher | ACM |

> Publications > Optimal Gossip with Direct Addressing