Randomized Local Network Computing

Laurent Feuilloley, Pierre Fraigniaud.

SPAA 2015: 27th ACM Symposium on Parallelism in Algorithms and Architectures, Portland, Oregon, USA, June 13 - 15, 2015
doi: 10.1145/2755573.2755596, hal: 01247357

Links

Publisher’s version HAL version Slides

Abstract

Extending 
		derandomization from LD to BPLD.

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.

Notes

This paper contains the main part of the work done during my masters'final internship (the other part is basically contained in Brief Announcement: Average Complexity for the LOCAL Model). I gave the talk at SPAA, and at a CNRS related event (ANR Displexity meeting).

As the conference version is self-contained, it is likely that there will be no journal version.

A different derandomization result appears in the celebrated paper An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model by Chang, Kopelowitz and Pettie. It has to be noted that in their paper the algorithm succeeds with high probability, whereas in Naor-Stockmeyer paper and our paper, the success probability is only assumed to be constant.