×

Efficient information exchange in the random phone-call model. (English) Zbl 1288.68008

Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-14161-4/pbk). Lecture Notes in Computer Science 6199, 127-138 (2010).
Summary: We consider the gossiping problem in the classical random phone-call model introduced by A. Demers et al. [“Epidemic algorithms for replicated database maintenance”, in: Proceedings of the 6th annual ACM symposium on principles of distributed computing, PODC 1987. New York, NY: ACM Press. 1–12 (1987; doi:10.1145/41840.41841)]. We are given a complete graph, in which every node has an initial message to be disseminated to all other nodes. In each step every node is allowed to establish a communication channel with a randomly chosen neighbour. R. Karp et al. [“Randomized rumor spreading”, in: Proceedings of the 41st annual symposium on foundations of computer science, FOCS 2000. Los Alamitos, CA: IEEE Computer Society Press. 565–574 (2000; doi:10.1109/SFCS.2000.892324)] proved that it is possible to design a randomized procedure performing \(O(n\log \log n)\) transmissions that accomplishes broadcasting in time \(O(\log n)\), with probability \(1 - n ^{ - } 1\).
In this paper we provide a lower bound argument that proves \(\Omega (n\log n)\) message complexity for any \(O(\log n)\)-time randomized gossiping algorithm, with probability \(1 - o(1)\). This should be seen as a separation result between broadcasting and gossiping in the random phone-call model.
We study gossiping at the two opposite points of the time and message complexity trade-off. We show that one can perform gossiping based on exchange of \(O(n\cdot \log n/\log \log n)\) messages in time \(O(\log ^{2} n/\log \log n)\), and based on exchange of \(O(n\log \log n)\) messages with the time complexity \(O(\sqrt n).\) Both results hold wit probability \(1 - n ^{ - 1}\).
Finally, we consider a model in which each node is allowed to store a small set of neighbours participating in its earlier transmissions. We show that in this model randomized gossiping based on exchange of \(O(n\log \log n)\) messages can be obtained in time \(O(\log n)\), with probability \(1 - n ^{ - 1}\).
For the entire collection see [Zbl 1194.68006].

MSC:

68M10 Network design and communication in computer systems
68M12 Network protocols
68M14 Distributed systems
PDFBibTeX XMLCite
Full Text: DOI