Jump to : Download | Abstract | Keywords | Contact | BibTex reference | EndNote reference |

chalopin:hal-00695944

Jérémie Chalopin, Emmanuel Godard, Yves Métivier. Election in Partially Anonymous Networks with Arbitrary Knowledge in Message Passing Systems. Distributed Computing, 25(4):297-311, July 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

{This paper attempts to find an answer to an open question of Angluin in her seminal paper (Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th Symposium on Theory of Computing, pp. 82-93 (1980)) about the election problem for families of graphs (Section 4, page 87). More precisely, we characterize families of (labelled) graphs which admit an election algorithm in the message passing model by using the notion of quasi-coverings which captures ''the existence of large enough area of one graph that looks locally like another graph''.}

Keywords

[ Election algorithm for families of graphs ] [ Covering ] [ Quasi-covering ]

Contact

Jérémie Chalopin
Emmanuel Godard
Yves Métivier

BibTex Reference

@article{chalopin:hal-00695944,
   Author = {Chalopin, Jérémie and Godard, Emmanuel and Métivier, Yves},
   Title = {{Election in Partially Anonymous Networks with Arbitrary Knowledge in Message Passing Systems}},
   Journal = {Distributed Computing},
   Volume = {25},
   Number = {4},
   Pages = {297--311},
   Month = {July},
   Year = {2012}
}

EndNote Reference [help]

Get EndNote Reference (.ref)