---
title: "Lamport algorithm for mutual exclusion"
subject: "Distributed System"
chapter: 6
key: "semester_7/distributed_system:lamport-mutex"
source: https://www.bctengineer.com/q/semester_7/distributed_system/lamport-mutex
site: BCT Engineering
---

# Lamport algorithm for mutual exclusion

Distributed System · Chapter 6: Coordination and Agreement

- Asked in: 2070 Chaitra, 2+6 marks
- Video: [Lamport Algorithm for Mutual Exclusion 🔥🔥](https://www.youtube.com/watch?v=Fr9yFVi-w7M) — Perfect Computer Engineer
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/distributed_system/lamport-mutex
- Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-6

## Question

How does mutual exclusion help in co-ordination in distributed system? Explain the way Lamport algorithm ensures mutual exclusion.

## Short answer

Mutual exclusion coordinates processes by allowing only one at a time into its critical section, using message ordering and logical clocks for consistent access. Lamport’s algorithm ensures it: a process must have its own request at the head of its timestamp-ordered queue and have received replies from all others before entering. The total order of (timestamp, id) prevents two processes from both satisfying the entry condition simultaneously.

## Answer

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

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

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What two conditions must hold for Pi to enter the CS in Lamport's algorithm?
   A. Its request is at the head of its queue and it has a later-timestamped message from every other process
   B. It holds the token and has sent a RELEASE
   C. It has replies from a majority and its id is highest
   D. Its queue is empty and the coordinator agrees
   Answer: A. Head of the queue gives the smallest timestamp, and later messages from all others ensure no earlier request is still in transit. (Key point: Entry condition)

2. How many messages per entry does Lamport's algorithm need?
   A. 2(N-1)
   B. 3(N-1)
   C. 3
   D. N
   Answer: B. N-1 REQUEST, N-1 REPLY and N-1 RELEASE messages. (Key point: Message count)

3. What happens when Pi leaves the CS?
   A. It passes the token on
   B. It sends deferred replies
   C. It removes its request and sends RELEASE so others remove it from their queues
   D. It broadcasts a new election
   Answer: C. RELEASE lets others remove the request so the next head can proceed. (Key point: Role of release)

4. Why is the FIFO channel assumption needed?
   A. To avoid needing logical clocks
   B. To allow lost messages
   C. To make the token move in order
   D. So the earlier request arrives before a later reply, ensuring a process sees any earlier request ahead of its own
   Answer: D. FIFO ordering guarantees the larger-timestamp process knows of the earlier request, preventing both entering. (Key point: Why FIFO matters)

## Related in Distributed System

- [Token ring mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atoken-ring-mutex) — Distributed System, chapter 6, asked 3×
- [Ricart-Agrawala mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aricart-agrawala) — Distributed System, chapter 6, asked 2×
- [Lamport's logical clock algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-clock) — Distributed System, chapter 5, asked 5×
- [Problems of Lamport's clock; vector clock](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-problems-vector-clock) — Distributed System, chapter 5, asked 2×
- [Physical vs logical clocks; Lamport](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-physical-compare) — Distributed System, chapter 5
- [Clock sync problems; Chandy-Lamport](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aphysical-clock-problems-chandy-lamport) — Distributed System, chapter 5

## Related in other subjects

- [Critical section; mutual exclusion](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Acritical-section-mutual-exclusion-pc) — Operating System, chapter 3
- [Race condition; mutual exclusion requirements](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-mutual-exclusion-requirements) — Operating System, chapter 3
- [Semaphore for mutual exclusion](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Asemaphore-enforce-mutual-exclusion) — Operating System, chapter 3
- [Mutual exclusion via sleep and wake](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Amutual-exclusion-sleep-wake) — Embedded System, chapter 6