Keep it fair: equivalence and composition

DOI10.1016/J.JLAMP.2019.01.004MaRDI QIDQ2423741zbMATH OpenOpenAlexWikidataFDO

Authors Stephan Mennicke, Tobias Prehn

Publication date 20 June 2019

Published in Journal of Logical and Algebraic Methods in Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jlamp.2019.01.004

zbMATH Keywords

equivalencefairnesslabeled transition systemsparallel composition

Mathematics Subject Classification ID

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

Review text

Since E. W. Dijkstra introduced the concept of fairness in 1987, various fairness notions for different models have been introduced, discussed and compared. Roughly speaking, fairness excludes infinite executions of distributed systems or programs where a local component does not progress or does not execute a certain activity, although this activity is persistently or infinitely often enabled to occur. Fairness is not a semantical property of a distributed system, but is rather used as an assumption, restricting the relevant behavior to executions respecting fairness. Each notion of semantics of a formal modeling language for distributed systems induces an equivalence notion on models, expressing semantical equivalence of models, i.e., the same behavior according to this semantics. Unfortunately, fairness is not always respected by this equivalence. The first contribution of this paper is an equivalence spectrum in which fairness assumptions are preserved. Modeling languages for distributed systems are equipped with a composition operator, inducing parallel composition of component executions. The paper also analyses parallel composition operators and their synchronization mechanisms with respect to fairness.

Recommendations

• Keep it fair: equivalences
• Appraising fairness in languages for distributed programming
• Stepwise development of fair distributed systems
• scientific article; zbMATH DE number 4096758
• scientific article; zbMATH DE number 1231579

Cites work

• A calculus of communicating systems
• A fair calculus of communicating systems
• A Theory of Communicating Sequential Processes
• Algebraic laws for nondeterminism and concurrency
• Algebraic specification and verification of communication protocols
• CCS: it's not fair! Fair schedulers cannot be implemented in CCS-like languages even under progress and certain fairness assumptions
• Communicating sequential processes
• CONCUR '90. Theories of concurrency: unification and extension. Amsterdam, The Netherlands, August 1990. Proceedings
• Elements of distributed algorithms. Modeling and analysis with Petri nets
• Fair testing
• Fairness of actions in system computations
• scientific article; zbMATH DE number 3972158 (Why is no real title available?)
• scientific article; zbMATH DE number 3806938 (Why is no real title available?)
• scientific article; zbMATH DE number 1863165 (Why is no real title available?)
• Keep it fair: equivalences
• Mutex needs fairness
• Processes and the denotational semantics of concurrency
• Theoretical Aspects of Computing – ICTAC 2005

Cited in

(16)

• About fair asynchrony
• On equivalence-completions of fairness assumptions
• On fairness notions in distributed systems. II: Equivalence-completions and their hierarchies
• Preface for the special issue on interaction and concurrency experience 2017
• Fairness of actions in system computations
• On deadlock and fairness decision problems for computations on client-server systems
• scientific article; zbMATH DE number 3846854 (Why is no real title available?)
• scientific article; zbMATH DE number 3890707 (Why is no real title available?)
• A Distributed Maximal Scheduler for Strong Fairness
• scientific article; zbMATH DE number 4096758 (Why is no real title available?)
• scientific article; zbMATH DE number 140260 (Why is no real title available?)
• scientific article; zbMATH DE number 1231579 (Why is no real title available?)
• scientific article; zbMATH DE number 2036567 (Why is no real title available?)
• scientific article; zbMATH DE number 2080199 (Why is no real title available?)
• Keep it fair: equivalences
• A note on fairness in I/O automata

This page was built for publication: Keep it fair: equivalence and composition

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