Relating Fairness and Timing in Process Algebras

CONCUR 2003 - Concurrency Theory
Eds.: R. Amadio, D. Lugiez
Springer 2003, Lect. Notes Comput. Sci. 2761, 446 – 460
Copyright by Springer, Berlin, Heidelberg DOI: 10.1007/b11938

This paper contrasts two important features of parallel system computations: fairness and timing. The study is carried out at 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 and with upper time bounds for the process activities.

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.