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 - gzipped PostScript
Full text - PDF
Slides - gzipped PostScript
Slides - PDF
Back to Publications page