Further results on randomized quantized averaging: A surplus-based approach

We have recently proposed a class of randomized gossip algorithms which solves the distributed averaging problem on directed graphs, with the constraint that each node has an integer-valued state. The essence of this algorithm is to maintain local records, called “surplus”, of individual state updates, thereby achieving average consensus even though the state sum of all nodes is not preserved. In this paper we study a modified version of this algorithm, whose feature is primarily in reducing both computation and communication effort. Concretely, each node needs to update fewer local variables, and each transmission of surplus requires only one bit. Under this modified algorithm we prove that reaching the average is ensured for arbitrary strongly connected graphs, a condition that is weaker than those in the literature for either real-valued or quantized states, in the sense that it does not require symmetric (or balanced) network structure. Finally, we provide numerical examples to illustrate the convergence result on a set of typical graph topologies.