Symmetry Breaking in Anonymous Networks: Characterizations.

Abstract

We characterize exactly the cases in which it is possible to elect a leader in an anonymous network of processors by a deterministic algorithm, and we show that for every network there is a weak election algorithm (i.e., if election is impossible all processors detect this fact in a distributed way). 1 Introduction We consider the problem of electing a leader in an anonymous network of processors. More precisely our model is that of a directed graph, with vertices corresponding to processors, and arcs to communication links (we freely interchange symmetric digraphs and undirected graphs). We make no assumption on the structure of the network: selfloops and parallel arcs are allowed. In particular, processors are anonymous: they do not have unique identifiers. We consider both synchronous and asynchronous processor activation models, and models with and without "port awareness" (local names for outgoing and/or for incoming arcs). We consider both unidirectional and bidirectional links. ...