Abstract
We consider finite connected undirected graphs as a model for anonymous computer networks. In this framework we show a general purpose distributed election protocol, which uses forward links over the standard communication channels between processors. The forward links are represented in the form of structured labels, so the algorithm is in fact a graph relabelling system. However, its transformations are not local in the classical sense. For this particular algorithm we define a new notion of semi-locality. We claim that semi-local computations are as powerful as global ones, while still conforming to the intuitive meaning of the locality term.
Get full access to this article
View all access options for this article.