Towards parallelization of concurrent systems

摘要

A notion of parallelization of concurrent processes is proposed that satisfies some intuitive requirements. Roughly, given a process P, a more parallel version Q of P can be the result of replacing one of the sequential summands S in one of P subterms by a process R, provided that Q is functionally equivalent to P and R is either a parallel term or a summand of S. this defines an equivalence preserving preorder on processes Q≤P according to which in Q parallelism is increased or the amount of redundancy is decreased. We show that our notion has some connection with the notion of factorization proposed by Milner and Moller. Finally, we identify some classes of processes for which the most parallel version is unique.