chalopin:hal-00710328
Jérémie Chalopin, Yves Métivier, Thomas Morsellino. Enumeration and Leader Election in Partially Anonymous and Multi-hop Broadcast Networks. Fundamenta Informaticae, 120(1):1-27, June 2012.
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
{We address the enumeration and the leader election problems over partially anonymous and multi-hop broadcast networks. We consider an asynchronous communication model where each process broadcasts a message and all its neighbours receive this message after arbitrary and unpredictable time. In this paper, we present necessary conditions that must be satisfied by any graph to solve these problems and we show that these conditions are sufficient by providing an enumeration algorithm on the one hand and a leader election algorithm on the other hand. For both problems, we highlight the importance of the initial knowledge. Considering the enumeration problem, each process only knows the size of the graph and, contrary to related works, the number of its neighbouring processes is unknown. Whereas for the election problem, we show that this combination of knowledge is not sufficient. Our algorithm assumes that each process initially knows a map of the network (without knowing its position in this map). From the complexity viewpoint, our algorithms offer polynomial complexities (memory at each process, number and size of exchanged messages).}
Keywords
[ Distributed computing ] [ Multi-hop ] [ Broadcast ] [ Election ] [ Naming ] [ Enumeration ] [ Fibrations ]
Contact
Jérémie Chalopin
Yves Métivier
Thomas Morsellino
BibTex Reference
@article{chalopin:hal-00710328,
Author = {Chalopin, Jérémie and Métivier, Yves and Morsellino, Thomas},
Title = {{Enumeration and Leader Election in Partially Anonymous and Multi-hop Broadcast Networks}},
Journal = {Fundamenta Informaticae},
Volume = {120},
Number = {1},
Pages = {1--27},
Month = {June},
Year = {2012}
}
EndNote Reference [help]
Get EndNote Reference (.ref)