An Efficient Message Passing Election Algorithm based on Mazurkiewicz's Algorithm

Issue title: Half a Century of Inspirational Research: Honoring the Scientific Influence of Antoni Mazurkiewicz

Article type: Research Article

Authors: Chalopin, Jérémie | Métivier, Yves

Affiliations: LaBRI Université de Bordeaux, France. E-mail: {chalopin,metivier}@labri.fr

Abstract: We study the election and the naming problems in the asynchronous message passing model. We present a necessary condition based on Angluin's lifting lemma [1] that must be satisfied by any network that admits a naming (or an election) algorithm. We then show that this necessary condition is also sufficient: we present an election and naming algorithm based on Mazurkiewicz's algorithm [17]. The algorithmwe obtained is totally asynchronous and it needs a polynomial number of messages of polynomial size, whereas previous election algorithms in this model are pseudosynchronous and use messages of exponential size.

Keywords: Distributed Algorithm, AsynchronousMessage Passing Model, Anonymous Network, Local Computation, Election, Naming, Covering

Journal: Fundamenta Informaticae, vol. 80, no. 1-3, pp. 221-246, 2007