FINDING THE EXTREMA OF A DISTRIBUTED MULTISET

We consider the problem of finding the extrema of a distributed multis et in a ring, that is, of determining the minimum and the maximum valu es, x(min) and x(max), of a multiset X = {x(0), x(2),..., x(n-1)} whos e elements are drawn from a totally ordered universe U and stored at t he n entities of a ring network. This problem is unsolvable if the rin g size is not known to the entities, and it has complexity Theta(n(2)) in the case of asynchronous rings of known size. We show that, in syn chronous rings of known size, this problem can always be solved in O(( c + log n). n) bits and O(n . c . x(1/c)) time for any integer c > 0, where x = Max{\x(min)\, \x(max)\}. The previous solutions required O(n (2)) bits and the same amount of time. Based on these results, we also present a bit-optimal solution to the problem of finding the multipli city Of the extrema. (C) 1996 Academic Press, Inc.