TY - JOUR

T1 - The Distributed Bit Complexity of the Ring

T2 - From the Anonymous to the Non-anonymous Case

AU - Bodlaender, H. L.

AU - Moran, S.

AU - Warmuth, M. K.

PY - 1994/1/1

Y1 - 1994/1/1

N2 - In Moran and Warmuth (1993, SIAM .J. Comput.22, No. 2, 379-399), it was shown that computing any non-constant function on a ring of n of processors requires Ω(n log) bits and this bound is tight. This model assumed that all the processors in the ring are identical (anonymous), i.e., all processors run the same program and the only parameter of the program is the input to the processor. In a relaxed model the anonymity is broken by providing each processor with a distinct identity which becomes a second parameter of the program that is executed by all processors. If the set of possible identities grows doubly exponentially in n, then by a reduction to the anonymous case one can show that the lower bound holds as well. In this paper we show that the lower bound of Ω(n log n) bits for computing any non-constant function holds even if the set of possible identities is "very small," that is, of sizer n1 + ε{lunate}, for any positive ε{lunate}.

AB - In Moran and Warmuth (1993, SIAM .J. Comput.22, No. 2, 379-399), it was shown that computing any non-constant function on a ring of n of processors requires Ω(n log) bits and this bound is tight. This model assumed that all the processors in the ring are identical (anonymous), i.e., all processors run the same program and the only parameter of the program is the input to the processor. In a relaxed model the anonymity is broken by providing each processor with a distinct identity which becomes a second parameter of the program that is executed by all processors. If the set of possible identities grows doubly exponentially in n, then by a reduction to the anonymous case one can show that the lower bound holds as well. In this paper we show that the lower bound of Ω(n log n) bits for computing any non-constant function holds even if the set of possible identities is "very small," that is, of sizer n1 + ε{lunate}, for any positive ε{lunate}.

UR - http://www.scopus.com/inward/record.url?scp=0037825182&partnerID=8YFLogxK

U2 - 10.1006/inco.1994.1002

DO - 10.1006/inco.1994.1002

M3 - Article

AN - SCOPUS:0037825182

SN - 0890-5401

VL - 108

SP - 34

EP - 50

JO - Information and Computation

JF - Information and Computation

IS - 1

ER -