Compositional Systems over Reducible Networks

Issue title: Special Issue on Concurrency Specification and Programming (CS&P)

Article type: Research Article

Authors: Mazurkiewicz, Antoni

Affiliations: Institute of Computer Science of PAS Ordona 21, 01-237, Warsaw, Poland. E-mail: amaz@ipipan.waw.pl

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

Keywords: Local algorithms, distributed data, computation networks, distributed computing

Journal: Fundamenta Informaticae, vol. 79, no. 3-4, pp. 265-282, 2007