Bit complexity of breaking and achieving symmetry in chains and rings (extended abstract)
Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum · 1999
Ye m Dinitz Shlomo Moran Sergio Rajsbaum Abstract We consider a failure-free, asynchronous message passing network, with n processors arranged on a ring or a chain. The processes are identically programmed but have distinct identities, taken from f1; : : : ; Mg. We investigate the communication costs of three well studied tasks: Consensus, Leader, and MaxF ( nding the maximum identity, a restricted version of Leader). We show that in both chain and ring topologies, somewhat surprisingly, the message complexities of all three tasks are the same. Hence, we suggest as a ner measure of complexity the number of bits transmitted, BitC(). We show that in chains, w.r.t. this measure, Consensus is easier than Leader, which is easier than MaxF. More speci cally, 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) = 2 log 2 M O(1). For a chain, BitC(Consensus) = (n), and BitC(MaxF) = (n log M ). When the length is even BitC(Leader) = (n), while if the length is odd BitC(Leader) = (n + log M ).