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

article

An optimal bit complexity randomized distributed MIS algorithm

Authors:

N. Saheb-Djahromi,

A. ZemmariAuthors Info & Claims

Distributed Computing, Volume 23, Issue 5-6

Pages 331 - 340

https://doi.org/10.1007/s00446-010-0121-5

Published: 01 April 2011 Publication History

Abstract

We present a randomized distributed maximal independent set (MIS) algorithm for arbitrary graphs of size n that halts in time O(log n) with probability 1 ? o(n?1), and only needs messages containing 1 bit. Thus, its bit complexity par channel is O(log n). We assume that the graph is anonymous: unique identities are not available to distinguish between the processes; we only assume that each vertex distinguishes between its neighbours by locally known channel names. Furthermore we do not assume that the size (or an upper bound on the size) of the graph is known. This algorithm is optimal (modulo a multiplicative constant) for the bit complexity and improves the best previous randomized distributed MIS algorithms (deduced from the randomized PRAM algorithm due to Luby (SIAM J. Comput. 15:1036---1053, 1986)) for general graphs which is O(log2 n) per channel (it halts in time O(log n) and the size of each message is log n). This result is based on a powerful and general technique for converting unrealistic exchanges of messages containing real numbers drawn at random on each vertex of a network into exchanges of bits. Then we consider a natural question: what is the impact of a vertex inclusion in the MIS on distant vertices? We prove that this impact vanishes rapidly as the distance grows for bounded-degree vertices and we provide a counter-example that shows this result does not hold in general. We prove also that these results remain valid for Luby's algorithm presented by Lynch (Distributed algorithms. Morgan Kaufman 1996) and by Wattenhofer (http://dcg.ethz.ch/lectures/fs08/distcomp/lecture/chapter4.pdf, 2007). This question remains open for the variant given by Peleg (Distributed computing--a locality-sensitive approach 2000).

References

[1]

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

Digital Library

[2]

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

Digital Library

[3]

Bodlaender H.L., Moran S., Warmuth M.K.: The distributed bit complexity of the ring: from the anonymous case to the non-anonymous case. Inf. comput. 114(2), 34---50 (1994)

Digital Library

[4]

Chalopin J., Métivier Y.: An efficient message passing election algorithm based on mazurkiewicz's algorithm. Fundam. Inform. 80(1-3), 221---246 (2007)

Digital Library

[5]

Dinitz, Y., Moran, S., Rajsbaum, S.: Bit complexity of breaking and achieving symmetry in chains and rings. J. ACM. 55(1) (2008)

Digital Library

[6]

Ghosh S.: Distributed Systems--An Algorithmic Approach. CRC Press, Boca Raton (2006)

[7]

Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.): Probabilistic Methods for Algorithmic Discrete Mathematics, of Algorithms and Combinatorics, vol. 16. Springer-Verlag, Berlin (1998)

[8]

Karp, R.M., Widgerson, A.: A fast parallel algorithm for the maximal independent set problem. In: Proceedings of the 16th ACM Symposium on Theory of Computing (STOC), pp. 266---272. ACM Press (1984)

Digital Library

[9]

Kothapalli, K., Onus, M., Scheideler, C., Schindelhauer, C.: Distributed coloring in Õ$${\left(\sqrt{\log n}\right)}$$ bit rounds. In: 20th International Parallel and Distributed Processing Symposium (IPDPS 2006), Proceedings April 2006, Rhodes Island, Greece. IEEE pp. 25---29 (2006)

Digital Library

[10]

Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: DISC, pp. 273---287 (2005)

Digital Library

[11]

Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 24 Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 300---309 (2004)

Digital Library

[12]

Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: Proceedings of the 25 Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 7---15. ACM Press (2006)

Digital Library

[13]

Kushilevitz E., Nisan N.: Communication Complexity. Cambridge University Press, Cambridge, MA (1999)

Digital Library

[14]

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

Digital Library

[15]

Luby M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15, 1036---1053 (1986)

Digital Library

[16]

Lynch, N.A.: Distributed Algorithms. Morgan Kaufman (1996)

Digital Library

[17]

Moscibroda T., Wattenhofer R.: Coloring unstructured radio networks. Distrib. Comput. 21(4), 271---284 (2008)

Digital Library

[18]

Naor M., Stockmeyer L.J.: What can be computed locally?. SIAM J. Comput. 24(6), 1259---1277 (1995)

Digital Library

[19]

Peleg, D.: Distributed computing--A Locality-sensitive approach. SIAM Monographs on Discrete Mathematics and Applications (2000)

Digital Library

