Distributed Averaging in Dynamic Networks

The question of computing average of numbers present at nodes in a network in a distributed manner using gossip or message-passing algorithms has been of great recent interest across disciplines-algorithms, control and robotics, estimation, social networks, etc. It has served as a non-trivial, representative model for an important class of questions arising in these disciplines and thus guiding intellectual progress over the past few decades. In most of these applications, there is inherent dynamics present, such as changes in the network topology in terms of communication links, changes in the values of numbers present at nodes, and nodes joining or leaving. The effect of dynamics in terms of communication links on the design and analysis of algorithms for averaging is reasonably well understood, e. g., J. Tsitsiklis, Problems in decentralized decision making and computation, Ph.D. dissertation, MIT, 1984; D. Bertsekas et al., Convergence theories of distributed iterative processes: A survey, MIT, 1983; A. Jadbabaie et al., Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Trans. on Automatic Control, vol. 48, no. 6, pp. 988-1001, 2003; S. Boyd et al., Gossip algorithms: Design, analysis and applications, Proc. IEEE INFOCOM, 2005, pp. 1653-1664. However, little is known about the effect of other forms of dynamics. In this paper, we study the effect of such types of dynamics in the context of maintaining average in the network. Specifically, we design dynamics-aware message-passing or gossip algorithm that maintains good estimate of average in presence of continuous change in numbers at nodes. Clearly, in presence of such dynamics the best one can hope for is a tradeoff between the accuracy of each node's estimate of the average at each time instant and the rate of dynamics. For our algorithm, we characterize this tradeoff and establish it to be near optimal. The dependence of the accuracy of the algorithm on the rate of dynamics as well as on the underlying graph structure is quantified.