Fairness of Actions in System Computations

This paper contrasts two important features of parallel system computations: fairness and timing. The study is carried out at a specification system level by resorting to a well-known process description language. The language is extended with labels which allow to filter out those process executions that are not (weakly) fair [as in Costa and Stirling (Acta Inf. 21:417–441, 1984) and in Costa and Stirling (Inf. Comput. 73:207–244, 1987)], and with upper time bounds for the process activities (as in Corradini et al. Acta Inf. 38:735–792, 2002). We show that fairness and timing are closely related. Two main results are stated. First, we show that each everlasting (or non-Zeno) timed process execution is fair. Second, we provide a characterization for fair executions of untimed processes in terms of timed process executions. This results in a finite representation of fair executions using regular expressions.