Convergence speed of binary interval consensus (Q2910896)

Algorithms for distributed computation attract interest because of applications in peer-to-peer, sensor, online social networks and distributed databases. A problem of interest is the so-called binary consensus where, initially, each node of the network holds one of two states and the goal is to decide which of two states was initially held by the majority of nodes. This is done by a decentralized algorithm where changes are based on the information exchanged at contacts with other nodes restricted by the network topology. The paper focusses on binary interval consensus to find which of two partitions contains the average of the initial values held by the individual nodes, for this case it answers the question how fast the interval consensus converges to the final state. An upper bound of expected convergence time is found on arbitrary connected graphs. The method is demonstrated for complete graphs, paths, cycles and Erdős-Rényi graphs. The results show how the expected convergence time depends on the network structure and the voting margin defined as the difference between the fraction of nodes initially holding the majority state and the fraction of nodes initially holding the minority state.