Microsoft

1Abstract – We consider the speed of convergence of an instance of the binary interval consensus, a distributed and decentralized algorithm for computing the quantized average value. With binary consensus problem, each node initially holds one of two states and the goal for each node is to correctly decide which one of the two states was initially held by the majority of nodes. We derive an upper bound on the expected convergence time that holds for arbitrary connected graphs; it is based on the location of the eigenvalues of some contact rate ma-trices. We instantiate our bound for particular networks of interest, including complete graphs, star-shaped networks, and Erdös-Rényi random graphs, and in the former two cases compare with alternative computations. We find that for all these examples our bound is of the exact order with respect to the number of nodes and in some cases yields the exact multiplicative constant. We pinpoint the fact that the expected convergence time critically depends on the voting margin defined as the difference between the proportions of nodes that initially held the majority and the minority states, respectively. We derive an exact relation between the expected convergence time and the voting margin, for some of these graphs, that reveals how the expected convergence time tends to infinity as the voting margin approaches zero. Our results provide insights on how the expected con-vergence time depends on the network topology which can be used for performance evaluation and network design. The results are of interest in the context of peer-to-peer systems; in particular, for sensor networks and distributed databases. I