A space- and time-efficient local-spin spin lock. (Q1853104)

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.