CHALOPIN_2007_HAL-00308125_1
Jérémie Chalopin, Yves Métivier. An efficient message passing algorithm based on Mazurkiewicz s algorithm. Fundamenta Informaticae, 80(1):221-246, 2007.
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
{W}e study the election and the naming problems in the asynchronous message passing model. {W}e present a necessary condition based on {A}ngluin's lifting lemma that must be satisfied by any network that admits a naming (or an election) algorithm. {W}e then show that this necessary condition is also sufficient: we present an election and naming algorithm based on {M}azurkiewicz's algo\-rithm. {T}he algorithm we obtained is totally asynchronous and it needs a polynomial number of messages of polynomial size, whereas previous election algorithms in this model are pseudo-synchronous and use messages of exponential size.
Contact
Jérémie Chalopin
Yves Métivier
BibTex Reference
@article{CHALOPIN_2007_HAL-00308125_1,
Author = {Chalopin, Jérémie and Métivier, Yves},
Title = {{A}n efficient message passing algorithm based on {M}azurkiewicz s algorithm},
Journal = {{F}undamenta {I}nformaticae},
Volume = {80},
Number = {1},
Pages = {221--246},
Year = {2007}
}
EndNote Reference [help]
Get EndNote Reference (.ref)