Distributed Consensus Formation Through Unconstrained Gossiping
This work provides a theoretical foundation and analytical tools for ensuring valid consensus in distributed systems where nodes may receive conflicting information, addressing a practical bottleneck in gossip-based protocols.
The paper addresses the problem of nodes receiving multiple signals in gossip algorithms, which can lead to invalid states, by introducing conflict resolution mechanisms that guarantee convergence to a valid consensus under certain network conditions. The authors also develop a Markov chain-based methodology to analyze convergence probabilities and expected time, validated through simulations.
Gossip algorithms are widely used to solve the distributed consensus problem, but issues can arise when nodes receive multiple signals either at the same time or before they are able to finish processing their current work load. Specifically, a node may assume a new state that represents a linear combination of all received signals; even if such a state makes no sense in the problem domain. As a solution to this problem, we introduce the notion of conflict resolution for gossip algorithms and prove that their application leads to a valid consensus state when the underlying communication network possesses certain properties. We also introduce a methodology based on absorbing Markov chains for analyzing gossip algorithms that make use of these conflict resolution algorithms. This technique allows us to calculate both the probabilities of converging to a specific consensus state and the time that such convergence is expected to take. Finally, we make use of simulation to validate our methodology and explore the temporal behavior of gossip algorithms as the size of the network, the number of states per node, and the network density increase.