Layering techniques for development of parallel systems: An algebraic approach

A process language is presented which makes a clear distinction between temporal order and causal order. This allows for several algebraic laws that are particularly interesting for the design of concurrent systems. One of these is an algebraic formulation of the communication closed layers principle by [EF82]. These laws suffice to rewrite process terms that avoid specification of temporal ordering into a unique normal form. Other transformations allow for gradually imposing temporal ordering on an already functionally correct design. The combination of such laws enables a design strategy where architecture independent designs are transformed towards a form that matches a particular implementation architecture. We apply this style of design to various distributed algorithms, including an algorithm for the “point-in-polygon” problem transformed to a form suitable for pipelined execution on a tree network, and the Floyd-Warshall algorithm for the all-points shortest path transformed to a form suitable for execution on a SIMD architecture