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?

  • $\begingroup$ That modification (do not process messages in critical section) may sound a little like Ricart–Agrawala algorithm $\endgroup$ – yeputons Feb 4 at 17:28
  • $\begingroup$ Actually, it's not quite Ricart–Agrawala, because it still allows a process with lower priority to take the shared resource first. $\endgroup$ – yeputons Feb 11 at 16:25

Looks like this modification is correct. Proof is similar to proof of Lamport algorithm and follows.

Consider two processes $P_i$ and $P_k$ who entered critical sections at moments $e$ and $f$, correspondingly, requested them at moments $e'$ and $f'$, and exited at moments $e''$ and $f''$.

At moment $e$ process $P_i$ have received a confirmation from $P_k$. Suppose it was sent by $P_k$ at moment $g \to e$.

Case 1: $g < f'$. In that case, process $P_k$ has both itself and $P_i$ in queue, and $P_k$'s ticket is greater than $P_i$'s (because we use logical clock as tickets). So process $P_k$ cannot enter the critical section until it receives a release from $P_i$, and we have a correct mutual exclusion.

Case 2: $f' < f < f'' < g$. In that case, $f'' \to g \to e$, and we have a correct mutual correct mutual exclusion.

Case 3: $f' < f < g < f''$. That case is impossible as $P_k$ have sent a confirmation while in critical section.

Case 4: $f' < g < f < f''$. In that case, process $P_k$ should've received a confirmation from process $P_i$ by $f$. Suppose it was sent by $P_i$ at moment $h$. If $h > e$, then $h > e''$ and we have a correct mutual exclusion ($e'' \to h \to f$). Otherwise, $h < e$, so process $P_i$ learns about $P_k$'s wish before entering the critical section. Similarly, as $g < f$, $P_k$ learns about $P_i$'s wish before entering the critical section. But only one of them has lower priority, hence, their critical sections happen in order.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.