Compositional Systems over Reducible Networks

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.