A probabilistic characterization of a fault-tolerant gossiping algorithm |
| |
Authors: | Xiaohu Li Paul Parker Shouhuai Xu |
| |
Institution: | (1) Department of Computer Science, University of Texas at San Antonio, One UTSA Circle, San Antonio, TX 78249, USA |
| |
Abstract: | Gossiping is a popular technique for probabilistic reliable multicast (or broadcast). However, it is often difficult to understand
the behavior of gossiping algorithms in an analytic fashion. Indeed, existing analyses of gossip algorithms are either based
on simulation or based on ideas borrowed from epidemic models while inheriting some features that do not seem to be appropriate
for the setting of gossiping. On one hand, 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. On the other hand, the often assumed homogeneity
in epidemic spreading models (especially that every node has equal contact to everyone else in the population) has been silently
inherited in the gossiping literature, meaning that an expensive membership protocol is often needed for maintaining nodes’
views. Motivated by these observations, the authors present a characterization of a popular class of fault-tolerant gossip
schemes (known as “push-based gossiping”) based on a novel probabilistic model, while taking the afore-mentioned factors into
consideration.
This work is supported in part by the US National Science Foundation.
The views and conclusions contained in the paper are those of the authors and should not be interpreted as, in any sense,
the official policies or endorsements of the government or the agencies. |
| |
Keywords: | Fault-tolerance gossip probabilistic broadcast reliable multicast |
本文献已被 SpringerLink 等数据库收录! |
|