Breaking symmetry in synchronous networks. (English) Zbl 0599.68049

VLSI algorithms and architectures, Proc. Aegean Workshop Comput., Loutraki/Greece 1986, Lect. Notes Comput. Sci. 227, 26-33 (1986).
[For the entire collection see Zbl 0587.00021.]
The paper deals with two symmetry breaking problems, i.e. the problems of election of the central node in distributed computing systems, where the identities of nodes are not necessarily equal.
First, a new detailed randomized algorithm for symmetry breaking in a synchronous unidirectional ring is presented. Then it is proved that this algorithm terminates with probability 1 exchanging O(n) bits in O(n) time units on the average (where n is the number of nodes), without any assumption on initiation time.
Second, the symmetry breaking problem is considered in the family C of digraphs and it is shown that under the assumption on simultaneous initiation, symmetry can be broken in a strongly connected digraph G in C in \(O(n^{1/(k+1)}\partial [G])\) time units with O(ke) bits exchanged on the average for any fixed k, where \(k\in <1,\log_ pn)\); \(p\leq n\), k, p positive integers; e is the number of links, \(\partial [G]\) is the length of the shortest cycle in G. Both problems were analysed by several authors, but the algorithms presented here are faster.
Reviewer: W.Molisz


68R10 Graph theory (including graph drawing) in computer science
94C15 Applications of graph theory to circuits and networks


Zbl 0587.00021