research-article

A log-star distributed maximal independent set algorithm for growth-bounded graphs

Authors:

Johannes Schneider,

Roger WattenhoferAuthors Info & Claims

PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing

Pages 35 - 44

https://doi.org/10.1145/1400751.1400758

Published: 18 August 2008 Publication History

Abstract

We present a novel distributed algorithm for the maximal independent set (MIS) problem. On growth-bounded graphs (GBG) our deterministic algorithm finishes in O(log* n) time, n being the number of nodes. In light of Linial's Ω(log* n) lower bound our algorithm is asymptotically optimal. Our algorithm answers prominent open problems in the ad hoc/sensor network domain. For instance, it solves the connected dominating set problem for unit disk graphs in O(log* n) time, exponentially faster than the state-of-the-art algorithm. With a new extension our algorithm also computes a delta+1 coloring in O(log* n) time, where delta is the maximum degree of the graph.

References

[1]

N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567--583, 1986.

Digital Library

[2]

K. Alzoubi, X. Li, Y. Wang, P. Wan, and O. Frieder. Geometric Spanners for Wireless Ad Hoc Networks. IEEE Transactions on Parallel and Distributed Systems, 14(5), 2003.

Digital Library

[3]

A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Sorting in Linear Time. Journal of Computer and System Sciences, 57:74--93, 1998.

Digital Library

[4]

B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin. Network decomposition and locality in distributed computation. In Proceedings of the 30 th Symposium on Foundations of Computer Science (FOCS), pages 364--369, 1989.

Digital Library

[5]

G. V. B Awerbuch. Distributed program checking: a paradigm for buildingself-stabilizing distributed protocols. In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science (FOCS), 1991.

Digital Library

[6]

R. Cole and U. Vishkin. Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Inf. Control, 70(1):32--54, 1986.

Digital Library

[7]

B. Gfeller and E. Vicari. A Randomized Distributed Algorithm for the Maximal Independent Set Problem in Growth-Bounded Graphs. In Proc. of the 26th ACM Symposium on Principles of Distributed Computing (PODC), 2007.

Digital Library

[8]

A. Goldberg, S. Plotkin, and G. Shannon. Parallel Symmetry-Breaking in Sparse Graphs. SIAM Journal on Discrete Mathematics (SIDMA), 1(4):434--446, 1988.

Digital Library

[9]

A. Israeli and A. Itai. A Fast and Simple Randomized Parallel Algorithm for Maximal Matching. Information Processing Letters, 22:77--80, 1986.

Digital Library

[10]

F. Kuhn, T. Moscibroda, T. Nieberg, and R. Wattenhofer. Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs. In Proc. of the 19th Int. Symposium on Distributed Computing (DISC), 2005.

Digital Library

[11]

F. Kuhn, T. Moscibroda, T. Nieberg, and R. Wattenhofer. Local Approximation Schemes for Ad Hoc and Sensor Networks. In Proc. of the 3rd ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), 2005.

Digital Library

[12]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. On the Locality of Bounded Growth. In Proceedings of the 24th ACM Symp. on Principles of Distributed Computing (PODC), pages 60--68, 2005.

Digital Library

[13]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. What Cannot Be Computed Locally! In Proc. of the 23rd ACM Symp. on Principles of Distributed Computing (PODC), pages 300--309, 2005.

Digital Library

[14]

C. Lenzen and R. Wattenhofer. Leveraging lineal's locality limit. In Submission.

Digital Library

[15]

N. Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1):193--201, 1992.

Digital Library

[16]

M. Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM Journal on Computing, 15:1036--1053, 1986.

Digital Library

[17]

T. Moscibroda and R. Wattenhofer. Maximal Independent Sets in Radio Networks. In Proceedings of the 24th ACM Symp. on Principles of Distributed Computing (PODC), pages 148--157, 2005.

Digital Library

[18]

A. Panconesi and A. Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proc. of the 24th annual ACM symposium on Theory of computing (STOC), pages 581--592. ACM Press, 1992.

Digital Library

[19]

J. Schneider and R. Wattenhofer. An Asymptotically Optimal Distributed Maximal Independent Set Algorithm for Wireless Networks with Collision Detection. In Submission.

Cited By

