2013 · 25 citations · 31 references
ComputingComputer ScienceMathematicsAlgorithmsDistributed SystemsDynamical SystemsDistributed AlgorithmsDistributed ComputingDistributed ControlDistributed CoordinationIterative SolversMatrix ComputationConsensus Under Communication DelaysDirected Graph MatricesDistributed EstimationDistributed Linear AlgebraDistributed Problem SolvingDistributed State EstimationNeighbor Relations
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 N(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” N(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.
31
The internal model principle of control theory
Bruce A. Francis, W.M. Wonham · Automatica · 1976 · 2.8K citations