A Semantic Approach to Fairness

Abstract

In the semantic framework of metric process theory, we undertake a general investigation of fairness of processes from two points of view: (1) intrinsic fairness of processes, and (2) fair operations on processes. Regarding (1), we shall define a “fairification” operation on processes called Fair such that for every (generally unfair) process p the process Fair(p) is fair, and contains precisely those paths of p that are fair. Its definition uses systematic alternation of random choices. The second part of this paper treats the notion of fair operations on processes: suppose given an operator on processes (like merge, or infinite iteration), we want to define a fair version of it. For the operation of infinite iteration we define a fair version, again by a “fair scheduling” technique.