Optimal Gossip with Direct Addressing Regular Submission

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 �(logn) rounds while sending only O(loglogn) messages per node on average. They also showed that at least �(logn) rounds are necessary in this model and that algorithms achieving this round-complexity need to send ω(1) messages per node on average.