Igor Benko
The Committee Problem and Delay-Insensitive Circuits

MMath thesis
Department of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1
May 1993

Abstract

The committee problem (n-party rendezvous) is a general synchronization problem that combines mutual exclusion and condition synchronization. We show that the following problems are special cases of the committee problem: phase synchronization, mutual exclusion, dining philosophers, the arbitrating test-and-set, and the n-input sequencer. Specifications of committee schedulers for these special cases and for the general case are given in terms of a CSP-like language called commands and in terms of Petri nets. Efficient implementations of the special-case schedulers as delay-insensitive circuits are derived. A number of implementations of a general committee scheduler are proposed: a naive implementation which suffers from deadlock, and several implementations based on sequential finite state machines. Different ways of implementing the finite state machines for the general committee scheduler are discussed.

Download this document (compressed postscript).


Go back to publications index.
Go back to Maveric home page.