Lower Bounds for Distributed Maximum-Finding Algorithms

Reviewer: Daniel P. Bovet

A set of n nodes are connected by communication channels to form a ring; each of them has a distinct value and can send messages to its immediate neighbor in the clockwise direction (unidirectional ring), or to both immediate neighbors (bidirectional ring). A maximum-finding algorithm is a distributed algorithm to find the node with the highest value in the ring. The performance measure is the total number of messages sent when all nodes in the ring begin execution simultaneously. An application of these algorithms occurs in token ring networks when the control token is lost and all nodes have to select a new emitter for the control token. Efficient O( nlog n) algorithms have been introduced for unidirectional rings with an unknown number of nodes n. The paper establishes four lower bounds, all of the form &OHgr;( nlog n), for distributed maximum-finding algorithms. These bounds refer, respectively, to unidirectional and bidirectional rings with a known and unknown number of nodes. The main result stated in Th. 2.2 is that, for every maximum-finding algorithm A for a unidirectional ring with unknown number of nodes, there exists a corresponding set E( A) of sequences of node values called exhaustive set. Furthermore, the number of messages transmitted by A for a given set of node values s is at least equal to the cardinality of the set: { t e E( A) &vbm0; t is a prefix of a cyclic permutation of s}. The results obtained are rather specialized, but they will be welcomed by those whose research is closely related.