A performance model of gossip-based update propagation

We consider the problem of propagating an update to nodes in a distributed system using two gossiping protocols. The first is an idealized algorithm with static and dynamic knowledge of the system, and the second is a simple randomized algorithm. We construct a theoretical model that allows us to derive work and completion time statistics under varying transmission delay distributions. Numerical results are obtained for both exponential and nonexponential transmission times using linear-algebraic queueing theory techniques. Additionally, we present the results of simulation experiments showing that under node churn assumptions, the randomized algorithm's performance is qualitatively different than in a fault-free system. © 2010 IEEE.

0 citations (Crossref) [2023-10-31] tex.type: Proceedings paper