Mutual exclusion on a hypercube

DOI10.1006/JPDC.1993.1031MaRDI QIDQ2365580zbMATH OpenOpenAlexFDO

Authors Steven C. Bruell, Sukumar Ghosh, Ajay K. Gupta

Publication date 29 June 1993

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jpdc.1993.1031

zbMATH Keywords

Blocking Delaycontentionhypercubemutual exclusionRound-trip Delay

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10)

Review text

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.

Recommendations

• A fast, scalable mutual exclusion algorithm
• Improving fast mutual exclusion
• Adaptive and efficient mutual exclusion
• A new fast-path mechanism for mutual exclusion
• Adaptive solutions to the mutual exclusion problem

Cited in

(6)

• Nondominated \(k\)-coteries for multiple mutual exclusion
• Mutual exclusion scheduling
• Mutual exclusion as a matter of priority
• Mutual Exclusion by Interpolation
• scientific article; zbMATH DE number 842887 (Why is no real title available?)
• A class of high performance Maekawa-type algorithms for distributed systems under heavy demand

This page was built for publication: Mutual exclusion on a hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2365580)