Analysis of accelerated gossip algorithms

J. Liu; B. D.O. Anderson; M. Cao; A. S. Morse

doi:10.1109/CDC.2009.5399566

Analysis of accelerated gossip algorithms

J. Liu
, B. D.O. Anderson
, M. Cao
, A. S. Morse

Electrical Engineering

Australian National University
University of Groningen
Yale University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

19 Scopus citations

Abstract

This paper investigates accelerated gossip algorithms for distributed computations in networks where shiftregisters are utilized at each node. By using tools from matrix analysis, we prove the existence of the desired acceleration and establish the fastest rate of convergence in expectation for two-register symmetric gossip. Some classes of networks with regular graph topologies are studied in detail to validate the analytical results by comparison with existing empirical data. We also analyze convergence of second moment and provide a necessary condition for convergence in multi-register symmetric gossip. The proposed approach has the potential to be applied to the more challenging open problem of asymmetric gossip.

Original language	English
Title of host publication	Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	871-876
Number of pages	6
ISBN (Print)	9781424438716
DOIs	https://doi.org/10.1109/CDC.2009.5399566
State	Published - 2009
Event	48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009 - Shanghai, China Duration: Dec 15 2009 → Dec 18 2009

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009
Country/Territory	China
City	Shanghai
Period	12/15/09 → 12/18/09

Access to Document

10.1109/CDC.2009.5399566

Cite this

Liu, J., Anderson, B. D. O., Cao, M., & Morse, A. S. (2009). Analysis of accelerated gossip algorithms. In Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009 (pp. 871-876). Article 5399566 (Proceedings of the IEEE Conference on Decision and Control). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2009.5399566

@inproceedings{1ce0f83fdb31401fa12bc5582f87f60c,

title = "Analysis of accelerated gossip algorithms",

abstract = "This paper investigates accelerated gossip algorithms for distributed computations in networks where shiftregisters are utilized at each node. By using tools from matrix analysis, we prove the existence of the desired acceleration and establish the fastest rate of convergence in expectation for two-register symmetric gossip. Some classes of networks with regular graph topologies are studied in detail to validate the analytical results by comparison with existing empirical data. We also analyze convergence of second moment and provide a necessary condition for convergence in multi-register symmetric gossip. The proposed approach has the potential to be applied to the more challenging open problem of asymmetric gossip.",

author = "J. Liu and Anderson, \{B. D.O.\} and M. Cao and Morse, \{A. S.\}",

year = "2009",

doi = "10.1109/CDC.2009.5399566",

language = "English",

isbn = "9781424438716",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "871--876",

booktitle = "Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009",

note = "48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009 ; Conference date: 15-12-2009 Through 18-12-2009",

}

Liu, J, Anderson, BDO, Cao, M & Morse, AS 2009, Analysis of accelerated gossip algorithms. in Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009., 5399566, Proceedings of the IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers Inc., pp. 871-876, 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009, Shanghai, China, 12/15/09. https://doi.org/10.1109/CDC.2009.5399566

Analysis of accelerated gossip algorithms. / Liu, J.; Anderson, B. D.O.; Cao, M. et al.
Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009. Institute of Electrical and Electronics Engineers Inc., 2009. p. 871-876 5399566 (Proceedings of the IEEE Conference on Decision and Control).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Analysis of accelerated gossip algorithms

AU - Liu, J.

AU - Anderson, B. D.O.

AU - Cao, M.

AU - Morse, A. S.

PY - 2009

Y1 - 2009

N2 - This paper investigates accelerated gossip algorithms for distributed computations in networks where shiftregisters are utilized at each node. By using tools from matrix analysis, we prove the existence of the desired acceleration and establish the fastest rate of convergence in expectation for two-register symmetric gossip. Some classes of networks with regular graph topologies are studied in detail to validate the analytical results by comparison with existing empirical data. We also analyze convergence of second moment and provide a necessary condition for convergence in multi-register symmetric gossip. The proposed approach has the potential to be applied to the more challenging open problem of asymmetric gossip.

AB - This paper investigates accelerated gossip algorithms for distributed computations in networks where shiftregisters are utilized at each node. By using tools from matrix analysis, we prove the existence of the desired acceleration and establish the fastest rate of convergence in expectation for two-register symmetric gossip. Some classes of networks with regular graph topologies are studied in detail to validate the analytical results by comparison with existing empirical data. We also analyze convergence of second moment and provide a necessary condition for convergence in multi-register symmetric gossip. The proposed approach has the potential to be applied to the more challenging open problem of asymmetric gossip.

UR - https://www.scopus.com/pages/publications/77950853682

U2 - 10.1109/CDC.2009.5399566

DO - 10.1109/CDC.2009.5399566

M3 - Conference contribution

AN - SCOPUS:77950853682

SN - 9781424438716

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 871

EP - 876

BT - Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009

Y2 - 15 December 2009 through 18 December 2009

ER -

Liu J, Anderson BDO, Cao M, Morse AS. Analysis of accelerated gossip algorithms. In Proceedings of the 48th IEEE Conference on Decision and Control held jointly with 2009 28th Chinese Control Conference, CDC/CCC 2009. Institute of Electrical and Electronics Engineers Inc. 2009. p. 871-876. 5399566. (Proceedings of the IEEE Conference on Decision and Control). doi: 10.1109/CDC.2009.5399566

Analysis of accelerated gossip algorithms

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this