There are a couple of randomized parallel algorithms for the maximal independent set problem, e.g. A Simple Parallel Algorithm for the Maximal Independent Set Problem, A fast and simple randomized parallel algorithm for the maximal independent set problem.
These algorithms were the (or one of the) first examples where $k$-wise independent events/random variables are used to derandomize parallel algorithms. One algorithm (which is described here in the chapter "Fast MIS v2") works as follows:
The algorithm operates in synchronous rounds, grouped into phases.
A single phase is as follows:
1) Each node v chooses a random value r(v) from [0,1] and sends it to its
neighbors.
2) If r(v) < r(w) for all neighbors w in N(v), node v enters the MIS and
informs its neighbors.
3) If v or a neighbor of v entered the MIS, v terminates (v and all edges
adjacent to v are removed from the graph), otherwise v enters the next phase.
My question: Is it known that this algorithm also works if the random values are $k$-wise or even pairwise independent?
I didn't find anything in the literature but maybe I just miss something.
