Summary: Suppose that \(n\) processors are arranged in a ring and can communicate only with their immediate neighbors. It is shown that any probabilistic algorithm for 3 coloring the ring must take at least \({1\over 2}\log^*n-2\) rounds, otherwise the probability that all processors are colored legally is less than \(1\over 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 R. Cole and U. Vishkin [Inf. Control 70, 32-53 (1986; Zbl 0612.68044)] and extends the lower bound for deterministic algorithms of N. Linial [Distributive graphs algorithms — global solutions from local data. Proc. 28th IEEE Foundations of Computer Science Symposium, 331-335 (1987)].