Arbiter

A arbiter is a device which examines two or more signals which are either:

• synchronous, but using clocks which are not fixed relative to one another; or
• at least one is asynchronous

and decides which of them arrived first.

For signals that arrive more or less simultaneously, it is usually more important that the arbiter pick one relatively quickly, without dithering too long over the choice. That is because the chief function of an arbiter is usually to provide mutual exclusion; i.e. to prevent two different clients from trying to use a single resource at the same time.

If the incoming signals are aligned 'just right' (in other words, 'just wrong'), this process can be subject to meta-stability issues, if the circuitry is constructed of standard digital components (flip-flops, etc).

One common solution is to use a special-purpose component called a 'three-output flip-flop', which has a 'not done yet' output in addition to the normal '0' and '1' outputs. The third output is produced by the addition of two analog comparators, which look at the output, and check to see if it is above a low margin, and below a high margin (i.e. the output has not yet settled into one state or another).

Even this kind of arbiter is not guaranteed to produce an answer within a fixed, bounded time (it is currently believed that this is theoretically impossible), but at least the user is aware that such an arbiter is still dithering. By suitable engineering, it is however possible to create arbiters that do meet a modest timing limit an extremely high percentage of the time (with failure rates on the order of centuries).

Further reading

• Warren Mackie Littlefield, Thomas J. Chaney, "The Glitch Phenomenon", Technical Memo No. 10, Washington University in St. Louis, 1966 - An extensive look at early WUSTL work on meta-stability, it includes an amusing analogy to describe the arbiter meta-stability problem
• Warren Mackie Littlefield, Thomas J. Chaney, "The Synchronizer "Glitch" Problem", Technical Report No. 47, Washington University in St. Louis, 1974 - Includes perhaps the earliest description of the 'three-output flip-flop' solution
• David J. Kinniment, John V. Woods, "Synchronization and Arbitration Circuits in Digital Systems", Proceedings of the IEEE, Vol. 123, pp. 961-966, 1976 - A crisp description of the three-output flip-flop solution