Mutual exclusion on a hypercube (Q2365580)

We present a decentralized, symmetric mutual exclusion algorithm that is tailored to the hypercube architecture. Our algorithm has better time complexity than a suitable hypercube adaptation of \textit{Maekawa}'s \(O(\sqrt N)\) Mutual Exclusion algorithm [A Sqrt(N) algorithm for mutual exclusion in decentralized systems, ACM Trans. Comput. Syst. 3, No. 2, 145-159 (1985)]. We show that, in the presence of contention, our algorithm has a shorter Blocking Delay than Maekawa's algorithm. In the absence of contention, our algorithm achieves optimal Round-trip Delay under both the \(n\)-port and the one-port communication models.