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

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. August 26, 1991 i 1. Introduction Mutual exclusion is a basic and classic synchronisation problem. Informally it can be formulated as follows. We have a collection of N processes each having the structure illustrated in Figure 1.1. repeat NCS Trying Protocol CS Exit Protocol forever Figure 1.1: Mutual exclusion problem Each process iterates repeatedly through a non-critical section (NCS) and a critical section (CS). The problem is to design a Trying Protocol and and Exit Protocol which surround the critical section and synchronise access to it in the following sense: Mutual Exclusion: No two processes should ever be inside their critical sections at the same time. Deadlock Freedom: A set of processes wishing to enter the critical sec...