Jiang JTian WHan GZhang F(2024)A Medium Access Control Protocol Based on Parity Group-Graph Coloring for Underwater AUV-Aided Data CollectionIEEE Internet of Things Journal10.1109/JIOT.2023.330925111:4(5967-5979)Online publication date: 15-Feb-2024
https://doi.org/10.1109/JIOT.2023.3309251
Metkewar PBokhare A(2023)One stride ahead Advancements in Dispersed Graph Coloring2023 International Conference for Advancement in Technology (ICONAT)10.1109/ICONAT57137.2023.10080064(1-3)Online publication date: 24-Jan-2023
https://doi.org/10.1109/ICONAT57137.2023.10080064
La Chance EHallé S(2023)An investigation of distributed computing for combinatorial testingSoftware Testing, Verification and Reliability10.1002/stvr.184233:4Online publication date: 27-Feb-2023
https://doi.org/10.1002/stvr.1842
Show More Cited By

Index Terms

A log-star distributed maximal independent set algorithm for growth-bounded graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

A new technique for distributed symmetry breaking
PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

We introduce Multi-Trials, a new technique for symmetry breaking for distributed algorithms and apply it to various problems in general graphs. For instance, we present three randomized algorithms for distributed (vertex or edge) coloring improving on ...
Coloring unstructured wireless multi-hop networks
PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

We present a randomized coloring algorithm for the unstructured radio network model, a model comprising autonomous nodes, asynchronous wake-up, no collision detection and an unknown but geometric network topology. The current state-of-the-art coloring ...
An optimal maximal independent set algorithm for bounded-independence graphs

We present a novel distributed algorithm for the maximal independent set problem (This is an extended journal version of Schneider and Wattenhofer in Twenty-seventh annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, 2008). On ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing

August 2008

474 pages

ISBN:9781595939890

DOI:10.1145/1400751

General Chair:
Rida Bazzi
Arizona State University, USA
,
Program Chair:
Boaz Patt-Shamir
Tel Aviv University, Israel

Copyright © 2008 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 August 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '08

Sponsor:

PODC '08: ACM Symposium on Principles of Distributed Computing

August 18 - 21, 2008

Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

108
Total Citations
View Citations
668
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jiang JTian WHan GZhang F(2024)A Medium Access Control Protocol Based on Parity Group-Graph Coloring for Underwater AUV-Aided Data CollectionIEEE Internet of Things Journal10.1109/JIOT.2023.330925111:4(5967-5979)Online publication date: 15-Feb-2024
https://doi.org/10.1109/JIOT.2023.3309251
Metkewar PBokhare A(2023)One stride ahead Advancements in Dispersed Graph Coloring2023 International Conference for Advancement in Technology (ICONAT)10.1109/ICONAT57137.2023.10080064(1-3)Online publication date: 24-Jan-2023
https://doi.org/10.1109/ICONAT57137.2023.10080064
La Chance EHallé S(2023)An investigation of distributed computing for combinatorial testingSoftware Testing, Verification and Reliability10.1002/stvr.184233:4Online publication date: 27-Feb-2023
https://doi.org/10.1002/stvr.1842
Ghaffari MPortmann JAgrawal KLee I(2022)Average Awake Complexity of MIS and MatchingProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538566(45-55)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538566
Eppstein DKhodabandeh HAgrawal KLee I(2022)Brief Announcement: Distributed Lightweight Spanner Construction for Unit Ball Graphs in Doubling MetricsProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538553(57-59)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538553
Hourani KPandurangan GRobinson P(2022)Awake-Efficient Distributed Algorithms for Maximal Independent Set2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS54860.2022.00153(1338-1339)Online publication date: Jul-2022
https://doi.org/10.1109/ICDCS54860.2022.00153
Elkin MNeiman O(2022)Distributed strong diameter network decompositionTheoretical Computer Science10.1016/j.tcs.2022.04.019922(150-157)Online publication date: Jun-2022
https://doi.org/10.1016/j.tcs.2022.04.019
Akhoondian Amiri SWiederhake B(2022)Distributed distance-r covering problems on sparse high-girth graphsTheoretical Computer Science10.1016/j.tcs.2022.01.001Online publication date: Jan-2022
https://doi.org/10.1016/j.tcs.2022.01.001
Barenboim LOren G(2022)Distributed backup placementDistributed Computing10.1007/s00446-022-00423-z35:5(455-473)Online publication date: 24-Mar-2022
https://doi.org/10.1007/s00446-022-00423-z
Oren GBarenboim L(2021)Distributed Backup K-Placement and Applications to Virtual Memory in Wireless NetworksAdjunct Proceedings of the 2021 International Conference on Distributed Computing and Networking10.1145/3427477.3429466(139-144)Online publication date: 5-Jan-2021
https://dl.acm.org/doi/10.1145/3427477.3429466
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents