research-article

Randomized Local Network Computing

Authors:

Laurent Feuilloley,

Pierre FraigniaudAuthors Info & Claims

SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures

Pages 340 - 349

https://doi.org/10.1145/2755573.2755596

Published: 13 June 2015 Publication History

Abstract

In this paper, we carry on investigating the line of research questioning the power of randomization for the design of distributed algorithms. In their seminal paper, Naor and Stockmeyer [STOC 1993] established that, in the context of network computing, in which all nodes execute the same algorithm in parallel, any construction task that can be solved locally by a randomized Monte-Carlo algorithm can also be solved locally by a deterministic algorithm. This result however holds in a specific context. In particular, it holds only for distributed tasks whose solutions can be locally checked by a deterministic algorithm. In this paper, we extend the result of Naor and Stockmeyer to a wider class of tasks. Specifically, we prove that the same derandomization result holds for every task whose solutions can be locally checked using a 2-sided error randomized Monte-Carlo algorithm. This extension finds applications to, e.g., the design of lower bounds for construction tasks which tolerate that some nodes compute incorrect values. In a nutshell, we show that randomization does not help for solving such resilient tasks.

References

[1]

L. M. Adleman: Two Theorems on Random Polynomial Time. In proc. 19th IEEE Symp. on Foundations of Computer Science, pp75--83, 1978.

Digital Library

[2]

H. Arfaoui, P. Fraigniaud: What can be computed without communications? SIGACT News 45(3): 82--104 (2014)

Digital Library

[3]

H. Arfaoui, P. Fraigniaud, D. Ilcinkas, F. Mathieu: Distributedly Testing Cycle-Freeness. In proc. 40th Int. Work. on Graph-Theoretic Concepts in Computer Science (WG), Springer LNCS, pp15--28, 2014.

[4]

L. Barenboim, M. Elkin: Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers, 2013.

Digital Library

[5]

H. T.-H. Chan, M. Dinitz, A. Gupta: Spanners with Slack. In proc. 14th Annual European Symposium on Algorithms (ESA), pp196--207, 2006.

Digital Library

[6]

K.-M. Chung, S. Pettie, H.-H. Su: Distributed algorithms for the Lovász local lemma and graph coloring. In proc. 33rd ACM Symp. on Principles of Distributed Computing (PODC), pp134--143, 2014.

Digital Library

[7]

A. Das Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, R. Wattenhofer: Distributed Verification and Hardness of Distributed Approximation. SIAM J. Comput. 41(5): 1235--1265 (2012)

Digital Library

[8]

M. Dinitz: Compact routing with slack. In proc. 26th ACM Symp. on Principles of Distributed Computing (PODC), pp81--88, 2007.

Digital Library

[9]

Y. Emek, C. Pfister, J. Seidel, R. Wattenhofer: Anonymous networks: randomization $=$ 2-hop coloring. In proc. 33rd ACM Symp. on Principles of Distributed Computing (PODC), pp96--105, 2014.

Digital Library

[10]

P. Floréen, J. Kaasinen, P. Kaski, J. Suomela: An optimal local approximation algorithm for max-min linear programs. In proc. 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pp260--269, 2009.

Digital Library

[11]

P. Fraigniaud, M. Göös, A. Korman, M. Parter, D. Peleg: Randomized distributed decision. Distributed Computing 27(6): 419--434 (2014)

Digital Library

[12]

P. Fraigniaud, M. Göös, A. Korman, J. Suomela: What can be decided locally without identifiers? In proc. 32nd ACM Symp. on Principles of Distributed Computing (PODC) 2013: 157--165

Digital Library

[13]

P. Fraigniaud, A. Korman, D. Peleg: Towards a complexity theory for local distributed computing. J. ACM 60(5): 35 (2013)

Digital Library

[14]

P. Fraigniaud, S. Rajsbaum, C. Travers: Locality and checkability in wait-free computing. Distributed Computing 26(4): 223--242 (2013)

Digital Library

[15]

P. Fraigniaud, S. Rajsbaum, C. Travers: On the Number of Opinions Needed for Fault-Tolerant Run-Time Monitoring in Distributed Systems. In proc. 5th International Conference on Runtime Verification (RV), pp92--107, 2014.

[16]

C. Gavoille, A. Kosowski, M. Markiewicz: What Can Be Observed Locally? In proc. 23rd Int. Symp. on Distributed Computing (DISC), Springer LNCS, pp243--257, 2009.

Digital Library

[17]

M. Göös, J. Hirvonen, J. Suomela: Lower bounds for local approximation. J. ACM 60(5): 39 (2013)

Digital Library

[18]

H. Hasemann, J. Hirvonen, J. Rybicki, J. Suomela: Deterministic Local Algorithms, Unique Identifiers, and Fractional Graph Colouring. In proc. 19th Colloq. on Struct. Information and Comm. Complexity (SIROCCO), Springer LNCS, pp48--60, 2012.

Digital Library

[19]

G. Konjevod, A. W. Richa, D. Xia, H. Yu: Compact routing with slack in low doubling dimension. In proc. 26th ACM Symp. on Principles of Distributed Computing (PODC), pp71--80, 2007.

Digital Library

[20]

A. Korman, Shay Kutten, D. Peleg: Proof labeling schemes. Distributed Computing 22(4): 215--233 (2010)

Digital Library

[21]

A. Korman, J.-S. Sereni, L. Viennot: Toward more localized local algorithms: removing assumptions concerning global knowledge. Distributed Computing 26(5--6): 289--308 (2013)

[22]

F. Kuhn, T. Moscibroda, R. Wattenhofer: What cannot be computed locally! In proc. 23rd ACM Symp. on Principles of Distributed Computing (PODC), pp300--309, 2004.

