Enumeration and Leader Election in Partially Anonymous and Multi-hop Broadcast Networks

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

Abstrakty

EN

We address the enumeration and the leader election problems over partially anonymous and multi-hop broadcast networks. We consider an asynchronous communication model where each process broadcasts a message and all its neighbours receive this message after arbitrary and unpredictable time. In this paper, we present necessary conditions that must be satisfied by any graph to solve these problems and we show that these conditions are sufficient by providing an enumeration algorithm on the one hand and a leader election algorithm on the other hand. For both problems, we highlight the importance of the initial knowledge. Considering the enumeration problem, each process only knows the size of the graph and, contrary to related works, the number of its neighbouring processes is unknown. Whereas for the election problem, we show that this combination of knowledge is not sufficient. Our algorithm assumes that each process initially knows a map of the network (without knowing its position in this map). From the complexity viewpoint, our algorithms offer polynomial complexities (memory at each process, number and size of exchanged messages).

Słowa kluczowe

EN

distributed computing; multi-hop; broadcast; election; naming; enumeration; fibrations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 120, nr 1
• Strony: 1--27
• Opis fizyczny: Bibliogr. 25 poz., rys.

Twórcy

autor

Chalopin J.

autor

Métivier Y.

autor

Morsellino T.

• Université de Bordeaux, LaBRI, UMR CNRS 5800, 351, cours de la Libération, 33405 Talence, France,

Bibliografia

• [1] Angluin, D.: Local and global properties in networks of processors, Proc. of the 12th Symposium on Theory of Computing (STOC 1980), 1980, 82-93.
• [2] Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols, Distributed Computing, 20(4), November 2007, 279-304.
• [3] Bang-Jensen, J., Gutin, G.: Digraphs - Theory, Algorithms and Applications, Springer, 2002, ISBN 978-1-85233-611-0.
• [4] Bodlaender, H.: The classification of coverings of processor networks, Journal of parallel and distributed computing, 6(1), 1989, 166-182.
• [5] Boldi, P., Codenotti, B., Gemmell, P., Shammah, S., Simon, J., Vigna, S.: Symmetry breaking in anonymous networks: characterizations, Proc. of the 4th Israeli Symposium on Theory of Computing and Systems (ISTCS 1996), IEEE Press, 1996, 16-26.
• [6] Boldi, P., Vigna, S.: Fibrations of graphs, Discrete Mathematics, 243(1-3), 2002, 21-66.
• [7] Chalopin, J., Métivier, Y.: An Efficient Message Passing Election Algorithm based on Mazurkiewicz's Algorithm, Fundamenta Informaticae, 80(1-3), 2007, 221-246.
• [8] Chalopin, J., Métivier, Y.: On the power of synchronization between two adjacent processes, Distributed Computing, 23(3), 2010, 177-196.
• [9] Chalopin, J., Métivier, Y., Zielonka, W.: Local computations in graphs: the case of cellular edge local computations, Fundamenta Informaticae, 74(1), 2006, 85-114.
• [10] Chlebus, B.: Randomized Communication in Radio Networks, in: Handbook of Randomized Computing (P. Pardalos, S. Rajasekaran, J. Reif, J. Rolim, Eds.), vol. I, Kluwer Academic Publishers, 2001, 401-456,.
• [11] Cidon, I., Mokryn, O.: Propagation and Leader Election in a Multihop Broadcast Environment, DISC, 1998, 104-118.
• [12] Godard, E., Métivier, Y., Muscholl, A.: Characterization of classes of graphs recognizable by local computations, Theory of Computing Systems, 37(2), 2004, 249-293.
• [13] Guerraoui, R., Ruppert, E.: What Can Be Implemented Anonymously?, DISC, 2005, 244-259.
• [14] Helary, J.-M., Raynal, M.: Assigning distinct identities to sites on an anonymous distributed system, Distributed Computing Systems in the 1990s, 1988. Proceedings., Workshop on the Future Trends of, sep 1988, 82 -86.
• [15] LeLann, G.: Distributed systems, towards a formal approach, Information processing 1977, North-Holland, 1977, 155-160.
• [16] Massey, W.: A basic course in algebraic topology, Springer-Verlag, 1991, Graduate texts in mathematics.
• [17] Mazurkiewicz, A.: Distributed enumeration, Information Processing Letters, 61(5), 1997, 233-239.
• [18] Santoro, N.: Design and Analysis of Distributed Algorithms (Wiley Series on Parallel and Distributed Computing), Wiley-Interscience, 2006, ISBN 0471719978.
• [19] Stojmenovic, I.: Handbook of Sensor Networks : Algorithms and Architectures, Wiley, 2005.
• [20] Szymanski, B., Shy, Y., Prywes, N.: Terminating iterative solutions of simultaneous equations in distributed message passing systems, Proc. of the 4th Annual ACM Symposium on Principles of Distributed Computing (PODC 1985), ACM Press, 1985, 287-292.
• [21] Tanenbaum, A., van Steen, M.: Distributed Systems - Principles and Paradigms, Prentice Hall, 2002.
• [22] Tel, G.: Introduction to distributed algorithms, Cambridge University Press, 2000.
• [23] Yamashita, M., Kameda, T.: Computing on anonymous networks: Part I - Characterizing the solvable cases, IEEE Transactions on parallel and distributed systems, 7(1), 1996, 69-89.
• [24] Yamashita, M., Kameda, T.: Computing on anonymous networks: Part II - decision and membership problems, IEEE Transactions on parallel and distributed systems, 7(1), 1996, 90-96.
• [25] Yamashita, M., Kameda, T.: Leader election problem on networks in which processor identity numbers are not distinct, IEEE Transactions on parallel and distributed systems, 10(9), 1999, 878-887.