More Web Proxy on the site http://driver.im/

Article

Free access

Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems

Author:

B. AwerbuchAuthors Info & Claims

STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing

Pages 230 - 240

https://doi.org/10.1145/28395.28421

Published: 01 January 1987 Publication History

Abstract

This paper develops linear time distributed algorithms for a class of problems in an asynchronous communication network. Those problems include Minimum-Weight Spanning Tree (MST), Leader Election, counting the number of network nodes, and computing a sensitive decomposable function (e.g. majority, parity, maximum, OR, AND).

The main problem considered is the problem of finding the MST. This problem, which has been known for at least 9 years, is one of the most fundamental and the most studied problems in the field of distributed network algorithms.

Any algorithm for any one of the problems above requires at least Ω(E + VlogV) communication and Ω(V) time in the general network. In this paper, we present new algorithms, which achieve those lower bounds. The best previous algorithm requires Θ(E + VlogV) in communication and Θ(V log V) in time.

Our result enables to improve algorithms for many other problems in distributed computing, achieving lower bounds on their communication and time complexities.

References

[1]

B. Awerbuch, "Complexity of Network Synchronization", Journal of the A CM, ~ol. 82, No. 4, October 1985, pp. 8O4-823.

Digital Library

[2]

P.A.Alsberg and J.D.Day, "A Principle for Resilient Sharing of Distributed Resources", Proceeding ~nd Int. Conference on Software Engineering, San-Francisco, October 1976.

Digital Library

[3]

Y.Aiek and E.Gafni, "Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks", Proceedings of 1985 PODC Conference, Minacki, Ontario, August 1985.

Digital Library

[4]

B. Awerbuch and S. Even, Reliable Broadest in Unreliable Networks, to appear in Networks.

[5]

B.Awerbuch and R.Gallager, "Distributed Breadth-FirsbSearch Algorithms", IEEE Symposium on Foundation8 of Computer Science, October 1985, Portland, Oregon.

[6]

B.Awerbuch, O.Goldreich and R.Vainish, "On message complexity of broadcast: a bamc lower bound", unpublished manuscript, January 1987.

[7]

B. Awerbueh and S.Micali, "Dynamic Deadlock Resolution Protocols with Bounded Complexities", uapublished manuscript, MIT, 1985.

[8]

B. Awerbuch and $.Micali, "Dynamic Deadlock Resolution Protocols", Proceedings o/~1986 FOOS Conference, Toronto, Ontario, October 1986.

[9]

B.Awerbuch and S.P!otkin, "A.n O(E+ Vlog2V) leader election in faulty networks", unp'ublished manuscript, MIT, December 1986.

[10]

J.E.Burns, "A Formal Model for Message-Passing Systems", TR-91, indiana Univ., Bloomington, May 1980.

[11]

F.Ch. in and H.F.Ting, "An almost linear time and O(l/log V+E) messages Distributed Algorithm for Minimum Weight Spanning Trees", Proce~'ding, of 1985 FOGS Conference, Portland, Oregon, October 1985.

[12]

Y.K. Dalai and R. Met~alfe, "Reserve Path Forwarding of Broadcast Packets", CA OM, Vol. 21, No. 12, pp. 1040-1048, December 1978.

Digital Library

[13]

G. Frederiekson and N.Lyneh, "The Impact of Synchronous Communication on the Problem of Electing a Leader in a }Ring", Proceedings of the 16'th ACM Sgtmpoalum on Theoqt of Computing, Washington, D.C., April 1984.

Digital Library

[14]

E.Gafni, "improvements in time complexities of two message-optimal algorithms", Proceedings of i~85 PODC Conference, Minaeki, Ontario, August 1985.

Digital Library

[15]

R.G. Ca!lager, P.A. Humblet and P.M. Spira, "A Distributed Algorithm for Minimum Weight Spanning Trees", ACM Trans. on Program. Lang. & Systems, Vol. 5, pp. 66-77, J~nuary 1983.

Digital Library

[16]

P. Kmaellakis, "An Election Problem in a Network", #.854 term paper, MIT, May 1978.

[17]

E.Korach, S.Moran and S.Zaks, "Tight Lower and Upper Bounds for some Distributed Algorithms for Complete Network of Processes", Proceeding, of 1985 PODC Conference, Vancouver, BC, August 1984.

Digital Library

[18]

D.A.Menasce, R.Muntz and J. Popek, "A Locking Protocol for Resource Coordination in Dmtributed Databases" Proceedinga of A CM $IGMOD, June 1978.

