Convergence Speed of Binary Interval Consensus

Overview

This paper considers 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. The paper derives 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 matrices. The paper instantiates the bound for particular networks of interest, including complete graphs, star-shaped networks, and Erdos-Renyi random graphs, and in the former two cases compare with alternative computations.