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,x_minandx_max, of a multisetX= {x₀,x₂, ...,x_n−1} whose elements are drawn from a totally ordered universeUand stored at thenentities of a ring network. This problem is unsolvable if the ring size is not known to the entities, and it has complexity Θ(n²) in the case of asynchronous rings of known size. We show that, in synchronous rings of known size, this problem can always be solved inO((c+ logn) ·n) bits andO(n·c·x^1/c) time for any integerc> 0, wherex= Max{|x_min|, |x_max|}. The previous solutions requiredO(n²) 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.