CCS: It’s not fair!

Rob J. van Glabbeek, Peter Höfner

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

In the process algebra community it is sometimes suggested that, on some level of abstraction, any distributed system can be modelled in standard process-algebraic specification formalisms like CCS. This sentiment is strengthened by results testifying that CCS, like many similar formalisms, is Turing powerful and provides a mechanism for interaction. This paper counters that sentiment by presenting a simple fair scheduler—one that in suitable variations occurs in many distributed systems—of which no implementation can be expressed in CCS, unless CCS is enriched with a fairness assumption. Since Dekker’s and Peterson’s mutual exclusion protocols implement fair schedulers, it follows that these protocols cannot be rendered correctly in CCS without imposing a fairness assumption. Peterson expressed this algorithm correctly in pseudocode without resorting to a fairness assumption, so it furthermore follows that CCS lacks the expressive power to accurately capture such pseudocode.
Original languageEnglish
Pages (from-to)175-205
Number of pages31
JournalActa Informatica
Volume52
Issue number2
DOIs
Publication statusPublished - 19 Mar 2015

Fingerprint

Dive into the research topics of 'CCS: It’s not fair!'. Together they form a unique fingerprint.

Cite this