CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Simple gossiping with balls and bins

Boris Koldehofe (Institutionen för datavetenskap)
Göteborg : Chalmers University of Technology, 2002.

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 propagation 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.

Nyckelord: multipeer communication, gossipping, analytical evaluation

Denna post skapades 2013-06-11.
CPL Pubid: 178240


Institutioner (Chalmers)

Institutionen för datavetenskap (2002-2004)


Data- och informationsvetenskap

Chalmers infrastruktur

Ingår i serie

Technical report - Department of Computing Science, Chalmers University of Technology and Göteborg University 02-03