School on the Practice and Theory of Distributed Computing

A journey into the World of Persistent Memory

Persistent memory is a new byte-addressable durable device included in the cache-consistency domain of processors. Since persistent memory is almost as efficient as volatile memory, using a file system interface to access persistent memory is inefficient. In this lesson, we will study how we can efficiently access persistent memory without using a file system interface. This is difficult because a crash may happen at any time, and the state stored in persistent memory has to remain consistent after the crash. The lesson will introduce new programming abstractions for persistent memory, and present how we can build these abstractions by starting from simple low-level instructions. We will also study how we can implement these abstractions efficiently in a practical lab (you will only need a Linux system with a C compiler).

Cache-Conscious Concurrent Data Structures for Near-Memory Computing

The performance gap between memory and CPU has grown exponentially. To bridge this gap, hardware architects have proposed near-memory computing (NMC), where a lightweight processor (called an NMC core) is located close to memory. Due to its proximity to memory, memory access from an NMC core is much faster than from a CPU core. New advances in 3D integration and die-stacked memory make NMC viable in the near future. Prior work has shown significant performance improvements by using NMC for embarrassingly parallel and data-intensive applications, as well as for pointer-chasing traversals in sequential data structures. However, current server machines have hundreds of cores, and algorithms for concurrent data structures exploit these cores to achieve high throughput and scalability, with significant benefits over sequential data structures. Thus, it is important to examine how NMC performs with respect to modern concurrent data structures and understand how concurrent data structures can be developed to take advantage of NMC.

This talk focuses on specific examples of cache-optimized data structures, such as skiplists and B+ trees, where lookups begin at a small number of top-level nodes, and diverge to many different node paths as they move down the hierarchy. These data structures expoint a memory structure split into a host-managed portion consisting of higher-level nodes and an NMP-managed portion consisting of the remaining lower-level nodes.

Joint work with Jiwon Choe, Andriew Crotty, Tali Moreshet, and Iris Bahar.

Database Isolation Levels

Transaction isolation specifications determine which database states transactions can observe during their execution, and thus, which results queries are allowed to return. This isolation corresponds to the letter "I" in the famous ACID acronym. Different "ACID" systems actually provide a spectrum of isolation levels, which expose the concurrency inside the database to the application programmer to a lesser or greater extent. Examples of such levels are serializability, snapshot isolation, and read committed.

Historically, the definitions of isolation levels have often been ambiguous or tied to database implementation internals. As a result, transaction isolation remains a difficult topic, even for seasoned database professionals. This is a problem because understanding the isolation level provided by a given database is necessary to use it correctly. In this tutorial, I will explain the concept of transaction isolation and highlight pitfalls to be wary of when navigating the spectrum of isolation levels while also explaining some of the levels provided by modern database systems.

Modular Construction of Live Byzantine Consensus Protocols

In this tutorial, we will consider the question of constructing fault-tolerant distributed protocols in the presence of arbitrary (or Byzantine) process failures and timing uncertainty. This class of protocols is an attractive design choice for mission-critical systems, such as distributed ledgers, thanks to their ability to deal with a wide variety of adversarial behaviors. Our specific focus will be on Byzantine fault-tolerant (BFT) protocols for consensus and state-machine replication (SMR), which are widely used by the distributed ledger systems to construct and maintain a replicated sequence of transaction blocks or blockchain. While many existing BFT consensus or SMR protocols do a good job of guaranteeing that the blockchain is always consistent and never forks, until recently, the process of ensuring that it also makes progress (i.e. an honest participant is eventually able to add a new block) has been poorly understood. This led to implementations that were unnecessarily complex and prone to subtle bugs.

As part of the tutorial, I will introduce a new modular framework, which facilitates constructing BFT consensus and SMR protocols with well-defined progress guarantees. This is achieved by delegating the intricacies of handling timing uncertainties (which is key for ensuring progress) into a new pluggable abstraction of a view synchronizer. I will discuss the view synchronizer properties and its implementation, and then show how it can be used to obtain versions of several well-known BFT consensus and SMR protocols (such as PBFT, HotStuff, and Tendermint), which are simple, efficient, and provably correct.