An efficient message passing algorithm based on Mazurkiewicz s algorithm
| Autor: | Chalopin, Jérémie, Métivier, Yves |
|---|---|
| Přispěvatelé: | Métivier, Yves, Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF), Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2007 |
| Předmět: |
[INFO.INFO-OH] Computer Science [cs]/Other [cs.OH]
Computer Science::Computer Science and Game Theory [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] [INFO.INFO-DC] Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] |
| Zdroj: | Fundamenta Informaticae Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2007, 80 (1-3), pp.221-246 Fundamenta Informaticae, 2007, 80 (1-3), pp.221-246 |
| ISSN: | 0169-2968 |
| Popis: | International audience; 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 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 algo\-rithm. The 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|