Abstract | ||
---|---|---|
We consider consensus algorithms in their most general setting and provide conditions under which such algorithms are guaranteed to converge, almost surely, to a consensus. Let {A(t),B(t)} isin RN times N be (possibly) random, non-stationary matrices and {x(t),m(t)} isin RN times 1 be state and perturbation vectors, respectively. For any consensus algorithm of the form x(t + 1) = A(t)x(t) + B(t)m(t), we provide conditions under which consensus is achieved almost surely, i.e., Pr {limtrarrinfin x(t) = c1} = 1 for some c isin R. Moreover, we show that this general result subsumes recently reported results for specific consensus algorithms classes, including sum-preserving, non-sum-preserving, quantized and noisy gossip algorithms. Also provided are the e-converging time for any such converging iterative algorithm, i.e., the earliest time at which the vector x(t) is e close to consensus, and sufficient conditions for convergence in expectation to the initial node measurements average. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1109/INFCOM.2009.5062137 | Rio de Janeiro |
Keywords | Field | DocType |
iterative methods,matrix algebra,randomised algorithms,telecommunication network routing,vectors,iterative algorithm,nonsum-preserving gossip algorithm,perturbation vector,perturbed nonstationary consensus algorithm convergence,random nonstationary matrix,randomized algorithm,sum-preserving gossip algorithm,telecommunication network routing | Convergence (routing),Consensus algorithm,Randomized algorithm,Algorithm design,Iterative method,Matrix (mathematics),Stochastic process,Almost surely,Mathematics,Distributed computing | Conference |
ISSN | ISBN | Citations |
0743-166X E-ISBN : 978-1-4244-3513-5 | 978-1-4244-3513-5 | 3 |
PageRank | References | Authors |
0.83 | 17 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tuncer C. Aysal | 1 | 468 | 26.75 |
Kenneth E Barner | 2 | 354 | 39.58 |