A lower bound for distributed averaging algorithms on the line graph
We derive lower bounds on the convergence speed of a widely used class of distributed averaging algorithms. In particular, we prove that any distributed averaging algorithm whose state consists of a single real number and whose (possibly nonlinear) update function satisfies a natural smoothness cond...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/73151 https://orcid.org/0000-0003-2658-8239 |
| _version_ | 1826206700780126208 |
|---|---|
| author | Tsitsiklis, John N. Olshevsky, Alexander |
| 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. Olshevsky, Alexander |
| author_sort | Tsitsiklis, John N. |
| collection | MIT |
| description | We derive lower bounds on the convergence speed of a widely used class of distributed averaging algorithms. In particular, we prove that any distributed averaging algorithm whose state consists of a single real number and whose (possibly nonlinear) update function satisfies a natural smoothness condition has a worst case running time of at least on the order of n[superscript 2] on a line network of n nodes. Our results suggest that increased memory or expansion of the state space is crucial for improving the running times of distributed averaging algorithms. |
| first_indexed | 2024-09-23T13:36:53Z |
| format | Article |
| id | mit-1721.1/73151 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:36:53Z |
| publishDate | 2012 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/731512022-10-01T16:03:55Z A lower bound for distributed averaging algorithms on the line graph Tsitsiklis, John N. Olshevsky, Alexander Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Tsitsiklis, John N. Olshevsky, Alexander We derive lower bounds on the convergence speed of a widely used class of distributed averaging algorithms. In particular, we prove that any distributed averaging algorithm whose state consists of a single real number and whose (possibly nonlinear) update function satisfies a natural smoothness condition has a worst case running time of at least on the order of n[superscript 2] on a line network of n nodes. Our results suggest that increased memory or expansion of the state space is crucial for improving the running times of distributed averaging algorithms. National Science Foundation (U.S.) (grant CMMI-0856063) National Science Foundation (U.S.) (grant ECCS-0701623) 2012-09-25T12:51:51Z 2012-09-25T12:51:51Z 2011-02 2010-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-7745-6 0743-1546 http://hdl.handle.net/1721.1/73151 Tsitsiklis, John N. and Alexander Olshevsky. "A lower bound for distributed averaging algorithms on the line graph." Proceedings of the 2010 IEEE Conference on Decision and Control (CDC): 4523-4528. © 2010 IEEE. https://orcid.org/0000-0003-2658-8239 en_US http://dx.doi.org/ 10.1109/CDC.2010.5716968 Proceedings of the 49th IEEE Conference on Decision and Control (CDC), 2010 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers (IEEE) IEEE |
| spellingShingle | Tsitsiklis, John N. Olshevsky, Alexander A lower bound for distributed averaging algorithms on the line graph |
| title | A lower bound for distributed averaging algorithms on the line graph |
| title_full | A lower bound for distributed averaging algorithms on the line graph |
| title_fullStr | A lower bound for distributed averaging algorithms on the line graph |
| title_full_unstemmed | A lower bound for distributed averaging algorithms on the line graph |
| title_short | A lower bound for distributed averaging algorithms on the line graph |
| title_sort | lower bound for distributed averaging algorithms on the line graph |
| url | http://hdl.handle.net/1721.1/73151 https://orcid.org/0000-0003-2658-8239 |
| work_keys_str_mv | AT tsitsiklisjohnn alowerboundfordistributedaveragingalgorithmsonthelinegraph AT olshevskyalexander alowerboundfordistributedaveragingalgorithmsonthelinegraph AT tsitsiklisjohnn lowerboundfordistributedaveragingalgorithmsonthelinegraph AT olshevskyalexander lowerboundfordistributedaveragingalgorithmsonthelinegraph |