Distributed Stopping for Average Consensus in Digraphs

Abstract

We consider how iterative strategies for asymptotic average consensus in directed graphs (digraphs) can be adapted so that the nodes can determine, in a distributed fashion, a stopping criterion that allows them to terminate the execution of the iteration when approximate average consensus has been reached. The nodes are said to have reached approximate average consensus when each of them has a value that is close (in a way that we precisely define) to the desirable average. In a digraph, the absence of bidirectional communication links makes this task particularly challenging, due to the presence of asymmetric information (for a pair of nodes, only one of them may be aware of a discrepancy and may have no direct way of informing the other). The proposed algorithms can be used to cap the number of transmissions that are required in order to reach (approximate) average consensus, and we provide simulation studies that analyze performance with respect to this metric, and provide comparisons against existing work.