Local Computations in Graphs: The Case of Cellular Edge Local Computations

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

Abstrakty

EN

We examine the power and limitations of the weakest vertex relabelling system which allows to change a label of a vertex in function of its own label and of the label of one of its neighbours. We characterize the graphs for which two important distributed algorithmic problems are solvable in this model : naming and election.

Słowa kluczowe

EN

distributed computing; local computations; election; naming; submersion

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 1
• Strony: 85--114
• Opis fizyczny: bibliogr. 20 poz.

Twórcy

autor

Chalopin J.

autor

Métivier Y.

autor

Zielonka W.

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

Bibliografia

• [1] Angluin, D.: Local and global properties in networks of processors, Proceedings of the I2th S\mposium on Theory ofComputing, 1980.
• [2] Attiya, H., Welch, J.: Distńbuted computing: fundamenlals, simulalions. and adwmced topics, McGraw-Hill, 1998.
• [3] Boldi, R, Codenotti, B., Gemmell, R, Shammah, S., Simon, J., Vigna, S.: Symmetry breaking in anonymous networks: Characterization s, P mc. 4th Israeli Symposium on Theory of Computing and Systems, IEEE Press. 1996.
• [4] Chalopin, J.: Election and local computations on closed unlabelled edges (exlended abstract), Proc.ofSOF-SEM2005,number 3381 in LNCS,2005.
• [5] Chalopin, J., Metivier, Y.: Election and local computations on edges (ext. abstract). Proc. of Foundations of Software Science and Computation Structures, FOSSACS'04, number 2987 in LNCS, 2004.
• [6] Chalopin, J., Metivier, Y.: A bridge between the asynchronous message passing model and local computations in graphs (ex!, abstract), Proc. of Mathematical Foundations of Computer Science, MFCS'05, number 3618 in LNCS, 2005.
• [7] Chalopin, J., Metivier, Y, Zielonka, W.: Election, naming and cellular edge local computations (ext. abstract), Proc. of International conference on graph Iransformation, ICGT'04, number 3256 in LNCS, 2004.
• [8] Fiala, J., Paulusma, D.: A complete complexity classification ofthe role assignement problem. Theoretical computer science, to appear.
• [9] Fiala, J., Paulusma, D., Telle, J. A.: Matrix and graph orders derived from locally constrained graph homo-morphisms, Proc. of Mathematical Foundations of Computer Science. MFCS'05, number 3618 in LNCS. 2005.
• [10] Godard, E., Metivier, Y, Muscholl, A.: Characterization of classes of graphs recognizable by local computations, Theory of Computing Systems, 37(2), 2004, 249-293.
• [l1] Godard, E., Metivier, Y, Tel, G.: Election, termination and graph cartography, in preparation.
• [12] Godard, E., Metivier, Y: A characterization of families of graphs in which election is possible (ext. abstract}. Proc. of Foundations of Software Science and Computation Structures, FOSSACS'02, number 2303 in LNCS. Springer-Verlag,2002.
• [13] LeLann, G.: Distributed systems: Towards a formal approach, Informationprocessing'77(B. Gilchrist, Ed.), North-Holland, 1977
• [14] Lynch, N. A.: Distributed algorithms, Morgan Kaufman, 1996.
• [15] Mazurkiewicz, A.: Distributed enumeration, Inf. Processing Letters, 61(5), 1997, 233-239.
• [16] Mazurkiewicz, A.: Bilateral ranking negotiations, Fundamenta Informaticae, 60, 2004, 1-16.
• [17] Szymanski, B., Sny, Y., Prywes, N.: Terminating iterative solutions of simultaneous equations in distributed message passing systems. Proc. ofthe 4th Symposium on Principles of Distributed Computing, PODC'85, 1985.
• [18] Tel, G.: Intmduction to distributed algorithms, Cambridge University Press, 2000.
• [19] 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.
• [20] Yamashita, M., Kameda, T.: Leader election problem on networks in which processor identity numbers arę notdistinct, IEEE Transactions on parallel and distribut systems, 10(9), 1999, 878-887.