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

• Autorzy: Chalopin J. , Métivier Y.
• Języki publikacji: EN

Abstrakty

EN

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 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.

Słowa kluczowe

EN

distributed algorithms; Asynchronous Message Passing Model; Anonymous Network; local computations; election; naming; coverings

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 80, nr 1-3
• Strony: 221--246
• Opis fizyczny: bibliogr. 25 poz., wykr.

Twórcy

autor

Chalopin J.

autor

Métivier Y.

• LaBRI, Universite Bordeaux , 351 cours de la Liberation, F-33405 Talence, France,

Bibliografia

• [1] D. Angluin. Local and global properties in networks of processors. In Proc. of the 12th Symposium on Theory of Computing (STOC 1980), pages 82-93, 1980.
• [2] H. Attiya and J. Welch. Distributed computing: fundamentals, simulations, and advanced topics. John Wiley and Sons, 2004.
• [3] P. Boldi, B. Codenotti, P. Gemmell, S. Shammah, J. Simon, and S. Vigna. Symmetry breaking in anonymous networks: characterizations. In Proc. of the 4th Israeli Symposium on Theory of Computing and Systems (ISTCS 1996), pages 16-26. IEEE Press, 1996.
• [4] H.L. Bodlaender. The classification of coverings of processor networks. Journal of parallel and distributed computing, 6(1):166-182, 1989.
• [5] P. Boldi and S. Vigna. Fibrations of graphs. Discrete Mathematics, 243(1-3):21-66, 2002.
• [6] J. Chalopin, E. Godard, Y. Métivier, and G. Tel. About the termination detection in the asynchronous message passing model. In Proc. of the 33rd Conference on Current Trends in Theory and Practice of Informatics (SOFSEM2007), volume 4362 of Lecture Notes in Computer Science, pages 200-211. Springer-Verlag, 2007.
• [7] J. Chalopin. Local computations on closed unlabelled edges: the election problem and the naming problem. In Proc. of the 31st Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2005), volume 3381 of Lecture Notes in Computer Science, pages 81-90. Springer-Verlag, 2005.
• [8] J. Chalopin and Y. Métivier. Election and local computations on edges. In Proc. of Foundations of Software Science and Computation Structures, 7th International Conference (FOSSACS 2004), volume 2987 of Lecture Notes in Computer Science, pages 90-104. Springer-Verlag, 2004.
• [9] J. Chalopin and Y. Métivier. A bridge between the asynchronous message passing model and local computations in graphs. In Proc. of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005), volume 3618 of Lecture Notes in Computer Science, pages 212-223. Springer-Verlag, 2005.
• [10] J. Chalopin, Y. Métivier, and W. Zielonka. Election, naming and cellular edge local computations. In Proc. of the 2nd International Conference on Graph Transformations (ICGT 2004), volume 3256 of Lecture Notes in Computer Science, pages 242-256. Springer-Verlag, 2004.
• [11] E. Godard and Y. Métivier. A characterization of families of graphs in which election is possible (ext. abstract). In Proc. of Foundations of Software Science and Computation Structures, 5th International Conference (FOSSACS 2002), volume 2303 of Lecture Notes in Computer Science, pages 159-172. Springer-Verlag, 2002.
• [12] E. Godard, Y. Métivier, and A. Muscholl. Characterization of classes of graphs recognizable by local computations. Theory of Computing Systems, 37(2):249-293, 2004.
• [13] J. Hopcroft and J. Ullman. Introduction to automata theory, languages and computation. Addison-Wesley, 1979.
• [14] F.T. Leighton. Finite common coverings of graphs. J. Combin. Theory, Ser. B, 33(3):231-238, 1982.
• [15] G. LeLann. Distributed systems, towards a formal approach. In Information processing 1977, pages 155-160. North-Holland, 1977.
• [16] N. Lynch. Distributed algorithms. Morgan Kaufman, 1996.
• [17] A. Mazurkiewicz. Distributed enumeration. Information Processing Letters, 61(5):233-239, 1997.
• [18] A. Mazurkiewicz. Bilateral ranking negotiations. Fundamenta Informaticae, 60(1-4):1-16, 2004.
• [19] Y. Métivier and G. Tel. Termination detection and universal graph reconstruction. In Proc. of 7th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2000), Proceedings in Informatics, pages 237-251. Carleton Scientific, 2000.
• [20] N. Norris. Universal covers of graphs: isomorphism to depth n − 1 implies isomorphism to all depths. Discrete Applied Math., 56(1):61-74, 1995.
• [21] B. Szymanski, Y. Shy, and N. Prywes. Terminating iterative solutions of simultaneous equations in distributed message passing systems. In Proc. of the 4th Annual ACM Symposium on Principles of Distributed Computing (PODC 1985), pages 287-292. ACM Press, 1985.
• [22] G. Tel. Introduction to distributed algorithms. Cambridge University Press, 2000.
• [23] A. Tanenbaum and M. van Steen. Distributed Systems - Principles and Paradigms. Prentice Hall, 2002.
• [24] M. Yamashita and T. Kameda. Computing on anonymous networks: Part i - characterizing the solvable cases. IEEE Transactions on parallel and distributed systems, 7(1):69-89, 1996.
• [25] M. Yamashita and T. Kameda. Leader election problem on networks in which processor identity numbers are not distinct. IEEE Transactions on parallel and distributed systems, 10(9):878-887, 1999.