AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

We present an algorithm to solve the group mutual exclusion problem in the cache-coherent (CC) model. For the same problem in the distributed shared memory (DSM) model, Danek and Hadzilacos presented algorithms of $O(n)$ remote memory references (RMR) and proved a matching lower bound, where $n$ is the number of processes. We show that in the CC model, our algorithm achieves $O(min(\log n,k))$ RMR, where $k$ is the point contention, which is so far the best. Moreover, given a recent result of Attiya, Hendler and Woelfel showing that exclusion problems have a $\Omega(\log n)$ RME lower bound using registers, comparison primitives and LL/SC variables, our result closes the gap.

Chien-Chung Huang

--email hidden

passcode not visible

logged in users only