Randomized Local Network Computing

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 that 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.
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01247357
Contributor : Pierre Fraigniaud <>
Submitted on : Monday, December 21, 2015 - 5:47:56 PM
Last modification on : Friday, September 6, 2019 - 10:36:02 PM
Long-term archiving on : Saturday, April 29, 2017 - 11:27:37 PM

File

de-rand-BPLD.pdf
Files produced by the author(s)

Identifiers

Citation

Laurent Feuilloley, Pierre Fraigniaud. Randomized Local Network Computing. 27th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Jun 2015, Portland, United States. pp.340-349, ⟨10.1145/2755573.2755596⟩. ⟨hal-01247357⟩

Share

Metrics

Record views

491

Files downloads

236