Degree fluctuations and the convergence time of consensus algorithms
We consider a consensus algorithm in which every node in a time-varying undirected connected graph assigns equal weight to each of its neighbors. Under the assumption that the degree of any given node is constant in time, we show that the algorithm achieves consensus within a given accuracy ∈ on n n...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73573 https://orcid.org/0000-0003-2658-8239 |
| _version_ | 1811083906795962368 |
|---|---|
| author | Tsitsiklis, John N. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Tsitsiklis, John N. |
| author_sort | Tsitsiklis, John N. |
| collection | MIT |
| description | We consider a consensus algorithm in which every node in a time-varying undirected connected graph assigns equal weight to each of its neighbors. Under the assumption that the degree of any given node is constant in time, we show that the algorithm achieves consensus within a given accuracy ∈ on n nodes in time O(n[superscript 3]ln(n=∈)). Because there is a direct relation between consensus algorithms in time-varying environments and inhomogeneous random walks, our result also translates into a general statement on such random walks. Moreover, we give simple proofs that the convergence time becomes exponentially large in the number of nodes n under slight relaxations of the above assumptions. We prove that exponential convergence time is possible for consensus algorithms on fixed directed graphs, and we use an example of Cao, Spielman, and Morse to give a simple argument that the same is possible if the constant degrees assumption is even slightly relaxed. |
| first_indexed | 2024-09-23T12:41:30Z |
| format | Article |
| id | mit-1721.1/73573 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:41:30Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/735732022-10-01T10:31:09Z Degree fluctuations and the convergence time of consensus algorithms Tsitsiklis, John N. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Tsitsiklis, John N. We consider a consensus algorithm in which every node in a time-varying undirected connected graph assigns equal weight to each of its neighbors. Under the assumption that the degree of any given node is constant in time, we show that the algorithm achieves consensus within a given accuracy ∈ on n nodes in time O(n[superscript 3]ln(n=∈)). Because there is a direct relation between consensus algorithms in time-varying environments and inhomogeneous random walks, our result also translates into a general statement on such random walks. Moreover, we give simple proofs that the convergence time becomes exponentially large in the number of nodes n under slight relaxations of the above assumptions. We prove that exponential convergence time is possible for consensus algorithms on fixed directed graphs, and we use an example of Cao, Spielman, and Morse to give a simple argument that the same is possible if the constant degrees assumption is even slightly relaxed. 2012-10-03T18:02:10Z 2012-10-03T18:02:10Z 2011-12 2011-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-61284-799-3 978-1-61284-800-6 0743-1546 http://hdl.handle.net/1721.1/73573 Olshevsky, Alex, and John N. Tsitsiklis. “Degree Fluctuations and the Convergence Time of Consensus Algorithms.” 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), 2011. 6602–6607. https://orcid.org/0000-0003-2658-8239 en_US http://dx.doi.org/10.1109/CDC.2011.6160945 Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), 2011 Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Tsitsiklis, John N. Degree fluctuations and the convergence time of consensus algorithms |
| title | Degree fluctuations and the convergence time of consensus algorithms |
| title_full | Degree fluctuations and the convergence time of consensus algorithms |
| title_fullStr | Degree fluctuations and the convergence time of consensus algorithms |
| title_full_unstemmed | Degree fluctuations and the convergence time of consensus algorithms |
| title_short | Degree fluctuations and the convergence time of consensus algorithms |
| title_sort | degree fluctuations and the convergence time of consensus algorithms |
| url | http://hdl.handle.net/1721.1/73573 https://orcid.org/0000-0003-2658-8239 |
| work_keys_str_mv | AT tsitsiklisjohnn degreefluctuationsandtheconvergencetimeofconsensusalgorithms |