The family of locally checkable problems that can be solved by randomized algorithms in poly(log n) rounds of the LOCAL model of computation on an n node graph.
The same as P-LOCAL, except now the vertices may use randomness in the messages they send and their final output, and must give a valid output with probability at least 1 - 1/n.
Proven in [RG20] that P-LOCAL = P-RLOCAL.
The family of locally checkable problems that can be solved by deterministic algorithms in poly(log n) rounds of the LOCAL model of computation on an n node graph.
In the local model of computation, there is a graph with n vertices, each with its own, unique Θ(log(n)) bit ID. Each vertex starts with the state of knowing only its ID and has unbounded, deterministic, computational ability. At each round, every vertex synchronously sends and receives one unbounded message from each neighbor. At the end of the algorithm, each vertex gives an output satisfying the problem. For instance, the vertices may output a valid coloring.
Proven in [RG20] that P-LOCAL = P-RLOCAL.