Uniform Election in Trees and Polyominoids

Abstract

International audience

Election is a classical paradigm in distributed algorithms. This paper aims to design and analyze a distributed algorithm choosing a node in a graph which models a network. In case the graph is a tree, a simple schema of algorithm acts as follows: it removes leaves till the graph is reduced to a single vertex: the elected one. In \cite{MSZ03}, the authors studied a randomized variant of this schema which gives the same probability of being elected to each node of the tree. They conjectured that expected election duration of this algorithm is $O(\ln(n))$ where $n$ denotes the size of the tree and asked whether it is possible to use the same algorithm to obtain a fair election in other classes of graphs. In this paper, we prove their conjecture. We then introduce a new structure called polyominoid graphs. We show how a spanning tree for these graphs can be computed locally so that our algorithm, applied to this spanning tree, gives a uniform election algorithm on polyominoids.