25th IEEE International Conference on Distributed Computing Systems (ICDCS'05)
Transformations of Mutual Exclusion Algorithms from the Cache-Coherent Model to the Distributed Shared Memory Model
Columbus, Ohio, USA
June 06-June 10
ISBN: 0-7695-2331-5
We present two transformations that convert a class of local-spin mutual exclusion algorithms on the cache-coherent model to local-spin mutual exclusion algorithms on the distributed shared memory model without increasing their time complexity. Our first transformation uses registers and test-and-set objects, and does not increase the number of busy-waiting periods. The second transformation uses only registers, but contains two busy-waiting periods for each busy-waiting period of the input algorithm. We carefully define the class of mutual exclusion algorithms that are applicable to our transformations, and formally prove the correctness of our transformations.