2019/04/03 by Prasad Jayanti, Jayanti, Prasad, Siddhartha Jayanti +3
Computer Science · #Distributed systems and fault tolerance #Advanced Data Storage Technologies #Caching and Content Delivery
paper · pdf · doi:10.48550/arxiv.1904.02124
In light of recent advances in non-volatile main memory technology, Golab and\nRamaraju reformulated the traditional mutex problem into the novel em\nRecoverable Mutual Exclusion (RME) problem. In the best known solution for\nRME, due to Golab and Hendler from PODC 2017, a process incurs at most\nO(\(\log n)/(\log \log n)) remote memory references (RMRs) per passage,\nwhere a passage is an interval from when a process enters the Try section to\nwhen it subsequently returns to Remainder. Their algorithm, however, guarantees\nthis bound only for cache-coherent (CC) multiprocessors, leaving open the\nquestion of whether a similar bound is possible for distributed shared memory\n(DSM) multiprocessors.\n We answer this question affirmatively by designing an algorithm that\nsatisfies the same complexity bound as Golab and Hendler's for both CC and DSM\nmultiprocessors. Our algorithm has some additional advantages over Golab and\nHendler's: (i) its Exit section is wait-free, (ii) it uses only the\nFetch-and-Store instruction, and (iii) on a CC machine our algorithm needs each\nprocess to have a cache of only O(1) words, while their algorithm needs\nO(n) words.\n