Partiality I: Embedding relation algebras

AbstractParallel processes confront us with both, strict and non-strict situations. As long as no cooperation between processes is supposed to take place, one may consider them separately and need not ask for progress of the other processes. If, however, a composite result is to be delivered, it is important in which way the result is built.We define the concept of partiality to cope with partial availability of arguments and results. To this end, relation algebras are investigated for which, in addition to the identity I, a specific type of an ordering E⊇I is given in order to model increasing degrees of availability. It turns out that functions regulating transfer of partialities in processes are lattice-continuous with respect to such orderings.One may also consider partialities with regard to their “atomic” constituents. We exhibit how relations between the atomic constituents before and after a process step are represented by continuous partiality transfer functions. Our main result is that partiality transfer functions are images of multiplicatively embedding relations on the atomic constituents into a larger relation algebra. The latter will then give room for the theoretically unavoidable external arbiter who decides for strict transitions that all required components are available. In the forthcoming second part of the paper, universal characterisations of parallel products will be given and studied, testing them with regard to correctness rules