A distributed algorithm for solving a linear algebraic equation

A distributed algorithm is described for solving a linear algebraic equation of the form Ax = b where A is a matrix for which the equation has at least one solution. The equation is simultaneously solved by m agents assuming each agent knows only a subset of the rows of the partitioned matrix [A b], the current estimates of the equation's solution generated by its neighbors, and nothing more. Each agent recursively updates its estimate of a solution by utilizing the current estimates generated by each of its neighbors. Neighbor relations are characterized by a time-dependent directed graph ℕ(t) whose vertices correspond to agents and whose arcs depict neighbor relations. It is shown that for any matrix A for which the equation has a solution and any sequence of 'repeatedly jointly strongly connected graphs' ℕ(t), t = 1, 2,..., the algorithm causes all agents' estimates to converge exponentially fast to the same solution to Ax = b. It is also shown that in the absence of transmission delays, convergence to a solution occurs even if the times at which each agent updates its estimates are not synchronized with the update times of its neighbors.