[20]

Santoro N.: Design and Analysis of Distributed Algorithms. Wiley, London (2007)

Digital Library

[21]

Tel G.: Introduction to Distributed Algorithms. Cambridge University Press, Cambridge, MA (2000)

Digital Library

[22]

Wattenhofer, R.: http://dcg.ethz.ch/lectures/fs08/distcomp/lecture/chapter4.pdf. (2007)

[23]

Yao, A.C.: Some complexity questions related to distributed computing. In: Proceedings of the 11th ACM Symposium on Theory of Computing (STOC), pp. 209---213. ACM Press (1979)

Digital Library

Cited By

Ashkenazi YGelles RLeshem AEmek YCachin C(2020)Brief Announcement: Noisy Beeping NetworksProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405705(458-460)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3405705
Elkin MFiltser ANeiman OEmek YCachin C(2020)Distributed Construction of Light NetworksProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405701(483-492)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3405701
Abboud ACensor-Hillel KKhoury SLenzen C(2020)Fooling views: a new lower bound technique for distributed computations under congestionDistributed Computing10.1007/s00446-020-00373-433:6(545-559)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s00446-020-00373-4
Show More Cited By

An optimal bit complexity randomized distributed MIS algorithm
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis

Recommendations

An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
SIROCCO'09: Proceedings of the 16th international conference on Structural Information and Communication Complexity

We present a randomized distributed maximal independent set (MIS) algorithm for arbitrary graphs of size n that halts in time O(logn) with probability 1−o(n⁻¹), each message containing 1 bit: thus its bit complexity per channel is O(logn) (the bit ...
On the bit communication complexity of randomized rumor spreading
SPAA '10: Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures

We study the communication complexity of rumor spreading in the random phone-call model. Suppose nplayers communicate in parallel rounds, where in each round every player calls a randomly selected communication partner. A player u is allowed to exchange ...
An optimal distributed (Δ+1)-coloring algorithm?
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Δ+1)-list coloring in the randomized LOCAL model running in O(log^∗n + Det_d(poly logn)) time, where Det_d(n′) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Distributed Computing

Distributed Computing Volume 23, Issue 5-6

April 2011

93 pages

ISSN:0178-2770

Issue’s Table of Contents

Copyright © Copyright © 2011 Springer-Verlag.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 2011

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ashkenazi YGelles RLeshem AEmek YCachin C(2020)Brief Announcement: Noisy Beeping NetworksProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405705(458-460)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3405705
Elkin MFiltser ANeiman OEmek YCachin C(2020)Distributed Construction of Light NetworksProceedings of the 39th Symposium on Principles of Distributed Computing10.1145/3382734.3405701(483-492)Online publication date: 31-Jul-2020
https://dl.acm.org/doi/10.1145/3382734.3405701
Abboud ACensor-Hillel KKhoury SLenzen C(2020)Fooling views: a new lower bound technique for distributed computations under congestionDistributed Computing10.1007/s00446-020-00373-433:6(545-559)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s00446-020-00373-4
Augustine JGhaffari MGmyr RHinnenthal KScheideler CKuhn FLi JScheideler CBerenbrink P(2019)Distributed Computation in Node-Capacitated NetworksThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323195(69-79)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323195
Turau V(2019)Making Randomized Algorithms Self-stabilizingStructural Information and Communication Complexity10.1007/978-3-030-24922-9_21(309-324)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-24922-9_21
Métivier YRobson JZemmari A(2016)Randomised distributed MIS and colouring algorithms for rings with oriented edges in O ( log ź n ) bit roundsInformation and Computation10.1016/j.ic.2016.09.006251:C(208-214)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1016/j.ic.2016.09.006
Bury M(2015)Randomized OBDD-Based Graph AlgorithmsPost-Proceedings of the 22nd International Colloquium on Structural Information and Communication Complexity - Volume 943910.1007/978-3-319-25258-2_18(254-269)Online publication date: 14-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-319-25258-2_18
Navlakha SBar-Joseph Z(2014)Distributed information processing in biological and computational systemsCommunications of the ACM10.1145/267828058:1(94-102)Online publication date: 23-Dec-2014
https://dl.acm.org/doi/10.1145/2678280
Scott AJeavons PXu LFatourou PTaubenfeld G(2013)Feedback from natureProceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484247(147-156)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484247
Afek YAlon NBar-Joseph ZCornejo AHaeupler BKuhn F(2013)Beeping a maximal independent setDistributed Computing10.1007/s00446-012-0175-726:4(195-208)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1007/s00446-012-0175-7

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents