Please note: This PhD defence will take place in DC 3317 and online.
Gaetano Coccimiglio, PhD candidate
David R. Cheriton School of Computer Science
Supervisors: Professors Trevor Brown, Peter Buhr
The process of designing and implementing correct concurrent data structures is non-trivial and often error-prone. The recent commercial availability of non-volatile memory has prompted many researchers to also consider designing concurrent data structures that persist shared state allowing the data structure to be recovered following a power failure. These so-called persistent concurrent data structures further complicate the process of achieving correct and efficient implementations. Due to this difficulty, designing, implementing and effectively utilizing persistent concurrent data structures is often only feasible for expert programmers who already possess extensive specialized knowledge.
The goal of this thesis is to empower non-experts with the ability to achieve fast, safe, and persistent concurrent data structures without requiring the specialized knowledge needed to understand the details of such algorithms. I focus on two general techniques that non-experts can utilize to implement persistent concurrent data structures. Specifically, I consider transactional memory and universal constructions. Each approach provides a different trade-off between programmer effort and performance of the resulting data structures.
Achieving correct and efficient synchronization is one of the most difficult challenges when designing and implementing concurrent algorithms. This process can be simplified through the use of a mechanism known as transactional memory (TM). TMs allow users to execute sequences of memory accesses as atomic transactions. Within a transaction, the implementation can be written in a sequential manner with the added requirement of replacing accesses to shared objects with TM accesses. This requires minimal programmer effort. This approach is useful for non-experts since synchronization and persistence is handled by the TM. A different mechanism known as a universal construction (UC) trivializes the implementation of concurrent algorithms. Given a sequential object as input, a UC produces a concurrent object. Sequential data structures are relatively straightforward which makes this approach suitable for non-experts. Both TMs and UCs can be augmented to also guarantee persistence through the use of non-volatile memory.
I present a novel persistent TM, a novel volatile multiversion TM, and a novel persistent UC. I implement and experimentally evaluate these algorithms. These evaluations demonstrate that in many cases my algorithms represent the current state of the art. The end result of this thesis is a toolbox for non-experts to achieve fast, safe, and persistent concurrent data structures.
To attend this PhD defence in person, please go to DC 3317. You can also attend virtually on Zoom.