Symmetry breaking in distributed networks

Abstract

Given a ring of n processors it is required to design the processors such that they will be able to choose a leader (a uniquely designated processor) by sending messages along the ring. If the processors are indistinguishable then there exists no deterministic algorithm to solve the problem. To overcome this difficulty, probabilistic algorithms are proposed. The algorithms may run forever but they terminate within finite time on the average. For the synchronous case several algorithms are presented: The simplest requires, on the average, the transmission of no more than 2.442n bits and O(n) time. More sophisticated algorithms trade time for communication complexity. If the processors work asynchronously then on the average O(n log n) bits are transmitted. In the above cases the size of the ring is assumed to be known to all the processors. If the size is not known then finding it may be be done only with high probability: any algorithm may yield incorrect results (with nonzero probability) for some values of n. Another difficulty is that, if we insist on correctness, the processors may not explicity terminate. Rather, the entire ring reaches an inactive state, in which no processor initiates communication. © 1990.