A symmetric adaptive algorithm for speeding-up consensus

Performing distributed consensus in a network has been an important research problem for several years, and is directly applicable to sensor networks, autonomous vehicle formation, etc. While there exists a wide variety of algorithms that can be proven to asymptotically reach consensus, in applications involving time-varying parameters and tracking, it is often crucial to reach consensus “as quickly as possible”. In [?] it has been shown that, with global knowledge of the network topology, it is possible to optimize the convergence time in distributed averaging algorithms via solving a semi-definite program (SDP) to obtain the optimal averaging weights. Unfortunately, in most applications, nodes do not have knowledge of the full network topology and cannot implement the required SDP in a distributed fashion. In this paper, we present a symmetric adaptive weight algorithm for distributed consensus averaging on bi-directional noiseless networks. The algorithm uses an LMS (Least Mean Squares) approach to adaptively update the edge weights used to calculate each node´s values. The derivation shows that global error can be minimized in a distributed fashion and that the resulting adaptive weights are symmetric - symmetry being critical for convergence to the true average. Simulations show that convergence time is nearly equal to that of a non-symmetric adaptive algorithm developed in [?], and significantly better than that of the non-adaptive Metropolis-Hastings algorithm. Most importantly, our symmetric adaptive algorithm converges to the sample mean, whereas the method of [?] converges to an arbitrary value and results in significant error.