A communication-efficient distributed algorithm for solving linear algebraic equations

This paper proposes a communication-efficient distributed algorithm for solving linear algebraic equations of the form Ax = b among a network of m > 1 agents. Each agent knows only a subset of the rows of the partitioned matrix [A b] and recursively updates its estimate of a solution by utilizing information received only from its neighbors. Neighbor relations are characterized by a time-dependent undirected graph. To reduce communication costs at each iteration, each agent broadcasts the entries of its estimate in a cyclic manner, instead of broadcasting the entire vector of its estimate. It is shown that for any matrix A and vector b for which the equation has at least one solution and any repeatedly jointly connected sequence of neighbor graphs, the algorithm causes all agents' estimates to converge to the same solution to Ax = b under appropriate assumption. An asynchronous version of the algorithm is also proposed in which each agent independently updates its estimate at times determined by its own clock. It is not assumed that the agents' clocks are synchronized or that the event times at which any one agent updates its estimate are evenly spaced. It is shown that in the absence of transmission delays, convergence to the same solution occurs even if the cycle with which each agent broadcasts the entries of its estimate is not consistent with the cycles of its neighbors.