TY - JOUR
T1 - A probabilistic characterization of a fault-tolerant gossiping algorithm
AU - Li, Xiaohu
AU - Parker, Paul
AU - Xu, Shouhuai
PY - 2009/3
Y1 - 2009/3
N2 - 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.
AB - 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.
KW - Fault-tolerance
KW - Gossip
KW - Probabilistic broadcast
KW - Reliable multicast
UR - http://www.scopus.com/inward/record.url?scp=60649120552&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=60649120552&partnerID=8YFLogxK
U2 - 10.1007/s11424-009-9149-7
DO - 10.1007/s11424-009-9149-7
M3 - Article
AN - SCOPUS:60649120552
SN - 1009-6124
VL - 22
SP - 88
EP - 108
JO - Journal of Systems Science and Complexity
JF - Journal of Systems Science and Complexity
IS - 1
ER -