article

Some simple distributed algorithms for sparse networks

Authors:

Alessandro Panconesi,

Romeo RizziAuthors Info & Claims

Distributed Computing, Volume 14, Issue 2

Pages 97 - 100

https://doi.org/10.1007/PL00008932

Published: 01 April 2001 Publication History

Abstract

We give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most 2Δ-1 colours, and maximal matchings can be computed within O(log^* n + Δ) deterministic rounds, where Δ is the maximum degree of the network. We also show how to find maximal independent sets and (Δ + 1)-vertex colourings within O(log^* n + Δ²) deterministic rounds. All hidden constants are very small and the algorithms are very simple.

References

[1]

1. B. Awerbuch, A. V. Goldberg, M. Luby, S.A. Plotkin: Network decomposition and locality in distributed computation. In 30th Annual Symposium on Foundations of Computer Science, p 364-369 IEEE, November 1989.

Digital Library

Google Scholar

[2]

2. R. Jain, J. Werth, J.C. Browne, G. Sasaki: A graph-theoretic model for the scheduling problem and its application to simultaneous resource scheduling, In: Computer Science and Operations Research: New Developments in Their Interfaces, O. Balci, R. Shander, S. Zerrick (eds) Penguin Press, 1992.

Google Scholar

[3]

3. R. Jain, K. Somalwar, J. Werth, J.C. Browne: Scheduling Parallel I/O Operations in Multiple Bus Systems, J Parallel Distrib Comput 16(4), 352-362 (1992).

Crossref

Google Scholar

[4]

4. R. Jain, J. Werth: Analysis of Approximate Algorithms for Constrained and Unconstrained Edge Coloring of Bipartite Graphs, DIMACS Technical Report, 95-01 January, 1995, Information Processing Letters 54(3), 163-168 (1995).

Crossref

Google Scholar

[5]

5. A. Goldberg, S.A. Plotkin: Parallel (Δ + 1)-coloring of constantdegree graphs. Inform. Process. Lett., 25(4), 241-245 (1987).

Digital Library

Google Scholar

[6]

6. A. Goldberg, S. Plotkin, G.E. Shannon: Parallel symmetry breaking in sparse graphs SIAM J. Disc. Math. 1(4), 434-446 (1988).

Digital Library

Google Scholar

[7]

7. A. Goldberg, M. Luby, S. Plotkin, G.E. Shannon: Parallel symmetry breaking in sparse graphs SIAM J. Disc. Math. 1(4), 434-446 (1988).

Digital Library

Google Scholar

[8]

8. M. Hanckowiak, M. Karonski, A. Panconesi: A faster distributed algorithm for computing maximal matchings deterministically, in Proceedings of PODC 99, the Eighteenth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing.

Crossref

Google Scholar

[9]

9. N. Linial: Locality in distributed graph algorithms, SIAM J. Comput. 21(1), 193-201 (1992).

Digital Library

Google Scholar

[10]

10. N. Linial, M. Saks: Low diameter graph decompositions, Combinatorica 13(4), 441-454 (1993).

Crossref

Google Scholar

Cited By

View all

Dahal SSuomela J(2024)Distributed half-integral matching and beyondTheoretical Computer Science10.1016/j.tcs.2023.114278982:COnline publication date: 8-Jan-2024
https://dl.acm.org/doi/10.1016/j.tcs.2023.114278
Czumaj ADavies-Peck PParter M(2024)Component stability in low-space massively parallel computationDistributed Computing10.1007/s00446-024-00461-937:1(35-64)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s00446-024-00461-9
Dahal SSuomela J(2023)Distributed Half-Integral Matching and BeyondStructural Information and Communication Complexity10.1007/978-3-031-32733-9_15(339-356)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-32733-9_15
Show More Cited By

Index Terms

Some simple distributed algorithms for sparse networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Graph enumeration
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems

Recommendations

The Locality of Distributed Symmetry Breaking
FOCS '12: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science

We present new bounds on the locality of several classical symmetry breaking tasks in distributed networks. A sampling of the results include \begin{enumerate} \item A randomized algorithm for computing a maximal matching (MM) in $O(\log\Delta + (\log\...
Locally-Iterative Distributed (Δ+ 1): -Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models
PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing

We consider graph coloring and related problems in the distributed message-passing model. \em Locally-iterative algorithms are especially important in this setting. These are algorithms in which each vertex decides about its next color only as a ...
Node and edge averaged complexities of local graph problems
Abstract
We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph $G = (V, E)$ is the average over the times at which ... $\frac{}{} \sqrt{\frac{}{}}$ $\frac{}{} \sqrt{\frac{}{}}$ $\sqrt{}$ $\frac{}{} \sqrt{\frac{}{}}$ $^{}^{}$ $^{}^{}$ $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Distributed Computing Volume 14, Issue 2

April 2001

58 pages

ISSN:0178-2770

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 2001

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dahal SSuomela J(2024)Distributed half-integral matching and beyondTheoretical Computer Science10.1016/j.tcs.2023.114278982:COnline publication date: 8-Jan-2024
https://dl.acm.org/doi/10.1016/j.tcs.2023.114278
Czumaj ADavies-Peck PParter M(2024)Component stability in low-space massively parallel computationDistributed Computing10.1007/s00446-024-00461-937:1(35-64)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s00446-024-00461-9
Dahal SSuomela J(2023)Distributed Half-Integral Matching and BeyondStructural Information and Communication Complexity10.1007/978-3-031-32733-9_15(339-356)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-32733-9_15
Balliu ABrandt SKuhn FOlivetti DMilani AWoelfel P(2022)Distributed Edge Coloring in Time Polylogarithmic in ΔProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538440(15-25)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538440
Maus YTonoyan T(2022)Linial for listsDistributed Computing10.1007/s00446-022-00424-y35:6(533-546)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s00446-022-00424-y
Barenboim LOren G(2022)Distributed backup placementDistributed Computing10.1007/s00446-022-00423-z35:5(455-473)Online publication date: 24-Mar-2022
https://dl.acm.org/doi/10.1007/s00446-022-00423-z
Barenboim LElkin MGoldenberg U(2021)Locally-iterative Distributed (Δ + 1)-coloring and ApplicationsJournal of the ACM10.1145/348662569:1(1-26)Online publication date: 7-Dec-2021
https://dl.acm.org/doi/10.1145/3486625
Abboud ACensor-Hillel KKhoury SPaz A(2021)Smaller Cuts, Higher Lower BoundsACM Transactions on Algorithms10.1145/346983417:4(1-40)Online publication date: 4-Oct-2021
https://dl.acm.org/doi/10.1145/3469834
Balliu ABrandt SHirvonen JOlivetti DRabie MSuomela J(2021)Lower Bounds for Maximal Matchings and Maximal Independent SetsJournal of the ACM10.1145/346145868:5(1-30)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3461458
Balliu ABrandt SOlivetti DSuomela J(2021)Almost global problems in the LOCAL modelDistributed Computing10.1007/s00446-020-00375-234:4(259-281)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00446-020-00375-2
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

The Locality of Distributed Symmetry Breaking

Locally-Iterative Distributed (Δ+ 1): -Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models

Node and edge averaged complexities of local graph problems

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations