skip to main content
article

Asynchronous distributed averaging on communication networks

Published: 01 June 2007 Publication History

Abstract

Distributed algorithms for averaging have attracted interest in the control and sensing literature. However, previous works have not addressed some practical concerns that will arise in actual implementations on packet-switched communication networks such as the Internet. In this paper, we present several implementable algorithms that are robust to asynchronism and dynamic topology changes. The algorithms are completely distributed and do not require any global coordination. In addition, they can be proven to converge under very general asynchronous timing assumptions. Our results are verified by both simulation and experiments on Planetlab, a real-world TCP/IP network. We also present some extensions that are likely to be useful in applications.

References

[1]
{1} D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Englewood Cliffs, NJ: Prentice-Hall, 1989.
[2]
{2} S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, "Gossip algorithms: Design, analysis and applications," in Proc. IEEE INFOCOM, 2005.
[3]
{3} B. Cohen, Incentives build robustness in Bittorrent. {Online}. Available: http://bitconjurer.org/BitTorrent/bittorrentecon.pdf
[4]
{4} A. Fax and R. M. Murray, "Information flow and cooperative control of vehicle formations," IEEE Trans. Autom. Contr., vol. 49, pp. 1465-1476, Sep. 2004.
[5]
{5} KaZaA. {Online}. Available: http://www.kazaa.com
[6]
{6} D. Kempe, A. Dobra, and J. Gehrke, "Computing aggregate information using Gossip," in Proc. FOCS, 2003.
[7]
{7} D. Kempe and F. McSherry, "A decentralized algorithm for spectral analaysis," in Proc. STOC, 2004.
[8]
{8} N. Lynch, Distributed Algorithms. San Mateo, CA: Morgan Kaufmann, 1997.
[9]
{9} M. Mehyar, D. Spanos, J. Pongsajapan, S. H. Low, and R. M. Murray, "Distributed averaging on asynchronous communication networks," in Proc. IEEE Conf. Decision and Control, 2005.
[10]
{10} R. Merris, "Laplacian matrices of a graph: A survey," Linear Algebra and Its Applications, vol. 197, pp. 143-176, 1994.
[11]
{11} R. Olfati-Saber and R. Murray, "Consensus problems in networks of agents with switching topology and time-delays," IEEE Trans. Autom. Contr., vol. 49, no. 9, pp. 1520-1533, Sep. 2004.
[12]
{12} PlanetLab. {Online}. Available: http://www.planet-lab.org
[13]
{13} D. S. Scherber and H. C. Papadopoulos, "Distributed computation of averages over ad hoc networks," IEEE J. Sel. Areas Commun., vol. 23, no. 4, pp. 776-787, Apr. 2005.
[14]
{14} D. Spanos, R. Olfati-Saber, and R. M. Murray, "Distributed sensor fusion using dynamic consensus," in Proc. IFAC, 2005.
[15]
{15} D. P. Spanos, R. Olfati-Saber, and R. M. Murray, "Dynamic consensus on mobile networks," in Proc. IFAC, 2005.
[16]
{16} D. Spanos, R. Olfati-Saber, and R. M. Murray, "Distributed Kalman filtering in sensor networks with quantifiable performance," in Proc. IPSN, 2005.
[17]
{17} J. N. Tsitsiklis, "Problems in decentralized decision making and computation" Ph.D. dissertation, Dept. Electr. Eng. Comput. Sci., Massachusetts Inst. Technol., Cambridge, 1984 {Online}. Available: http:// web.mit.edu/jnt/www/PhD-84-jnt.pdf
[18]
{18} J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans, "Distributed asynchronous deterministic and stochastic gradient optimization algorithms," IEEE Trans. Autom. Contr., vol. 31, no. 9, pp. 803-812, 1986.
[19]
{19} L. Xiao and S. Boyd, "Fast linear iterations for distributed averaging," in Proc. Conf. Decision and Control, 2003.
[20]
{20} L. Xiao, S. Boyd, and S. Lall, "A scheme for asynchronous distributed sensor fusion based on average consensus," in Proc. IPSN, 2005.

Cited By

View all
  • (2023)Delay-agnostic asynchronous coordinate update algorithmProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619973(37582-37606)Online publication date: 23-Jul-2023
  • (2021)On Wireless Link Connectivity for Resilient Multi-Hop NetworksMILCOM 2021 - 2021 IEEE Military Communications Conference (MILCOM)10.1109/MILCOM52596.2021.9652882(285-290)Online publication date: 29-Nov-2021
  • (2018)Gossip Algorithms that Preserve Privacy for Distributed Computation Part I: The Algorithms and Convergence Conditions2018 IEEE Conference on Decision and Control (CDC)10.1109/CDC.2018.8619783(4499-4504)Online publication date: 17-Dec-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 15, Issue 3
June 2007
249 pages

Publisher

IEEE Press

Publication History

Published: 01 June 2007
Published in TON Volume 15, Issue 3

Author Tags

  1. asynchronous computation
  2. distributed averaging

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 07 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2023)Delay-agnostic asynchronous coordinate update algorithmProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619973(37582-37606)Online publication date: 23-Jul-2023
  • (2021)On Wireless Link Connectivity for Resilient Multi-Hop NetworksMILCOM 2021 - 2021 IEEE Military Communications Conference (MILCOM)10.1109/MILCOM52596.2021.9652882(285-290)Online publication date: 29-Nov-2021
  • (2018)Gossip Algorithms that Preserve Privacy for Distributed Computation Part I: The Algorithms and Convergence Conditions2018 IEEE Conference on Decision and Control (CDC)10.1109/CDC.2018.8619783(4499-4504)Online publication date: 17-Dec-2018
  • (2018)Gossip Algorithms that Preserve Privacy for Distributed Computation Part II: Performance Against Eavesdroppers2018 IEEE Conference on Decision and Control (CDC)10.1109/CDC.2018.8619065(5346-5351)Online publication date: 17-Dec-2018
  • (2017)Average consensus-based asynchronous tracking2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP.2017.7952988(4401-4405)Online publication date: 5-Mar-2017
  • (2015)Bucket-Filling: An Asymptotically Optimal Video-on-Demand Network With Source CodingIEEE Transactions on Multimedia10.1109/TMM.2015.241663617:5(723-735)Online publication date: 1-May-2015
  • (2015)A Survey of Distributed Data Aggregation AlgorithmsIEEE Communications Surveys & Tutorials10.1109/COMST.2014.235439817:1(381-404)Online publication date: 16-Mar-2015
  • (2014)A correction to algorithm A2 in "Asynchronous distributed averaging on communication networks"IEEE/ACM Transactions on Networking10.1109/TNET.2013.229280022:6(2026-2027)Online publication date: 1-Dec-2014
  • (2013)In-network outlier detection in wireless sensor networksKnowledge and Information Systems10.1007/s10115-011-0474-534:1(23-54)Online publication date: 1-Jan-2013
  • (2010)A vEB-tree-based architecture for interactive video on demand services in peer-to-peer networksJournal of Network and Computer Applications10.1016/j.jnca.2010.03.02133:4(353-362)Online publication date: 1-Jul-2010
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media