If the ring is asynchronous, the number of messages required to solve LE (and, thus, EF) is β°(n ΠΈ log n) [4, 6-8, 14, 15]. For synchronous rings, several solutions have been presented with different bits-time complexities [5, 8-11, 16, 18, 19]. Unlike the asynchronous case, knowledge of the ring size n has an impact on the established upper bounds. When n is known, the best bits-time bound for LE (and, thus, EF) obtained so far is O(c ΠΈ n) bits and O(c ΠΈ n ΠΈ v 1/c ) time [10], where c is an arbitrary positive integer and v Ο MinΝΝx min Ν, Νx max ΝΝ. When n is not known, the best bits-time trade-off is O(n ΠΈ g Οͺ1 (n)) bits and O(v ΠΈ g(g Οͺ1 (n)) time, where g is an arbitrary monotonically superincreasing function and g Οͺ1 is the pseudo-inverse of g [13]. In all these results it is assumed that U Ο Z Ο© (the set of positive integer).
The situation is more complex if the values are not necessarily distinct. In this case, which is also called the anonymous ring case, EF is unsolvable (i.e., no deterministic solution protocol exists) if the ring size n is not known to the entities [2]. Thus, let us assume that n is known.
For asynchonous rings β(n 2 ) messages are required [2], and this bound can be trivially achieved.
In synchronous rings, if U Ο Z Ο© (i.e., the values are positive integers), it is possible to find the minimum value with O(n) bits; furthermore, this can be done with a time sublinear in x min [10]. No similar results exist for maxima finding. Note that to restrict the values to be positive integers is equivalent to assuming (i) the existence of a lower bound on the minimum value and (ii) the knowlege by the entities of such a bound. In this light, the existing results can be rephrased as follows: if U Κ Z has a minimum u min and the minimum is known to the entities, then x min can be found using O(c ΠΈ n) bits and O(c ΠΈ n ΠΈ w 1/c ) time for any integer constant c ΟΎ 0, where w Ο x min or w Ο x min Οͺ u min depending on whether or not (u min ΠΈ x min ) Ο½ 0, respectively. Clearly, if U has a maximum u max which is known to the entities, also maxima finding can be solved with similar bits-time bounds.
It follows that, if U is finite and its minimum and maximum are both known to the entities, EF can be solved in O(n) bits and a time which is sublinear in ΝUΝ. This represents an improvement over the input collection technique of [2] which would require O(n ΠΈ log n) bits and time linear in ΝUΝ. See Table I for a summary. Note that n (the ring size) is a system parameter; on the other hand, the values