Question

Lamport's distributed mutual exclusion algorithm (also described here) solves mutual exclusion problem for $N$ processes with $3(N-1)$ messages per request ("take and release lock" cycle).

It requires that for each pair of processes $P$ and $Q$ all messages send by $P$ to $Q$ are received and processed by $Q$ in the same order. E.g. if $P$ sends messages $m_1$ and $m_2$ in that order, $Q$ cannot receive $m_2$ before receiving $m_1$.

I would like to see how it breaks if I remove that First-In-First-Out condition and allow reordering. The only counterexample I was able to built uses two processes who want to acquire the shared resource:

  1. $P$ starts with clock 10 and sends request $m_1$ to $Q$
  2. $Q$ starts with clock 1 and sends request $m_2$ to $P$
  3. $Q$ receives request $m_1$ with timestamp 10 and sends acknowledge message $m_3$ to $P$
  4. $P$ receives message $m_3$ before $m_2$ and enters critical section. As far as $P$ is concerned, it's the only process wanting the resource
  5. $P$ receives message $m_2$ and responds to $Q$ with acknowledge
  6. $Q$ enter critical section as $Q$'s request has timestamp 1 and $P$'s request has timestamp 10, so $Q$ has priority

However, that requires $P$ to respond to $Q$'s request $m_2$ while in critical section. Otherwise, $Q$ will receive acknowledgment when $P$ is no longer in critical section and there will be no conflict.

Question being: how to construct a counterexample where processes do not respond to external messages while in critical section?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top