Lamport's distributed mutual exclusion algorithm

Lamport's distributed mutual exclusion algorithm is a contention-based method for letting the processes of a distributed system take turns in a critical section with no central coordinator. Every process keeps its own queue of pending requests, ordered by virtual timestamps derived from Lamport timestamps. A process that wants the critical section puts its request in its own queue, sends the request to every other node and waits for a reply from each. It enters when its own request is at the head of its queue and all replies have arrived. On leaving it removes its request and sends a release message to every process. The other processes queue each request they receive, answer with a timestamp, and delete a request when its release arrives. Each entry costs 3(N - 1) messages for N processes, made up of requests, replies and releases. Its drawbacks are that the failure of any one process halts progress and that the message cost is high. The Ricart-Agrawala algorithm is an improvement over it.