New lower bound techniques for distributed leader finding and other problems on rings of processors

AbstractSeveral new lower bounds are derived for deterministic and randomized extrema finding and some other problems on asynchronous, non-anonymous rings of processors, where the ring size n is known in advance to the processors. With a new technique, using results from extremal graph theory, an Ω(n log n) lower bounds is obtained for the average number of messages for distributed leader finding, on rings where the processors know the ring size n, and processors take identities from a set I with size as small as cn, for any constant c>1. Formerly, this bound was only known for special values of n, and exponential size of I. Also, improvements are made on the constant factor of the Ω(n log n) bound. An elementary, but powerful result shows that the same bounds hold for randomized algorithms. It is shown the Ω(n log n) lower bounds can be derived for the expected message complexity for computing AND on an input 1n, OR on an input 0n or XOR over all inputs, even when processors have unique identities. This confirms a conjecture of Abrahamson et al. [2]