A space- and time-efficient local-spin spin lock.
A simple code transformation is presented that reduces the space complexity of Yang and Anderson's local-spin mutual exclusion algorithm. In both the original and the transformed algorithm, only atomic read and write instructions are used; each process generates \(\Theta(\log N)\) remote memory references per lock request, where \(N\) is the number of processes. The transformed algorithm uses \(\Theta(N)\) distinct variables, which is clearly optimal.
scientific article; zbMATH DE number 1856442