A first come first served mutual exclusion algorithm with small communication variables

Edward A. Lycklama and Vassos Hadzilacos

We present an algorithm for the mutual exclusion problem that satisfies the ``first come first served'' property and requires only five shared bits per participant. The algorithm works in a model of concurrency that does not assume atomic operations.