CCS: it's not fair! Fair schedulers cannot be implemented in CCS-like languages even under progress and certain fairness assumptions

DOI10.1007/S00236-015-0221-6MaRDI QIDQ2340255zbMATH OpenOpenAlexFDO

Publication date 16 April 2015

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.05964

fairness distributed system fair scheduler

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: 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.

Recommendations

Cites work

Cited in

(17)

Describes a project that uses

Uses Software

This page was built for publication: CCS: it's not fair! Fair schedulers cannot be implemented in CCS-like languages even under progress and certain fairness assumptions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2340255)