Technical Report CS0525

Title: The Distribured Bit Complexity of the Ring: From the Anonymous to the Non-Nnonymous Case
Authors: H.L. Bodlaender, S. Moran and M.F. Warmuth
Abstract: The distributed bit complexity of an asynchronous network of processors is a lower bound on the worst case bit complexity of computing any noo-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 O(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 O(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+epsilon), for any positive epsilon.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1988
To the main CS technical reports page

Computer science department, Technion