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

article

Distributed computing with advice: information sensitivity of graph coloring

Authors:

Pierre Fraigniaud,

Cyril Gavoille,

David Ilcinkas,

Andrzej PelcAuthors Info & Claims

Distributed Computing, Volume 21, Issue 6

Pages 395 - 403

https://doi.org/10.1007/s00446-008-0076-y

Published: 01 March 2009 Publication History

Abstract

We study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations. The required size of the advice enables to measure the information sensitivity of a network problem. A problem is information sensitive if little advice is enough to solve the problem rapidly (i.e., much faster than in the absence of any advice), whereas it is information insensitive if it requires giving a lot of information to the nodes in order to ensure fast computation of the solution. In this paper, we study the information sensitivity of distributed graph coloring.

References

[1]

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

Digital Library

[2]

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

Digital Library

[3]

Bellare M., Goldreich O., Sudan M.: Free bits, PCPs, and nonapproximability--towards tight results. SIAM J. Comput. 27(3), 804---915 (1998)

Digital Library

[4]

Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. In: 32nd Int. Colloquium on Automata, Languages and Programming (ICALP), LNCS 3580, pp. 335---346 (2005)

Digital Library

[5]

Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Labeling schemes for tree representation. In: 7th Int. Workshop on Distributed Computing (IWDC), LNCS 3741, pp. 13---24 (2005)

Digital Library

[6]

Cole, R., Vishkin, U.: Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In: 18th ACM Symp. on Theory of Computing (STOC), pp. 206---219 (1986)

Digital Library

[7]

Feige U., Kilian J.: Zero knowledge and the chromatic number. J. Comput. Syst. Sci. 57(2), 187---199 (1998)

Digital Library

[8]

Fich F., Ruppert E.: Hundreds of impossibility results for distributed computing. Distrib. Comput. 16, 121---163 (2003)

Digital Library

[9]

Fraigniaud, P., Ilcinkas, D., Pelc, A.: Oracle size: a new measure of difficulty for communication tasks. In: 25th ACM Symp. on Principles of Distributed Computing (PODC), pp. 179---187 (2006)

Digital Library

[10]

Fraigniaud, P., Ilcinkas, D., Pelc, A.: Tree exploration with an oracle. In: 31st Int. Symp. on Mathematical Foundations of Computer Science (MFCS), LNCS 4162, Springer, pp. 24---37 (2006)

Digital Library

[11]

Fraigniaud, P., Korman, A., Lebhar, E.: Local MST computation with short advice. In: 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2007)

Digital Library

[12]

Goldberg, A., Plotkin, S.: Efficient parallel algorithms for (Δ + 1)-coloring and maximal independent set problems. In: 19th ACM Symp. on Theory of Computing (STOC), pp. 315---324 (1987)

[13]

Goldberg, A., Plotkin, S., Shannon, G.: Parallel symmetry-breaking in sparse graphs. In: 19th ACM Symp. on Theory of Computing (STOC), pp. 315---324 (1987)

Digital Library

[14]

Karp, R.: Reducibility Among Combinatorial Problems. In: Complexity of Computer Computations, pp. 85---103 (1972)

[15]

Kothapalli, K., Onus, M., Scheideler, C., Schindelhauer, C.: Distributed coloring in $${O(\sqrt{\log n})}$$ bit rounds. In: 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS) (2006)

Digital Library

[16]

Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed Locally! In: 23th ACM Symp. on Principles of Distributed Computing, (PODC), pp. 300---309 (2004)

Digital Library

[17]

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

Digital Library

[18]

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

Digital Library

[19]

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

Digital Library

[20]

Lynch, N.: A hundred impossibility proofs for distributed computing. In: 8th ACM Symp. on Principles of Distributed Computing (PODC), pp. 1---28 (1989)

Digital Library

[21]

Moscibroda, T., Wattenhofer, R.: Coloring unstructured radio networks. In: 17th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pp. 39---48 (2005)

Digital Library

[22]

Naor M.: A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discrete Math. 4(3), 409---412 (1991)

Digital Library

[23]

Naor, M., Stockmeyer, L.: What can be computed locally? In: 25th ACM Symposium on Theory of Computing (STOC), pp. 184---193 (1993)

