HP Labs Technical Reports

Causal Streams: Tracing Causality in Distributed Systems

Ferrari, Gian-Luigi; Montanari, Ugo; Mowbray, Miranda

HPL-91-150

Keyword(s):

Abstract: When strings of actions are used to describe the behaviour of distributed systems, it is difficult to address some important properties which refer to dependencies, distribution and fairness. Partial orders have been proved to provide a more faithful description of distributed computations. However, the mathematical treatment of partial orders is cumbersome. In this paper, a new algebraic approach to the description of distributed computations is proposed. The category freely generated by a set of atomic actions is introduced. This category is the category with biproducts freely generated by the set. This construction resembles and extends Lawvere's construction of algebraic theories. Indeed, the morphisms of this category form a term algebra, giving an algebraic language for describing computations which keeps information on causal dependencies and distribution.

Back to Index