A generic local-spin fetch-and-φ-based mutual exclusion algorithm

We present a generic fetch-and-φ-based local-spin mutual exclusion algorithm, with O(1) time complexity under the remote-memory-references time measure. This algorithm is “generic” in the sense that it can be implemented using any fetch-and-φ primitive of rank 2N, where N is the number of processes. The rank of a fetch-and-φ primitive is a notion introduced herein; informally, it expresses the extent to which processes may “order themselves” using that primitive. This algorithm breaks new ground because it shows that O(1) time complexity is possible using a wide range of primitives. In addition, by applying our generic algorithm within an arbitration tree, one can easily construct a Θ(max(1,logrN)) algorithm using any primitive of rank r, where 2⩽r