On Distributed Averaging Algorithms and Quantization Effects
We consider distributed iterative algorithms for the averaging problem over time-varying topologies. Our focus is on the convergence time of such algorithms when complete (unquantized) information is available, and on the degradation of performance when only quantized information is available. We st...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Online Access: | http://hdl.handle.net/1721.1/53586 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-2658-8239 |
| _version_ | 1826201670053265408 |
|---|---|
| author | Tsitsiklis, John N. Ozdaglar, Asuman E. Olshevsky, Alexander Nedic, Angelia |
| 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. Ozdaglar, Asuman E. Olshevsky, Alexander Nedic, Angelia |
| author_sort | Tsitsiklis, John N. |
| collection | MIT |
| description | We consider distributed iterative algorithms for the averaging problem over time-varying topologies. Our focus is on the convergence time of such algorithms when complete (unquantized) information is available, and on the degradation of performance when only quantized information is available. We study a large and natural class of averaging algorithms, which includes the vast majority of algorithms proposed to date, and provide tight polynomial bounds on their convergence time. We also describe an algorithm within this class whose convergence time is the best among currently available averaging algorithms for time-varying topologies. We then propose and analyze distributed averaging algorithms under the additional constraint that agents can only store and communicate quantized information, so that they can only converge to the average of the initial values of the agents within some error. We establish bounds on the error and tight bounds on the convergence time, as a function of the number of quantization levels. |
| first_indexed | 2024-09-23T11:54:54Z |
| format | Article |
| id | mit-1721.1/53586 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:54:54Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/535862022-10-01T06:55:29Z On Distributed Averaging Algorithms and Quantization Effects Tsitsiklis, John N. Ozdaglar, Asuman E. Olshevsky, Alexander Nedic, Angelia Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Tsitsiklis, John N. Tsitsiklis, John N. Ozdaglar, Asuman E. Olshevsky, Alexander We consider distributed iterative algorithms for the averaging problem over time-varying topologies. Our focus is on the convergence time of such algorithms when complete (unquantized) information is available, and on the degradation of performance when only quantized information is available. We study a large and natural class of averaging algorithms, which includes the vast majority of algorithms proposed to date, and provide tight polynomial bounds on their convergence time. We also describe an algorithm within this class whose convergence time is the best among currently available averaging algorithms for time-varying topologies. We then propose and analyze distributed averaging algorithms under the additional constraint that agents can only store and communicate quantized information, so that they can only converge to the average of the initial values of the agents within some error. We establish bounds on the error and tight bounds on the convergence time, as a function of the number of quantization levels. Defence Advanced Research Projects Agency. Information Theory for Mobile Ad-Hoc Networks Program National Science Foundation (Grants ECCS-0701623, CMMI 07-42538, and DMI-0545910) 2010-04-08T16:59:58Z 2010-04-08T16:59:58Z 2009-10 2009-01 Article http://purl.org/eprint/type/JournalArticle 0018-9286 http://hdl.handle.net/1721.1/53586 Nedic, A. et al. “On Distributed Averaging Algorithms and Quantization Effects.” Automatic Control, IEEE Transactions on 54.11 (2009): 2506-2517. © 2009 IEEE https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-2658-8239 en_US http://dx.doi.org/10.1109/tac.2009.2031203 IEEE Transactions on Automatic Control 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 |
| spellingShingle | Tsitsiklis, John N. Ozdaglar, Asuman E. Olshevsky, Alexander Nedic, Angelia On Distributed Averaging Algorithms and Quantization Effects |
| title | On Distributed Averaging Algorithms and Quantization Effects |
| title_full | On Distributed Averaging Algorithms and Quantization Effects |
| title_fullStr | On Distributed Averaging Algorithms and Quantization Effects |
| title_full_unstemmed | On Distributed Averaging Algorithms and Quantization Effects |
| title_short | On Distributed Averaging Algorithms and Quantization Effects |
| title_sort | on distributed averaging algorithms and quantization effects |
| url | http://hdl.handle.net/1721.1/53586 https://orcid.org/0000-0002-1827-1285 https://orcid.org/0000-0003-2658-8239 |
| work_keys_str_mv | AT tsitsiklisjohnn ondistributedaveragingalgorithmsandquantizationeffects AT ozdaglarasumane ondistributedaveragingalgorithmsandquantizationeffects AT olshevskyalexander ondistributedaveragingalgorithmsandquantizationeffects AT nedicangelia ondistributedaveragingalgorithmsandquantizationeffects |