Randomised broadcasting: Memory vs. randomness

In this paper we analyse broadcasting in d  -regular networks with good expansion properties. For the underlying communication, we consider modifications of the so-called random phone call model. In the standard version of this model, each node is allowed in every step to open a channel to a randomly chosen neighbour, and the channels can be used for bi-directional communication. Then, broadcasting on the graphs mentioned above can be performed in time O(logn), where n   is the size of the network. However, every broadcast algorithm with runtime O(logn) needs on average Ω(logn/logd) message transmissions per node for random graphs with expected degree d [11].In this paper we show that it is possible to save significantly on communications if the standard model is modified such that nodes can avoid opening channels to exactly the same neighbours in two consecutive steps. We consider the so-called Rr model where we assume that every node has a cyclic list of all of its neighbours, ordered in a random way. Then, in step i the node communicates with the i  -th neighbour from that list. We provide an O(logn) time algorithm which produces in average O(logn) transmissions per node in networks with suitably defined expansion properties. Furthermore, we present a related lower bound of Ω(logn/loglogn) for the average number of message transmissions. These results show that by using memory it is possible to reduce the number of transmissions per node by almost a quadratic factor.