Average Consensus in the Presence of Delays and Dynamically Changing Directed Graph Topologies

Classical approaches for asymptotic convergence to the global average in a distributed fashion typically assume timely and reliable exchange of information between neighboring components of a given multi-component system. These assumptions are not necessarily valid in practical settings due to varying delays that might affect transmissions at different times, as well as possible changes in the underlying interconnection topology (e.g., due to component mobility). In this work, we propose protocols to overcome these limitations. We first consider a fixed interconnection topology (captured by a possibly directed graph) and propose a discrete-time protocol that can reach asymptotic aver-age consensus in a distributed fashion, 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 sends information). We subsequently extend the protocol to also handle changes in the underlying interconnection topology and describe a variety of rather loose conditions under which the modified protocol allows the components to reach asymptotic average consensus. The proposed algorithms are illustrated via examples