Distributed Stopping Criterion for Consensus in the Presence of Delays

Abstract

Linear consensus protocol is an iterative distributed algorithm with asymptotic convergence guarantees. This paper develops and analyzes an algorithm for agents running linear consensus iterations to detect convergence to consensus within a specified error tolerance in a distributed manner. The distributed stopping criterion allows for time-varying bounded delays in information transmission and reception between agents. The algorithm relies on distributively determining the maximum and minimum values held by the agents. This paper further develops an algorithm for average consensus that utilizes a distributive stopping criterion, based on maximum and minimum consensus, where no centralized coordination is needed on how each agent weights its neighbor's values. Here, the doubly stochastic assumption on the weight matrix is relaxed and only column stochasticity is needed. The effectiveness of the algorithms is demonstrated by simulations and a comparison with prior work in the literature. Moreover, the demonstration of the proposed algorithms on an experimental test bed of Raspberry-Pi agents communicating wirelessly validates its applicability and utility.