[an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] 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.

Blockchain and Distributed Ledgers

I am one of the founding members of the Sirius Research Group at Waterloo. Our mission is to study the foundations and applications of blockchain technology. My work in this area focuses on multi-data center scalability and robustness against both failures and asynchrony. I am a co-author of the RCanopus distributed consensus protocol.

Data Structures and Algorithms for Non-Volatile Main Memory

Please see our new web page!

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 (see extended draft of Recoverable Mutual Exclusion) explores additional implementation techniques in the context of lock-based programming. A follow-up paper appears in 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, PODC 2015 (see extended version), SCDM 2015, and SSS 2017 (best paper award). In a recent continuation of this project, I have written a formal proof of Abadi's PACELC principle based on the inherent latency-consistency trade-off (see preprint and ACM SIGACT News version).

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:

Acknowledgment of Financial Support

My students and I acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), Google, Hewlett-Packard, Cisco, Amazon, and Nvidia.