Averaging consensus over erasure channels via local synchronization

Averaging consensus on the values of nodes in a network is a principal problem in distributed computation. In the presence of erasure channels, conventional averaging consensus algorithms may not converge to the average value if packets are erased in arbitrary order. In this paper, we propose a “Pseudo-Synchronous Averaging Consensus” (PSAC) algorithm to guarantee averaging consensus over erasure channels by employing tagged packets. We show that the PSAC algorithm has a simple structure and it can work with just two tags “0” and “1”. In asynchronous networks, the PSAC algorithm is a synchronizer in the sense that it keeps the updates of various nodes in step with each other. By exploiting the broadcast nature of wireless links in complete graphs, the PSAC algorithm obtains the exact average value with minimum number of transmissions, in the asynchronous setting.