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-6zbMath1327.68171arXiv1505.05964OpenAlexW2081455126MaRDI QIDQ2340255

Peter Höfner, Robert J. van Glabbeek

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

zbMATH Keywords

fairnessdistributed systemfair scheduler

Mathematics Subject Classification ID

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

Related Items (15)

Structure Preserving Bisimilarity, Supporting an Operational Petri Net Semantics of CCSP ⋮ Off-the-shelf automated analysis of liveness properties for just paths ⋮ Unnamed Item ⋮ Modelling mutual exclusion in a process algebra with time-outs ⋮ Just testing ⋮ Keep it fair: equivalence and composition ⋮ Reactive bisimulation semantics for a process algebra with timeouts ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Explicit Identifiers and Contexts in Reversible Concurrent Calculus ⋮ Ensuring liveness properties of distributed systems: open problems ⋮ Unnamed Item ⋮ Global types with internal delegation ⋮ Off-the-shelf automated analysis of liveness properties for just paths (extended abstract)

Uses Software

• LOTOS
• COSY

Cites Work

• Mutex needs fairness
• Trapping mutual exclusion in the box calculus
• Turing machines, transition systems, and interaction
• A fair calculus of communicating systems
• Automated analysis of mutual exclusion algorithms using CCS
• Liveness of a mutex algorithm in a fair process algebra
• On the consistency of Koomen's fair abstraction rule
• Appraising fairness in languages for distributed programming
• Myths about the mutual exclusion problem
• A calculus of mobile processes. I
• COSY - a system specification language based on paths and processes
• Comparing the worst-case efficiency of asynchronous systems with PAFAS
• Efficiency of asynchronous systems, read arcs, and the MUTEX-problem
• Weak and strong fairness in CCS
• A process algebra for timed systems
• Discrete time process algebra
• Abstract processes of place/transition systems
• Towards a unified approach to encodability and separation results for process calculi
• Fairness of actions in system computations
• Expressiveness of Process Algebras
• A Process Algebra for Wireless Mesh Networks
• Reactive Turing Machines
• Time and Fairness in a Process Algebra with Non-blocking Reading
• Ready-Trace Semantics for Concrete Process Algebra with the Priority Operator
• A Theory of Communicating Sequential Processes
• Nets, Terms and Formulas
• On Specifying Timeouts
• Reactive Systems
• Analysis of A time‐shared processor
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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