The Distributed Bit Complexity of the Ring: From the Anonymous to the Non-anonymous Case

The distributed bit complexity of an asynchronous network of processors is a lower bound on the worst case bit complexity of computing any non-constant function of the inputs to the processors [MW]. This concept attempts to capture the amount of communication required for any useful computation on the network.
The aim of this kind of research is to characterize networks by their bit complexity. In [MW] Moran and Warmuth studied the bit complexity of a ring of n processors under the assumption that all the processors in the ring are identical (anonymous [ASW]), i.e. all processors run the same program and the only parameter to the program is the input of the processor. It was shown that for anonymous rings it takes Ω(nlogn) bits to compute any non-constant function. We would like to release the assumption that the processors are anonymous by allowing each of the processors to have a distinct identity (which becomes a second parameter to the program). If the set of possible identities grows double exponentially in n, then by a simple reduction to the anonymous case one can show that the lower bound holds as well [MW].
In this paper we show that the Ω(nlogn) bit lower bound for computing any non-constant function holds even if the set of possible identities is very small, that is, n^1+ɛ, for any positive ε.