Lamport's Algorithm

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 S_i 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 S_i wants to go into the critical section (CS), it sends a message REQUEST(ts_i, i) to all sites in its request set, and places that request on its request_queue_i.
2. When a site S_j receives the REQUEST(ts_i, i) from site S_i, it sends back a timestamped REPLY message to S_i and puts S_i's request on its own request_queue_j.

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

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

Releasing the critical section

1. When site S_i 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 S_j receives a RELEASE message from S_i, it removes that request from its request queue.

Performance
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.