A LOWER BOUND ON PROBABILISTIC ALGORITHMS FOR DISTRIBUTIVE RING COLORING

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/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 [Inform. and Control, 70 (1986), pp. 32-53] and extends the lower bound for deterministic algorithms of Linial [Proc. 28th IEEE Foundations of Computer Science Symposium, 1987, pp. 331-335].