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.