Local Computations on Triangular Graphs

• Autorzy: Mazurkiewicz A.
• Języki publikacji: EN

Abstrakty

EN

The paper deals with the class of finite triangular graphs. It turns out that this class enjoys regular properties similar to those of trees and complete graphs. The main objective of the paper is to lift algorithms for some typical local computations, known for other classes of graphs, to the class of triangular graphs. Local algorithms on graphs, according to [8, 9], are defined as local rules for relabeling graph nodes. Rules are local, if they are defined only for a class of subgraphs of processed graph (as neighborhoods of nodes or edges) and neither their results nor their applicability do not depend upon the knowledge of the whole graph labeling. While designing local algorithm for triangular graphs one needs to use some intrinsic properties of such graphs; it puts some additional light on their inherent structure. To illustrate essential features of local computations on triangular graphs, local algorithms for three typical issues of local computations are discussed: leader election, spanning tree construction, and nodes ordering. Correctness of these algorithms, as deadlock freeness, proper termination, and impartiality, are proved.The paper deals with the class of finite triangular graphs. It turns out that this class enjoys regular properties similar to those of trees and complete graphs. The main objective of the paper is to lift algorithms for some typical local computations, known for other classes of graphs, to the class of triangular graphs. Local algorithms on graphs, according to [8, 9], are defined as local rules for relabeling graph nodes. Rules are local, if they are defined only for a class of subgraphs of processed graph (as neighborhoods of nodes or edges) and neither their results nor their applicability do not depend upon the knowledge of the whole graph labeling. While designing local algorithm for triangular graphs one needs to use some intrinsic properties of such graphs; it puts some additional light on their inherent structure. To illustrate essential features of local computations on triangular graphs, local algorithms for three typical issues of local computations are discussed: leader election, spanning tree construction, and nodes ordering. Correctness of these algorithms, as deadlock freeness, proper termination, and impartiality, are proved.

Słowa kluczowe

EN

local algorithms; triangular graphs; leader elections; spanning trees; nodes orderings

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 100, nr 1/4
• Strony: 117--140
• Opis fizyczny: Bibliogr. 12 poz., tab.

Twórcy

autor

Mazurkiewicz A.

• Institute of Computer Science of PAS, Ordona 21, 01-237, Warsaw, Poland,

Bibliografia

• [1] ANGLUIN, D.: Local and global properties of networks of processors, Proceedings of the 12th ACM Symposium on Theory of Computing (1980) 103-112
• [2] BERGE, C.: Theorie des graphes et ses applications, Dunod, Paris (1958)
• [3] CHALOPIN, J.: Election and Local Computations on Closed Unlabelled Edges, SOFSEM 2005 Proc., Lecture Notes in Computer Science3381 (2005) 81-90
• [4] CHALOPIN, J., MÉTIVIER, Y.: Election and Local Computations on Edges FOSSAC 2004 Proc., Lecture Notes in Computer Science2987 (2004) 90-104
• [5] CHALOPIN, J., MĚTIVIER, Y., AND ZIELONKA, W.: Local computations in graphs: the case of cellular edge local computations. Fundamenta Informaticae 74(1) (2006) 85-114
• [6] FISHER,M.J., LYNCH,N.A., MERRITT,A.: Easy impossibility proofs for distributed consensus problems, in: Distributed Computing 1 (1986) 26-29
• [7] LE LANN,G.: Distributed systems - towards a formal approach, in: Information Processing 77 (IFIP), Gilchrist B., (editor), North-Holland (Amsterdam), (1977) 155-160.
• [8] LITOVSKY,I., MÉTIVIER,Y., SOPENA,E.: Graph relabelling systems and distributed algorithms, in: H.Ehrig, H.-J.Kreowski, U.Montanari, and G.Rozenberg (eds) Handbook of graph grammars and computing by graph transformation 3, World Scientific (1999) 1- 56
• [9] LITOVSKY,I., MÉTIVIER,Y., ZIELONKA,W.: On the recognition of families of graphs with local computations, in: Information & Computation 118 (1995) 110-119
• [10] MAZURKIEWICZ, A.:Locally Derivable Graphs, in: Fundamenta Informaticae 75 (2007) 335-355
• [11] YAMASHITA,M., KAMEDA,T.: Computing on anonymous networks: Part I - Characterizing the solvable cases in: IEEE Transactions on parallel and distributed systems 7 (1996) 69-89
• [12] YAMASHITA,M., KAMEDA,T.: Computing on anonymous networks: Part II - Decision and membership problems in: IEEE Transactions on parallel and distributed systems 7 (1996) 90-96