Digital Library

[23]

C. Lenzen, Y. Anne Oswald, R. Wattenhofer: What can be approximated locally?: case study: dominating sets in planar graphs. In proc. 20th ACM Symp. on Parallelism in Algo. and Arch. (SPAA), pp46--54, 2008.

Digital Library

[24]

C. Lenzen, R. Wattenhofer: Leveraging Linial's Locality Limit. In proc. 22nd Int. Symp. on Distributed Computing (DISC), pp394--407, 2008.

Digital Library

[25]

N. Linial: Locality in Distributed Graph Algorithms. SIAM J. Comput. 21(1): 193--201 (1992)

Digital Library

[26]

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

Digital Library

[27]

M. Naor: A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring. SIAM J. Discrete Math. 4(3): 409--412 (1991)

Digital Library

[28]

M. Naor, L. J. Stockmeyer: What Can be Computed Locally? SIAM J. Comput. 24(6): 1259--1277 (1995)

Digital Library

[29]

D. Peleg: Distributed Computing: A Locality- Sensitive Approach. SIAM, Philadelphia, PA, 2000.

Digital Library

[30]

J. Suomela: Survey of local algorithms. ACM Comput. Surv. 45(2): 24 (2013)

Digital Library

Cited By

Feuilloley LFraigniaud P(2021)Randomized Local Network Computing: Derandomization Beyond Locally Checkable LabelingsACM Transactions on Parallel Computing10.1145/34706408:4(1-25)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3470640
Jahja IYu HHou R(2021)On the Power of Randomization in Distributed Algorithms in Dynamic Networks with Adaptive AdversariesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2021.09.004Online publication date: Oct-2021
https://doi.org/10.1016/j.jpdc.2021.09.004
Censor-Hillel KParter MSchwartzman G(2020)Derandomizing local distributed algorithms under bandwidth restrictionsDistributed Computing10.1007/s00446-020-00376-1Online publication date: 18-Apr-2020
https://doi.org/10.1007/s00446-020-00376-1
Show More Cited By

Index Terms

Randomized Local Network Computing
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Distributed Detection of Cycles
SPAA '17: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures

Distributed property testing in networks has been introduced by Brakerski and Patt-Shamir (2011), with the objective of detecting the presence of large dense sub-networks in a distributed manner. Recently, Censor-Hillel et al. (2016) have shown how to ...
Randomized proof-labeling schemes

Proof-labeling schemes, introduced by Korman et al. (Distrib Comput 22(4):215---233, 2010. https://doi.org/10.1007/s00446-010-0095-3), are a mechanism to certify that a network configuration satisfies a given boolean predicate. Such mechanisms find ...
Randomized Local Network Computing: Derandomization Beyond Locally Checkable Labelings
We carry on investigating the line of research questioning the power of randomization for the design of distributed algorithms. In their seminal paper, Naor and Stockmeyer [STOC 1993] established that, in the context of network computing in which all ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '15: Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures

June 2015

362 pages

ISBN:9781450335881

DOI:10.1145/2755573

General Chair:
Guy Blelloch
Carnegie Mellon University, USA
,
Program Chair:
Kunal Agrawal
Washington University in St. Louis, USA

Copyright © 2015 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: 13 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPAA '15

Sponsor:

SPAA '15: 27th ACM Symposium on Parallelism in Algorithms and Architectures

June 13 - 15, 2015

Oregon, Portland, USA

Acceptance Rates

SPAA '15 Paper Acceptance Rate 31 of 131 submissions, 24%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
204
Total Downloads

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

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Feuilloley LFraigniaud P(2021)Randomized Local Network Computing: Derandomization Beyond Locally Checkable LabelingsACM Transactions on Parallel Computing10.1145/34706408:4(1-25)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3470640
Jahja IYu HHou R(2021)On the Power of Randomization in Distributed Algorithms in Dynamic Networks with Adaptive AdversariesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2021.09.004Online publication date: Oct-2021
https://doi.org/10.1016/j.jpdc.2021.09.004
Censor-Hillel KParter MSchwartzman G(2020)Derandomizing local distributed algorithms under bandwidth restrictionsDistributed Computing10.1007/s00446-020-00376-1Online publication date: 18-Apr-2020
https://doi.org/10.1007/s00446-020-00376-1
Jahja IYu HHou R(2020)On the Power of Randomization in Distributed Algorithms in Dynamic Networks with Adaptive AdversariesEuro-Par 2020: Parallel Processing10.1007/978-3-030-57675-2_24(376-391)Online publication date: 18-Aug-2020
https://doi.org/10.1007/978-3-030-57675-2_24
Fraigniaud POlivetti D(2019)Distributed Detection of CyclesACM Transactions on Parallel Computing10.1145/33228116:3(1-20)Online publication date: 15-Oct-2019
https://dl.acm.org/doi/10.1145/3322811
Arfaoui HFraigniaud PIlcinkas DMathieu FPelc A(2019)Deciding and verifying network properties locally with few output bitsDistributed Computing10.1007/s00446-019-00355-1Online publication date: 13-Jun-2019
https://doi.org/10.1007/s00446-019-00355-1
Fraigniaud POlivetti DScheideler CHajiaghayi M(2017)Distributed Detection of CyclesProceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3087556.3087571(153-162)Online publication date: 24-Jul-2017
https://dl.acm.org/doi/10.1145/3087556.3087571
Fraigniaud PHeinrich MKosowski A(2016)Local Conflict Coloring2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2016.73(625-634)Online publication date: Oct-2016
https://doi.org/10.1109/FOCS.2016.73
Chang YKopelowitz TPettie S(2016)An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2016.72(615-624)Online publication date: Oct-2016
https://doi.org/10.1109/FOCS.2016.72

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