Skip to the content of the web site.

Prof. Wojciech Golab — Research Projects

My research activities span three areas: in-memory storage systems, distributed computing theory, and optical networking. For a (nearly) complete list of publications, please refer to my DBLP record. Additional information on specific projects appears below.

Data Structures and Algorithms for Non-Volatile Main Memory

Recent breakthroughs in the production of low-latency non-volatile memories (e.g., 3D XPoint) foreshadow a convergence of primary and secondary storage into a single layer in the memory hierarchy that combines the performance benefits of conventional main memory with the durability of secondary storage. Harnessing these performance benefits in multi-core architectures requires a careful rethinking of concurrent data structures and synchronization algorithms. My research group has published several papers on this topic, starting with an investigation of correctness properties for shared objects in non-volatile main memory. This work appears in the proceedings of OPODIS 2015, and defines a correctness property called recoverable linearizability. Subsequent work appearing in PODC 2016 explores additional implementation techniques in the context of lock-based programming. A follow-up paper has been accepted to PODC 2017 and further research is underway with financial support from Google.

WatCA: The Waterloo Consistency Analyzer

Project page.

Analyzing Eventual Consistency

In this collaborative project, which began at Hewlett-Packard Labs, we seek to understand the behaviour of eventually-consistent key-value storage systems (e.g., Cassandra). Our initial goal is to analyze the consistency of data operations in such systems for various workloads, and quantify to what extent these systems deviate from the "gold standard" of linearizability. To that end, we leverage a methodology inspired by known algorithmic techniques for verifying shared memories. Preliminary experimental results arising from this project appear in HotDep 2012, and use technical ideas from my earlier work on verifying consistency properties (see PODC 2011). I have also co-authored a theoretical paper related to this project with colleagues at Google (see ICDCS 2013). The main contributions arising from this project include an invited article appearing in ACM Queue and CACM, as well as conference papers in ICDCS 2014 and PODC 2015.

Distributed B-tree

This project, conducted mostly at Hewlett-Packard Labs, looks at ways to create large and fast B-tree data structures by harnessing together multiple commodity servers. These novel data structures leverage in-memory storage to provide high-throughput low-latency transactional operations. Publications arising from this work appear in VLDB 2008 and VLDB 2012.

Theory of Shared Memory Algorithms

This body of theoretical work considers the problem of mutual exclusion, which underlies the popular practice of lock-based programming. My work in this area has helped establish a number of important complexity bounds on the amount of inter-process communication required to solve synchronization problems related to mutual exclusion. For more information, please see the following papers: