Department of Computer Science, Technion - Israel Institute of Technology, Haifa 32000, Israel

---

Abstract—k-Exclusion is a generalization of Mutual Exclusion that allows up to k processes to be in the critical section concurrently. Starvation Freedom and First-In-First-Enabled (FIFE) are two desirable progress and fairness properties of k-Exclusion algorithms. We present the first known bounded-space k-Exclusion algorithm that uses only atomic reads and writes, satisfies Starvation Freedom, and has a bounded Remote Memory Reference (RMR) complexity. Our algorithm also satisfies FIFE, and has an RMR complexity of O(n) in both the cache-coherent and distributed shared memory models.

Index Terms—k-exclusion, shared memory, remote memory reference

[PDF]

Cite: Meirav Zehavi, "An Improved k-Exclusion Algorithm," Journal of Computers vol. 9, no. 3, pp. 529-536, 2014.