Distributed averaging in the presence of a sparse cut

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Distributed averaging in the presence of a sparse cut

Full text

Pdf (253 KB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing table of contents

Toronto, Canada

SESSION: B3-1 table of contents

Pages 441-441

Year of Publication: 2008

ISBN:978-1-59593-989-0

Author

Hariharan Narayanan

University of Chicago, Chicago, USA

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 25, Citation Count: 0

Additional Information:

abstract index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1400751.1400836 What is a DOI?

ABSTRACT

We consider the question of averaging on a graph that has one sparse cut separating two subgraphs that are internally well connected. We exhibit a decentralized algorithm for such graphs that uses updates involving negative weights and has an averaging time that can be significantly shorter than the averaging time of known distributed averaging algorithms.

INDEX TERMS

Primary Classification:
H. Information Systems
H.0 GENERAL