Compositional Systems over Reducible Networks - invited paper

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

Abstrakty

EN

In the paper two notions related to local (distributed) computations are identified and discussed. The first one is the notion of reducible graphs. A graph is reducible if it can be reduced to a singleton by successive removing its removable nodes; the removing procedure should be local in the sense that to decide whether a node is removable or not it is sufficient to inspect its neighborhood. The second is the notion of compositional systems, consisting of a set of objects together with a composition operation which to each pair of local objects (like local votes, partial trees, partial orderings, local consensus, local processes etc.) assigns their possible compositions; a sequence of such composition operations leads to a global object (like a global vote, a full spanning tree, a total ordering, a global consensus, a synchronized process, etc). Combining these two notions gives rise to a generic distributed algorithm for composing different local objects assigned to nodes of a reducible graph into one global object assigned to all nodes. Correctness of the composing algorithm, i.e its proper termination and its impartiality is proved.

Słowa kluczowe

EN

local algorithms; distributed data; computation networks; distributed computing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 79, nr 3-4
• Strony: 265--282
• Opis fizyczny: bibliogr. 12 poz.

Twórcy

autor

Mazurkiewicz A.

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

Bibliografia

• [1] Angluin,D.: Local and global properties in networks of processors, in: Proc. of 12th Symp. on Theory of Computing (1980) 82-93
• [2] Berge, C.: Theorie des graphes et ses applications, Dunod, Paris (1958)
• [3] Courcelle,B., Métivier,Y.: Coverings and Minors: application to local computations in graphs, in: Europ. Journal of Combinatorics 15 (1994) 127-138
• [4] Fisher,M.J., Lynch,N.A., Merritt,A.: Easy impossibility proofs for distributed consensus problems, in: Distributed Computing 1 (1986) 26-29
• [5] Godard,E.:(Ph.D. dissertation) A characterization of families of graphs in which election is possible, in: Proc. of Foundations of Software Sci. and Comp. Structures, LNCS 2303 (2002) 159-171
• [6] Godard,E., Métivier,Y., MuscholL, A.: The power of local computations in graphs with initial knowledge, in: Proc. of Theory and Applications of Graph Transformations'98 1764 LNCS (2000) 71-84
• [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.: Solvability of the asynchronous ranking problem, in: Inf. Processing Letters 28 (1988) 221-224.
• [11] Mazurkiewicz,A.: Compositional Systems over Reducible Graphs, in: CS&P 2006 TR Informatik-Berichte den Humboldt Universitt zu Berlin Gabrielle Lindemann von Trzebiatowski und Holger Schlingloff, eds.), (2006) 1 - 14
• [12] MazurkiewicZ, A.: Local Properties of Triangular Graphs, in: CS&P 2006 TR Informatik-Berichte den Humboldt Universitt zu Berlin Gabrielle Lindemann von Trzebiatowski und Holger Schlingloff, eds.), (2006) 400 -409