Multi-stage discrete time and randomized dynamic average consensus

In this paper we propose a novel local interaction protocol which solves the discrete time dynamic average consensus problem, i.e., the consensus problem on the average value of a set of time-varying input signals in an undirected graph. The proposed interaction protocol is based on a multi-stage cascade of dynamic consensus filters which tracks the average value of the inputs with small and bounded error. We characterize its convergence properties for time-varying discrete-time inputs with bounded variations. The main novelty of the proposed algorithm is that, with respect to other dynamic average consensus protocols, we obtain the next unique set of advantages: i) The protocol, inspired by proportional dynamic consensus, does not exploit integral control actions or input derivatives, thus exhibits robustness to re-initialization errors, changes in the network size and noise in the input signals; ii) The proposed design allows to trade-off the quantity of information locally exchanged by the agents, i.e., the number of stages, with steady-state error, tracking error and convergence time; iii) The protocol can be implemented with randomized and asynchronous local state updates and keep in expectation the performance of the discrete-time version. Numerical examples are given to corroborate the theoretical findings, including the case where a new agent joins and leaves the network during the algorithm execution to show robustness to re-initialization errors during runtime.