@TechReport{Dartmouth:TR2011-682,
author = {Jonathan H. Choi},
title = {{A Solution to k-Exclusion with O(logk) RMR Complexity}},
institution = {Dartmouth College, Computer Science},
address = {Hanover, NH},
number = {TR2011-682},
year = {2011},
month = {June},
URL = {http://www.cs.dartmouth.edu/reports/TR2011-682.pdf},
comment = {
Senior Honors Thesis; advisor: Prasad Jayanti.
},
abstract = {
We specify and prove an algorithm solving k-Exclusion, a generalization of the Mutual Exclusion problem. k-Exclusion requires that at most k processes
be in the Critical Section (CS) at once; in addition, we require bounded exit, starvation freedom and fairness properties. The goal within this
framework is to minimize the number of Remote Memory References (RMRs) made. Previous algorithms have required Omega(k) RMRs in the worst case. Our
algorithm requires O(log k) RMRs in the worst case under the Cache-Coherent (CC) model, a considerable improvement in time complexity.
}
}