For what example would Maekawa's algorithm allow out of timestamp order access to the critical section. It is mentioned that ordering is not satisfied in Maekawa's algorithm. But in what scenario would this be true?
From my understanding, we will always have the queue at each process that follows FIFO and will ensure that whichever process requested access to critical seciton first, gets votes from the voting set first. Doesn't this satisfy ordering?
Consider three processes $P_1, P_2, P_3$ with voting sets $V_1 = {P_1, P_2}, V_2 = {P_2, P_3}, V_3 = {P_1, P_3}$. Let $T(p_i)$ denote the timestamp of a request from process $p_i$, and assume $T(p_1) < T(p_2)$ (meaning $p_1$ tries to enter the critical section before $p_2$). Suppose $p_1$ broadcasts its request to $V_1$ at time $t_0$, but a transient network delay causes $p_2$ to receive this message very late. Meanwhile, at time $t_1 > t_0$, $p_2$ sends its own request to $V_2$, which happens to arrive quickly at $p_3$. Because $p_3$ is in $V_2$ and also in $V_3$, it has no conflicting request from $p_1$ yet (that message is still delayed), so $p_3$ grants its vote to $p_2$. Process $p_2$ itself trivially grants its own vote to itself, so $p_2$ collects enough votes to enter the critical section and does so at some local time $t_2$. Eventually $p_1$’s request arrives at $p_2$, but by that time $p_2$ has already been granted the votes needed. Thus $p_2$ gets the critical section despite $T(p_1) < T(p_2)$, violating the global ordering. The local FIFO queue at each process only ensures that if two requests arrive at the same process in order, that single process respects arrival order. Maekawa’s algorithm uses intersections of voting sets that do not globally coordinate timestamps, so there is no guarantee of a total order. To show this rigorously, define the event of $p_1$’s request arrival at $p_2$ as $A_{1,2}$ and $p_2$’s request arrival at $p_3$ as $A_{2,3}$. In a run where $A_{1,2}$ is sufficiently delayed, we get $A_{2,3}$ before $A_{1,2}$ even though $T(p_1) < T(p_2)$. Formally, if $A_{1,2}$ occurs at time $\delta_{1,2} \gg T(p_2)$ while $A_{2,3}$ occurs at time $\delta_{2,3} \approx T(p_2)$, then $p_2$ is voted in first. The existence of such $\delta_{1,2}$ and $\delta_{2,3}$ that reorder requests demonstrates how Maekawa’s algorithm permits out-of-timestamp-order critical section entry. One can construct arbitrarily large sets of processes and voting sets to replicate this effect via local rather than global ordering.
