Local silencing rules for randomized gossip

Randomized gossip algorithms are attractive for collaborative in-network processing and aggregation because they are fully asynchronous, they require no overhead to establish and form routes, and they do not create any bottleneck or single point of failure. Previous studies have focused on analyzing the worst-case number of transmissions required to reach a specified level of accuracy. In a practical implementation, rather than always running for the worst-case number of transmissions, one would like to fix a final level of accuracy and have the algorithm run only until this level of accuracy is achieved, adapting to the initial condition and network topology. This paper describes and analyzes a local silencing rule: when a node's value has not changed significantly for enough consecutive gossip rounds, it no longer initiates new gossip transactions, thereby conserving transmissions. We provide theoretical guarantees on the final accuracy of the estimates, and we study the latency and message complexity of this approach through simulation. © 2011 IEEE.