Finding the extrema of a distributed multiset

We consider the problem of finding the extrema of a distributed multiset in a ring; that is, of determining the minimum and the maximum values, xmin and xmax, of a multiset X={x0, x2, …, xn-1}, whose elements are drawn from a totally ordered universe U and stored at the n entities of a ring network. This problem is unsolvable if the ring size is not known to the entities, and has complexity θ(n2) in the case of asynchronous rings of known size. We show that, in synchronous rings of known size, this problem can always be solved in O((c+ log n) · n) bits and O(n · c · x1/c) time for any integer c> 0, where x=Max{¦xmin¦, ¦xmax¦}. The previous solutions required O(n2) bits and the same amount of time. Based on these results, we also present a bit optimal solution to the problem of finding the multiplicity of the extrema