Candidate: Ahmed Fahmy
Date: November 1, 2023
Time: 1:00 PM
Place: EIT 3142
Supervisor(s): Golab, Wojciech
Abstract:
Persistent memory (PM) has emerged as a promising technology that enables data structure algorithms to preserve their consistent state after recovering from system failures. Detectable data structures have been proposed to detect the response of the last operation of a crashed process, and various lock-free detectable and recoverable concurrent data structures have been developed in the literature. However, designing detectable lock-based data structures is challenging due to the need to preserve the correctness properties of the underlying locks, such as mutual exclusion and deadlock-freedom, across failures. Therefore, lock-based detectable and persistent data structures are not as common as lock-free structures. In this work, we introduce DULL: A Fast, Scalable and Detectable Unrolled Lock-based Linked List. To the best of our knowledge, DULL is the fastest detectable lock-based linked list and the first detectable strictly-linearizable linked list. This paper presents the design and implementation of DULL, along with an evaluation of its recoverability and scalability. Experimental Results show that DULL is several-fold faster than the competition in all workloads that involve updates. Moreover, as opposed to some of the previous works, our algorithm is scalable when the multiprocessor is oversubscribed. DULL is a demonstration of the feasibility of using lock-based data structures with detectability in PM environments. We believe that DULL opens up new research directions for designing and analyzing detectable lock-based data structures.