Distributed Asynchronous Algorithms for Solving Positive Definite Linear Equations over Dynamic Networks

This paper develops Subset Equalizing (SE), a distributed algorithm for solving a symmetric positive definite system of linear equations over a network of agents with arbitrary asynchronous interactions and membership dynamics, where each agent may join and leave the network at any time, for infinitely many times, and may lose all its memory upon leaving. To design and analyze SE, we introduce a time-varying Lyapunov-like function, defined on a state space with changing dimension, and a generalized concept of network connectivity, capable of handling such interactions and membership dynamics. Based on them, we establish the boundedness, asymptotic convergence, and exponential convergence of SE, along with a bound on its convergence rate. Finally, through extensive simulation, we demonstrate the effectiveness of SE in a volatile agent network and show that a special case of SE, termed Groupwise Equalizing, is significantly more bandwidth/energy efficient than two existing algorithms in multi-hop wireless networks.