Randomized local network computing

Laurent Feuilloley, Pierre Fraigniaud

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

12 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationSPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures
Number of pages10
ISBN (Electronic)9781450335881
Publication statusPublished - 13 Jun 2015
MoE publication typeA4 Article in a conference publication
EventAnnual ACM Symposium on Parallelism in Algorithms and Architectures - Portland, United States
Duration: 13 Jun 201515 Jun 2015
Conference number: 27


ConferenceAnnual ACM Symposium on Parallelism in Algorithms and Architectures
Abbreviated titleSPAA
CountryUnited States

Fingerprint Dive into the research topics of 'Randomized local network computing'. Together they form a unique fingerprint.

Cite this