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:
- $P$ starts with clock 10 and sends request $m_1$ to $Q$
- $Q$ starts with clock 1 and sends request $m_2$ to $P$
- $Q$ receives request $m_1$ with timestamp 10 and sends acknowledge message $m_3$ to $P$
- $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
- $P$ receives message $m_2$ and responds to $Q$ with acknowledge
- $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?