New Perspectives on Fairness

I have just posted the concurrency column for the October 2006 installement of the Bulletin of the EATCS. The October column is a lovely piece entitled New Perspectives on Fairness by Daniele Varacca and Hagen Voelzer.

Fairness is an important concept that appears repeatedly in various forms in different areas of computer science, and plays a crucial role in the semantics and verification of reactive systems. Entire books are devoted to the notion of fairness---see, for instance, the monograph by Nissim Francez published in 1986---, and researchers in our community have painstakingly developed a taxonomy of various fairness properties that appear in the literature, such as unconditional fairness, weak fairness, strong fairness, and so on. This research is definitely important in light of the plethora of notions of fairness that have been proposed and studied in the literature.

But when is a temporal property expressing a fairness requirement? The authors of this column have recently developed a very satisfying answer to this fundamental question by offering three equivalent characterizations of ``fairness properties'' in the setting of linear-time temporal logic: a language-theoretic, a topological, and a game-theoretic characterization. This survey discusses these recent results in a very accessible fashion, and provides also a beautiful link between the study of fairness and classic probability theory.

I trust that you will enjoy reading this piece by Daniele and Hagen as much as I did. It is not often that one sees notions and results from several areas of mathematics and computer science combine so well to offer a formalization of a concept that confirms our intuition about it.