Average Consensus in the Presence of Delays in Directed Graph Topologies

Classical distributed algorithms for asymptotic average consensus typically assume timely and reliable exchange of information between neighboring components of a given multi-component system. These assumptions are not necessarily valid in practice due to varying delays that might affect computations at different nodes and/or transmissions at different links. In this work, we propose a protocol that overcomes this limitation and, unlike existing consensus protocols in the presence of delays, ensures asymptotic consensus to the exact average, despite the presence of arbitrary (but bounded) delays in the communication links. The protocol requires that each component has knowledge of the number of its out-neighbors (i.e., the number of components to which it can send information) and its proof of correctness relies on the weak convergence of a backward product of column stochastic matrices. The proposed algorithm is demonstrated via illustrative examples.