Bit complexity of breaking and achieving symmetry in chains and rings
Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum · Journal of the ACM · 2008
We consider a failure-free, asynchronous message passing network with n links, where the processors are arranged on a ring or a chain. The processors are identically programmed but have distinct identities, taken from {0, 1,… , M − 1}. We investigate the communication costs of three well studied tasks: Consensus, Leader, and MaxF (finding the maximum identity). We show that in chain and ring topologies, the message complexities of all three tasks are the same. Hence, we study a finer measure of complexity: the number of transmitted bits required to solve a task T , denoted BitC ( T ). We prove several new lower bounds (and some simple upper bounds) that imply the following results: For the two processors case, BitC (Consensus) = 2 and BitC (Leader) = BitC (MaxF) = 2log 2 M ± O (1), where the gap between the lower and upper bounds is almost always 1. For a chain, BitC (Consensus) = Θ( n ), BitC (Leader) = Θ( n + log M ), and BitC (MaxF) = Θ( n log M ). For the ring topology, we prove the lower bound of Ω( n log M ) for Leader, and (hence) MaxF. We consider also a chain where the intermediate processors have no identities. We prove that BitC (Leader) = Θ( n log M ), which is equal to n times the bit complexity of the problem for two processors. For the specific case when the chain length is even, we prove that BitC (Leader) = Θ( n ), for both above settings. In addition, we show that for any algorithm solving MaxF, there exists an input, for which every execution has the bit complexity Ω( n log M ) (this is not the case for Leader). In our proofs, we use both methods of distributed computing and of communication complexity theory, establishing new links between the two areas.