Digital Library

[24]

Nisse, N., Soguet, D.: Graph searching with advice. In: 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO), June 2007

Digital Library

[25]

Panconesi A., Rizzi R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14, 97---100 (2001)

Digital Library

[26]

Panconesi, A., Srinivasan, A.: Improved distributed algorithms for coloring and network decomposition problems. In: 24th ACM Symp. on Theory of Computing (STOC), pp. 581---592 (1992)

Digital Library

[27]

Panconesi A., Srinivasan A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 356---374 (1996)

Digital Library

[28]

Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM Monographs on Discrete Mathematics and applications. Philadelphia, PA (2000)

Digital Library

Cited By

Balliu ABrandt SKuhn FNowicki KOlivetti DRotenberg ESuomela JKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Local Advice and Local DecompressionProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662805(117-120)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662805
Gorain B Miller APelc A(2023)Four shades of deterministic leader election in anonymous networksDistributed Computing10.1007/s00446-023-00451-336:4(419-449)Online publication date: 31-May-2023
https://dl.acm.org/doi/10.1007/s00446-023-00451-3
Bhattacharya AGorain BMandal P(2023)Pebble Guided Treasure Hunt in PlaneNetworked Systems10.1007/978-3-031-37765-5_11(141-156)Online publication date: 22-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-37765-5_11
Show More Cited By

Recommendations

Distributed computing with advice: information sensitivity of graph coloring
ICALP'07: Proceedings of the 34th international conference on Automata, Languages and Programming

We study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations. The required size of the advice enables to measure the information sensitivity of a network ...
Ore-type versions of Brooks' theorem

The Ore-degree of an edge xy in a graph G is the sum @q(xy)=d(x)+d(y) of the degrees of its ends. In this paper we discuss colorings and equitable colorings of graphs with bounded maximum Ore-degree, @q(G)=max"x"y"@?"E"("G")@q(xy). We prove a Brooks-...
List-coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Distributed Computing

Distributed Computing Volume 21, Issue 6

March 2009

68 pages

ISSN:0178-2770

Issue’s Table of Contents

Copyright © Copyright © 2009 Springer-Verlag.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 March 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Balliu ABrandt SKuhn FNowicki KOlivetti DRotenberg ESuomela JKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Local Advice and Local DecompressionProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662805(117-120)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662805
Gorain B Miller APelc A(2023)Four shades of deterministic leader election in anonymous networksDistributed Computing10.1007/s00446-023-00451-336:4(419-449)Online publication date: 31-May-2023
https://dl.acm.org/doi/10.1007/s00446-023-00451-3
Bhattacharya AGorain BMandal P(2023)Pebble Guided Treasure Hunt in PlaneNetworked Systems10.1007/978-3-031-37765-5_11(141-156)Online publication date: 22-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-37765-5_11
Dhar AGorain BMondal KPatra SSingh R(2022)Edge exploration of anonymous graph by mobile agent with external helpComputing10.1007/s00607-022-01136-8105:2(483-506)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1007/s00607-022-01136-8
Bouchard SDieudonné YLamani A(2022)Byzantine gathering in polynomial timeDistributed Computing10.1007/s00446-022-00419-935:3(235-263)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s00446-022-00419-9
Ellen FGorain BMiller APelc A(2021)Constant-Length Labeling Schemes for Deterministic Radio BroadcastACM Transactions on Parallel Computing10.1145/34706338:3(1-17)Online publication date: 20-Sep-2021
https://dl.acm.org/doi/10.1145/3470633
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
Gorain BMiller APelc AAgrawal KAzar Y(2021)Four Shades of Deterministic Leader Election in Anonymous NetworksProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461794(265-274)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461794
Ellen FGorain BMiller APelc AScheideler CBerenbrink P(2019)Constant-Length Labeling Schemes for Deterministic Radio BroadcastThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323194(171-178)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323194
Dieudonné YPelc A(2019)Impact of Knowledge on Election Time in Anonymous NetworksAlgorithmica10.1007/s00453-018-0444-381:1(238-288)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s00453-018-0444-3
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents