Lamport algorithm for mutual exclusion

Mutual exclusion and coordination

Processes in different computers share resources (files, databases, printers) but have no shared memory. Mutual exclusion lets only one process use a shared resource (its critical section, CS) at a time. It coordinates the processes by a fixed rule on the order of access, based on messages and logical timestamps, so that actions are consistent and no resource is used by two processes together.

Lamport's mutual exclusion algorithm

It uses Lamport logical clocks and assumes reliable FIFO channels. Each process Pi keeps a request queue ordered by timestamp (Ci, i).

1. Request: to enter the CS, Pi puts its request (timestamp, i) in its own queue and sends REQUEST(ts, i) to all other N−1 processes.
2. On receiving a REQUEST from Pj: put it in the local queue and send a REPLY (with a later timestamp) to Pj.
3. Entry condition: Pi enters the CS when both hold: (a) its own request is at the head of its queue (smallest timestamp), and (b) it has received a message (REPLY) with timestamp larger than its request from every other process.
4. Release: on leaving the CS, Pi removes its request from its queue and sends RELEASE to all other processes; they remove Pi's request from their queues.

 P1: REQ(5,1) --> P2,P3          (queue: 5,1)
 P2: REPLY --> P1; P3: REPLY --> P1
 P1 sees own request at head + replies: enters CS
 P1: RELEASE --> P2,P3

Why it ensures mutual exclusion: requests are totally ordered by (timestamp, id). Two processes cannot both be at the head with replies from the other, since the one with the larger timestamp sees the earlier request ahead in its queue (the FIFO channel ensures the earlier request arrives before a later reply). Requests are served in order, so there is no starvation.

Messages: 3(N−1) per entry (N−1 REQUEST, N−1 REPLY, N−1 RELEASE). Ricart-Agrawala reduces this to 2(N−1) by merging release and reply.