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

Consider the ring of n processors each of which has been assigned a unique identification number. We now want to find out the maximum of those identification numbers with the help of a single, distributed algorithm running asynchronously on every processor. The paper first gives a sound mathematical formulation of the problem, of which several different variants are possible, e.g.: The maximum must be calculated and broadcast to every processor in the ring or only the processor with the maximum must know that his id-number is the maximum, the ring supports unidirectional or bidirectional communication, or the processors know or do not know the size of the ring. For most variants of the problem algorithms have been developed. The authors give a review on the lower bounds of necessary message exchanges that hold for arbitrary algorithms for a specific variant of the problem. They show, that algorithms that know the size of the ring cannot have a better worst-case performance than those not employing this knowledge. They analyze a question posed in 1981 whether an algorithm using time n on a ring of n processors must use a quadratic number of messages and show that the answer may be yes or no depending on the specific variant of the problem. The paper gives a complete review of existing results, detailed proofs and a long list of references.