ELHIBAOUI-2010-451114
Abdelaaziz El Hibaoui, John Michael Robson, Nasser Saheb-Djahromi, Akka Zemmari. Uniform Election in Trees and Polyominoids. Discrete Applied Mathematics, (158):981-987, 2010.
Download
Download paper:
Follow the link
Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Abstract
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
Contact
John-Michael Robson
Nasser Saheb-Djahromi
Akka Zemmari
BibTex Reference
@article{ELHIBAOUI-2010-451114,
Author = {El Hibaoui, Abdelaaziz and Robson, John Michael and Saheb-Djahromi, Nasser and Zemmari, Akka},
Title = {Uniform Election in Trees and Polyominoids},
Journal = {Discrete Applied Mathematics},
Number = {158},
Pages = {981--987},
Year = {2010}
}
EndNote Reference [help]
Get EndNote Reference (.ref)