Suppose that n processors are arranged in a ring and can communicate only with their immediate neighbors. We show that any probabilistic algorithm for 3 coloring the ring must take at least 1 2 log n 2 rounds, otherwise the probability that all processors are colored legally is less than 1 2 . A similar time bound holds for selecting a maximal independent set. The bound is tight (up to a constant factor) in light of the deterministic algorithms of Cole and Vishkin CV] and extends the lower bound for deterministic algorithms of Linial L].
For instance, REF proves this for 3-coloring the ring.
A lower bound on probabilistic algorithms for distributive ring coloring
SIAM J. Discrete Math.
SIAM J. Discrete Math.
Mathematics Computer Science