A Stochastic Characterization of a Fault-Tolerant Gossip Algorithm
Authors:
- Xiaohu LiXLXiaohu Li
- Paul ParkerPPPaul Parker
- Shouhuai XuSXShouhuai Xu
- 1 November 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15302059,p. 283-290
Abstract
Gossiping is a popular technique for probabilistic reliable multicast (or broadcast), whose service is often needed in reliable distributed computing and systems. However, existing analytic studies of gossip schemes are often based on ideas borrowed from epidemic models, and thus inherit some features that may not be appropriate for the setting of gossiping. Specifically, in epidemic spreading, an infected node typically intends to spread the infection an unbounded number of times (or rounds); whereas in gossiping, an infected node (i.e., a node having received the message in question) may prefer to gossip the message a bounded number of times. Motivated by this, we intend to understand the behavior of a simple abstraction and algorithm for a popular class of fault-tolerant gossip schemes.Keywords
This publication has 14 references indexed in Scilit:
- RaWMS -2006
- Feasibility and complexity of broadcasting with random transmission failures2005
- The Number of Neighbors Needed for Connectivity of Wireless NetworksWireless Networks, 2004
- Protocols and impossibility results for gossip-based communication mechanisms2003
- Random Geometric Graphs2003
- On diffusing updates in a Byzantine environment2003
- Spatial gossip and resource location protocols2001
- Bimodal multicastACM Transactions on Computer Systems, 1999
- Fault-tolerant broadcasting and gossiping in communication networksNetworks, 1996
- Epidemic algorithms for replicated database maintenance1987