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