Digital Library

[19]

P.Spira, "Communication Complexity of distributed minimum spanning tree algorithms", ~nd Berkele~l Conferenee on Distributed Data Management and Computer Networks, Berkeley, California, June 1977.

Cited By

Ghaffari MTrygub AKuznetsov PGelles ROlivetti D(2024)A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSPProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662812(401-411)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662812
Mwotil AAnderson TKanagwa BStavrinos TBainomugisha E(2024)LowPaxos: State Machine Replication for Low Resource SettingsIEEE Access10.1109/ACCESS.2024.342158212(91272-91288)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3421582
Huang ZWu WFu CLiu XShan FWang JXu X(2023)Communication-Topology-preserving Motion Planning: Enabling Static Routing in UAV NetworksACM Transactions on Sensor Networks10.1145/363153020:1(1-39)Online publication date: 7-Nov-2023
https://dl.acm.org/doi/10.1145/3631530
Show More Cited By

Index Terms

Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems

Recommendations

On the shortest path and minimum spanning tree problems
An Optimal Minimum Spanning Tree Algorithm
A distributed algorithm for directed minimum-weight spanning tree
Abstract
In the directed minimum spanning tree problem (DMST, also called minimum weight arborescence), we are given a directed weighted graph, and a root node r. Our goal is to construct a minimum-weight directed spanning tree, rooted at r and oriented ... $\overset{}{} \sqrt{}^{}$ $\overset{}{}$ $\overset{}{}^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing

January 1987

471 pages

ISBN:0897912217

DOI:10.1145/28395

Editor:
Alfred V. Aho

Copyright © 1987 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1987

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC87

Sponsor:

SIGACT

STOC87: 19th Annual ACM Conference on Theory of Computing

New York, New York, USA

Acceptance Rates

STOC '87 Paper Acceptance Rate 50 of 165 submissions, 30%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

210
Total Citations
View Citations
2,739
Total Downloads

Downloads (Last 12 months)92
Downloads (Last 6 weeks)19

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghaffari MTrygub AKuznetsov PGelles ROlivetti D(2024)A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSPProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662812(401-411)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662812
Mwotil AAnderson TKanagwa BStavrinos TBainomugisha E(2024)LowPaxos: State Machine Replication for Low Resource SettingsIEEE Access10.1109/ACCESS.2024.342158212(91272-91288)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3421582
Huang ZWu WFu CLiu XShan FWang JXu X(2023)Communication-Topology-preserving Motion Planning: Enabling Static Routing in UAV NetworksACM Transactions on Sensor Networks10.1145/363153020:1(1-39)Online publication date: 7-Nov-2023
https://dl.acm.org/doi/10.1145/3631530
Ghosh RGhosh H(2023)Leader ElectionDistributed Systems10.1002/9781119825968.ch7(157-188)Online publication date: 10-Feb-2023
https://doi.org/10.1002/9781119825968.ch7
Haeupler BRäcke HGhaffari MLeonardi SGupta A(2022)Hop-constrained expander decompositions, oblivious routing, and distributed universal optimalityProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520026(1325-1338)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520026
Augustine JGilbert SKuhn FRobinson PSourav S(2022)Latency, capacity, and distributed minimum spanning treesJournal of Computer and System Sciences10.1016/j.jcss.2021.11.006126:C(1-20)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1016/j.jcss.2021.11.006
Gilbert SRobinson PSourav S(2022)Leader Election in Well-Connected GraphsAlgorithmica10.1007/s00453-022-01068-x85:4(1029-1066)Online publication date: 24-Nov-2022
https://doi.org/10.1007/s00453-022-01068-x
Rehman EKhan MSoomro TTaleb NAfifi MGhazal T(2021)Using Blockchain to Ensure Trust between Donor Agencies and NGOs in Under-Developed CountriesComputers10.3390/computers1008009810:8(98)Online publication date: 10-Aug-2021
https://doi.org/10.3390/computers10080098
AKUSTA DAGDEVIREN Z(2021)A Minimum Spanning Tree based Clustering Algorithm for Cloud based Large Scale Sensor NetworksEuropean Journal of Science and Technology10.31590/ejosat.960421Online publication date: 1-Jul-2021
https://doi.org/10.31590/ejosat.960421
Haeupler BWajc DZuzic GKhuller SVassilevska Williams V(2021)Universally-optimal distributed algorithms for known topologiesProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451081(1166-1179)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451081
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents