**Measuring concurrency in CCS**

**V.C. Galpin**

**In ***Proceedings of the Eighth National Conference for Masters and PhD Students in Computer Science*, UNISA, South Africa, 29-30 June 1993. 80-89.

**Abstract**

This paper will report on research which investigates the application of Charron-Bost's measure of concurrency *m* to the Calculus of Communicating Systems (CCS), a formalism for expressing concurrency. The purpose of a measure of concurrency is to calculate a numerical value that describes the amount of concurrency occurring in a computation or algorithm. The aim of the research was 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 to provide a new tool for understanding concurrency using CCS. The approach taken in the research was to identify the differences between the message-passing formalism in which the measure *m* is defined, and CCS; and to modify the message-passing formalism to enable the mapping of CCS agents to it. A software tool, the Concurrency Measurement Tool, was developed to permit experimentation with chosen CCS agents and hence to allow the evaluation of *m*. The criteria used for evaluation are the intuitive understanding of the measure, being well-behaved for small examples, compatibility with operators, usability and applicability, expense of computation, ability to calculate the measure for a specific event and stability with respect to granularity. The experimentation showed that the measure *m*, although intuitively appealing, is defined by an algebraic expression that is ill-behaved, is not compatible with operators and is expensive to compute. A new measure is defined and it is shown that it matches the evaluation criteria better than *m*, although it is still not ideal. The research has demonstrated that it is feasible to measure concurrency in CCS and that a methodology has been developed for evaluating concurrency measures.

Full text - PDF

Slides - PDF

Back to Publications page