Professor Golab's 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 his DBLP record. Additional information on specific projects appears below.
Blockchain and Distributed Ledgers
Professor Golab is one of the founding members of the Sirius Research Group at Waterloo. The group's mission is to study the foundations and applications of blockchain technology. Professor Golab's work in this area focuses on multi-data center scalability and robustness against both failures and asynchrony. He is a co-author of the RCanopus distributed consensus protocol, and has published several papers on blockchain and decentralized applications.
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. Professor Golab's 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, and paved the way for several follow-up papers. My latest efforts in the area of persistent memory focus on detectability (see DISC 2021 and ApPLIED@PODC 2022).
Analyzing Eventual Consistency
In this collaborative project, which began at Hewlett-Packard Labs, the research team seeks to understand the behaviour of eventually-consistent key-value storage systems (e.g., Cassandra). The initial goal was 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, the group leverages 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 Professor Golab's earlier work on verifying consistency properties (see PODC 2011). He has 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, Professor Golab has written a formal proof of Abadi's PACELC principle based on the inherent latency-consistency trade-off (see preprint and ACM SIGACT News version).
Don't forget to visit the Waterloo Consistency Analyzer (WatCA) on GitHub.
Distributed indexing and transaction processing
This project, which started at Hewlett-Packard Labs, looks at ways to create large and fast index data structures by harnessing together multiple commodity servers. These novel data structures leverage in-memory storage to provide high-throughput low-latency transactional operations. The most significant publications arising from this work appear in VLDB 2008, VLDB 2012, and VLDB 2019.
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. Professor Golab's work in this area 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:
- writable objects (PODC 2014)
- strong linearizability (STOC 2011)
- cache-coherent vs. distributed shared memory models (PODC 2011)
- FCFS mutual exclusion (DISC 2008 / Dist. Comp. Journal)
- compare-and-swap (PODC 2007 / Dist. Comp. Journal)
- leader election (PODC 2006 / SIAM Journal on Computing)
Acknowledgment of Financial Support
Professor Golab and his students acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), Ontario Ministry of Research and Innovation, Google, Hewlett-Packard, Cisco, Amazon, Microsoft, and Nvidia.