Distributed Asynchronous Algorithms for Solving Positive Definite Linear Equations over Networks—Part I: Agent Networks

—This two-part paper presents and analyzes a family of distributed asynchronous algorithms for solving symmetric positive definite systems of linear equations over networks. In this Part I, we develop Subset Equalizing (SE), a Lyapunov-based algorithm for solving such equations over networks of agents with arbitrary asynchronous interactions and spontaneous membership dynamics, both of which may be exogenously driven and completely unpredictable. To analyze the behavior of SE, we introduce several notions of network connectivity, capable of handling such interactions and membership dynamics, and a time-varying quadratic Lyapunov-like function, defined on a state space with changing dimension. Based on them, we derive sufficient conditions for ensuring the boundedness, asymptotic convergence, and exponential convergence of SE, and show that these conditions are mild. Finally, we illustrate the effectiveness of SE through an example, using it to perform unconstrained quadratic optimization over a volatile multi-agent system.