Non asymptotic bounds in asynchronous sum-weight gossip protocols
This work addresses the efficiency of distributed computation in networks, offering incremental improvements in analyzing message exchange requirements for consensus.
The paper tackles the problem of determining the minimal number of messages needed for consensus in asynchronous gossip protocols, providing a probabilistic bound for general graphs and explicit formulas for fully connected graphs based on node count and graph spectrum approximations.
This paper focuses on non-asymptotic diffusion time in asynchronous gossip protocols. Asynchronous gossip protocols are designed to perform distributed computation in a network of nodes by randomly exchanging messages on the associated graph. To achieve consensus among nodes, a minimal number of messages has to be exchanged. We provides a probabilistic bound to such number for the general case. We provide a explicit formula for fully connected graphs depending only on the number of nodes and an approximation for any graph depending on the spectrum of the graph.