Computer Science Department
School of Computer Science, Carnegie Mellon University


On the Existence of Delay-Insensitive Fair Arbiters: Trace Theory and its Limitations


David L. Black

October 1985

A recent result claims to prove the non-existence of delay-insensitive fair arbiters oot Udding.J.T., On the non-existence of delay-insensitive fair arbiters , Technical Memorandum 306, Washington University, St. Louis, MO., July 1985. ; this has potentially profound consequences for both the theory and practice of asynchronous design. The resulting controversy ranges from hardware designers who are sure such arbiters exist and therefore doubt the utility of the theory to theoreticians who wonder just exactly what the hardware designers have been building. Among other goals, this paper makes a forthright attempt to settle the controversy.

We begin with an introduction to enough trace theory to formally present the concept of delay insensitivity and the above result. We then continue with a formal discussion of the possible notions of fairness and use them to analyze the non-existence result. This analysis reaches three important conclusions; first that the result is theoretically correct but of no practical significance because it uses an inappropriate notion of fairness, second that delay-insensitive fair arbiters do exist which we show by exhibiting an example , and third that the present trace theory lacks the expressive power to specify any of the relevant notions of fairness for asynchronous self-timed arbiters. Motivated by our third conclusion, the second section of this paper extends and generalizes trace theory to permit the expression of these fairness properties. Following an approach originally pioneered by Muller, we extend trace theory to infinite traces; as he discovered, liveness is necessarily important to the extension. We discuss the impact and role of liveness in our extension by example. In the process of formulating the extension we develop a more general trace-theoretic composition operator that does not require the domain constraints composability restrictions used by other authors. Finally we define an extended concept of delay insensitivity and formally show that our fair arbiter from the first section is delay insensitive.

33 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by