Half An Algorithm

Lamport's 1978 distributed mutual exclusion algorithm, condensed. Every message is timestamped, every process keeps a private request queue, and channels between any pair of processes are FIFO.

1. request:  send (T_i, "P_i requests") to all others; enqueue it locally.
2. on request from P_j: enqueue it; send P_j a timestamped ack.
3. release:  remove own request from the queue; tell all others.
4. on release from P_j: remove P_j's request from the queue.
5. grant to P_i when BOTH hold:
     (i)  P_i's own request is ordered first in P_i's queue by (T, pid)
     (ii) P_i has received a message from EVERY other process
          timestamped later than T_i

A team implements rules 1 through 4 and condition (i), and drops condition (ii) as redundant bookkeeping. With three processes and clocks near zero: P3 requests at T=4, P1 requests at T=7, and P3's request message to P1 is stuck in the network for 500 ms. What breaks?

Liveness. Condition (ii) is what eventually delivers the acknowledgements a waiting process needs, so without it a process can wait forever behind a request that was already released.

Mutual exclusion itself. P1's queue holds only (7,P1), so (i) is satisfied and P1 enters; P3's queue holds only (4,P3), so P3 enters too. Both hold the resource.

Only the ordering requirement. One process still holds the resource at a time, but P1's later request can be granted ahead of P3's earlier one.

Nothing, given FIFO channels. Messages between any pair arrive in send order, so each queue already reflects every request that could outrank the local one.