Measuring concurrency in CCS
V.C. Galpin
MSc Research Report, Department of Computer Science, University of
the Witwatersrand, 1993.
Abstract
This research report investigates the application of Charron-Bost's
measure of concurrency m to Milner's Calculus of Communicating
Systems (CCS). The aim of this is twofold: first to evaluate the
measure m in terms of criteria gathered from the literature; and
second to determine the feasibility of measuring concurrency in CCS and
hence provide a new tool for understanding concurrency using CCS. The
approach taken is to identify the differences between the
message-passing formalism in which the measure m is defined, and CCS;
and to modify this formalism to enable the mapping of CCS agents to it.
A software tool, the Concurrency Measurement Tool, is developed to
permit experimentation with chosen CCS agents. These experiments show
that the measure m, although intuitively appealing, is defined by an
algebraic expression that is ill-behaved. A new measure is defined and
it is shown that it matches the evaluation criteria better than m,
although it is still not ideal. This work demonstrates that it is
feasible to measure concurrency in CCS and that a methodology has been
developed for evaluating concurrency measures.
Full text - gzipped PostScript
Full text - PDF
Back to Publications page