Simple gossiping with balls and bins
Key: Kol04SUI
Author: Boris Koldehofe
Date: January 2004
Kind: @article
Keywords: gossip, p2p, analysis
Abstract: Recent research suggests decentralised probabilistic protocols on support for multipeer communication. The protocols scale well and impose an even load on the system. They provide statistical guarantees for the reliability, i.e. an information sent from an arbitrary source will reach all its destinations. Analysing the reliability is based on modelling the ropagation of events as an epidemic process often referred to as gossiping or rumour spreading. This work provides a new method for analysing such protocols, by representing the propagation of information as a balls-and-bins game. The method gives a simple relation between the number of hops a gossip message is propagated and the reliability provided. This way it can facilitate the analysis of the multiple delivery problem, i.e. to prevent multiple deliveries of the same message to the application layer. By introducing a new protocol it is shown how existing approaches can be adapted to the balls-and-bins approach. Furthermore, the proposed method is applied to analyse the performance of this protocol.
View Full paper (PDF) | Download Full paper (PDF)

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, not withstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.