Measuring concurrency in CCS

V.C. Galpin

MSc Research Report, Department of Computer Science, University of the Witwatersrand, 1993.


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 - PDF

Back to Publications page