As a demonstration of the usefulness of his clock synchronization scheme, Leslie Lamport created a distributed mutual exclusion algorithm. This is a non-token-based algorithm with no central controller. As these algorithms go, it's pretty simple, and quite easy to understand without massive amounts of study and hard work.

The Algorithm
Each site Si has a queue called request_queue which contains mutex requests ordered by timestamp ts. In order for this algorithm to work properly, messages must arrive in FIFO order between pairs of sites - if they arrive out of order, strange things can happen.

Requesting the critical section

  1. When a site Si wants to go into the critical section (CS), it sends a message REQUEST(tsi, i) to all sites in its request set, and places that request on its request_queuei.
  2. When a site Sj receives the REQUEST(tsi, i) from site Si, it sends back a timestamped REPLY message to Si and puts Si's request on its own request_queuej.

Executing the Critical Section
A site Si can enter the CS when these conditions are true:

  • Si has receieved a message with a timestamp greater than (tsi, i) from each other site
  • Si's request is at the top of its own request_queuei.

Releasing the critical section

  1. When site Si leaves the CS, it takes its request off of the top of its request queue, and sends a RELEASE message (with timestamp) to all the sites in its request set.
  2. When site Sj receives a RELEASE message from Si, it removes that request from its request queue.

Lamport's algorithm uses 3(N - 1) messages per CS invocation: (N - 1 ) REQUEST, REPLY, and RELEASE messages each are sent. The synchronization delay is T, the average message delay.