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