Some lower bound results for decentralized extrema-finding in rings of processors

摘要

We consider the problem of finding the largest of a set of n uniquely numbered processors, arranged in a ring, by means of an asynchronous distributed algorithm without a central controller. Processors are identical, except for their unique number (identity). Using a technique of Frederickson and Lynch we show that arbitrary algorithms that solve this problem on rings where processors know the ring size cannot have a better worst-case number of messages than algorithms that use only comparisons between identities. We show a similar type of result for rings, where the ring size is not known. We use these results to answer a question, posed by Korach, Rotem, and Santoro in 1981 whether each extrema-finding algorithm that uses time n on a ring of n processors must use a quadratic number of messages; and to show a lower bound of 0.683 n log(n) on the worst-case number of messages for unidirectional rings with known ring size n. Also, we give a lower bound of 12nlog(n) on the average number of messages for algorithms that use only comparisons on rings with known ring size n.