Lamport Distributed Mutual Exclusion

Normally, having consistent event ordering in a distributed system is hard because we have no common clock. Since we don’t have a common clock to measure with, we rely on logical properties of time in the absence of clock. Here we use causality replation between events.

In essence, Causality indicates a clock \(C\) is map from events to time satisfying: \(e\rightarrow e’\) implies \(C(e) < C(e’)\)

We can synthesize a clock by a simple protocol, usually referred as scalar clock or Lamport clock:

• Each process \(p\) has a local clock \(C(p)\).
• A message send by a process is stampled with the its corresponding local clock.
• On receiving \(M\), set the process’s local clock to be \(max(C(p), C(M)) + 1\).

This will give us a consistent total order of events in a distributed system.

Let’s take Lamport distributed mutual exclusion (DME) as an example. We use scalar clock to agree on the order of access to critical sections. Each process broadcasts a request with its local clock time. Receiver stores the request time and responds with its update local time (\(max(C(p), C(M)) + 1\)).

A process can only enter critical section given the condition \(W\) is met: \(W \equiv \forall...