Consider a computer network consisting of n computers connected in a ring by bidirectional communication channels. The message transmission takes unknown time, but messages do not overtake each other. The computers are anonymous, that is, they do not have unique identities. To be able to discuss them individually we number them 1,...,n. Let x be any string in {0, 1}n. At the start of the computation every computer i in the ring owns a copy of x and a bit yi.

Define y ≡ x if there is an s (0 ≤ s

Each computer executes the same algorithm to compute fx and eventually outputs the value fx(y). Show that there is an algorithm to compute fx(·), with C(x) ≥ n − O(log n), on an anonymous ring of n computers using O(n log n) bit exchanges for a fraction of at least 1 − 1/n of all 2n inputs, and hence Θ(n log n) bit exchanges on average.

Comments. S. Moran and M. Warmuth [SIAM J. Comput., 22:2(1993), 379–399] have shown that to compute nonconstant functions

f, the computers need to exchange Ω(n log n) bits, and that this bound is tight.

This creates a gap with the case of computing constant f requiring zero messages. Source: [E. Kranakis, D. Krizanc, and F.L. Luccio, pp.

392–401 in: Proc. 13th Symp. Math. Found. Comput. Sci., Lect. Notes Comput. Sci., Vol. 969, Springer-Verlag, 1995].