Optimal gossip with direct addressing

Gossip algorithms spread information in distributed networks by nodes repeatedly forwarding 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 Elsasser [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.