Randomized Local Network Computing: Derandomization Beyond Locally Checkable Labelings

Laurent Feuilloley, Pierre Fraigniaud.

ACM Transactions on Parallel Computing
doi:10.1145/3470640

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 only for distributed tasks such that the correctness of their 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 such that the correctness of their solutions can be locally checked using a 2-sided error randomized Monte-Carlo algorithm.

This paper originates from my masters' thesis. The conference version appeared at SPAA 2015. We decided to write a journal version when we realized there was an error in a proof (that wouldn't change the theorems), and that we could have a cleaner writing.

I gave the talk at SPAA (in Portland), and at some other events (ANR Displexity meeting).

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.