Back to search

University of Waterloo

Towards Fast, Safe and Persistent Concurrent Data Structures for Non-experts

Abstract

dc:description.abstract

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 allow recovery 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, 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 approach is useful for non-experts since synchronization 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 making 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. All three algorithms are fully implemented and experimentally evaluated. 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

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2026

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Coccimiglio, Gaetano

Subjects

dc:subject × 13

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/23896

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Coccimiglio, Gaetano. Towards Fast, Safe and Persistent Concurrent Data Structures for Non-experts. University of Waterloo, 2026. https://hdl.handle.net/10012/23896