Archive 2020

Foundations of distributed storage


  • Distributed emulation of shared memory — the ABD protocol;
  • Consensus using shared storage — Disk Paxos;
  • Reconfiguration of distributed storage;
  • Using erasure codes in distributed storage.

Materials: slides, video

Prof. Idit Keidar


Programming for persistent memory

For the coming decade, dynamic random-access memory (DRAM) is likely to be replaced in many applications by new forms of non-volatile memory (NVM), which retain their contents when power is lost. This prospect raises the possibility that certain data formerly kept in files might instead reside "in memory" across program runs and even system crashes, leading to significant reductions in program complexity and run-time overhead. To achieve this vision, this class will explore a variety of topics in the rapidly evolving field of persistent memory, including hardware (memory and processor) foundations; formal correctness criteria (memory persistency, durable linearizability); persistent data structures; run-time systems for failure atomicity; dynamic memory allocation; and operating system support for failure recovery and for safe, user-level sharing.

Materials: slides, exercises, video

Prof. Michael Scott

University of Rochester

Reasoning about data consistency in distributed systems

Modern distributed systems often partition and replicate the data they manage across a large number of nodes and a wide geographical span. A key challenge that such systems have to address is maintaining data consistency in the presence of concurrent modifications at different nodes and despite inevitable failures. There is a spectrum of consistency models that a system can provide, and navigating it is far from trivial. Strong consistency models give the programmer the illusion that all nodes are always in sync, but hinder system scalability. In contrast, weak consistency models expose the programmer to the effects of replication in exchange for more scalable implementations. We will present modern methods for formally specifying consistency models of distributed systems and reasoning about how their choice affects system correctness.

Materials: slides, video

Prof. Alexey Gotsman


Cryptographic tools for distributed computing

This short course presents a brief introduction to concepts and tools from modern cryptography. Based on mathematical models for reasoning about the security of information systems, the course explains basic notions like pseudorandomness, symmetric-key encryption and public-key encryption. It also introduces techniques to use cryptographic algorithms in distributed systems, such as threshold cryptography and verifiable randomness.


  • Basics of cryptography and provable security
  • Pseudo-random generators, pseudo-random functions and secret-key cryptosystems
  • Public-key cryptography, public-key encryption and digital signatures
  • Distributed cryptography

Materials: slides, video

Prof. Christian Cachin

University of Bern

A recoverable lock that meets the MCS gold-standard

The efficient design of a mutex lock is a fundamental problem that attracted a great deal of research, which culminated in the MCS algorithm that satisfies three important properties. First, unlike many algorithms that require a knowledge of the maximum number N of processes that access the algorithm and require their names to be from the set {1, 2, ... , N}, the MCS algorithm can support an arbitrary number of processes of arbitrary names. Second, the MCS algorithm guarantees that, of the memory references that a process makes while acquiring and releasing the lock, the number of references not satisfied by the cache is bounded by a small constant. Third, the MCS algorithm is also space-efficient: M locks shared by N processes require only O(M+N) words of memory to implement (as opposed to O(MN)).

However, traditional algorithms, such as MCS, are not fault-tolerant: if the system crashes due to a power outage and subsequently restarts, the processes start over from the protocol's initial configuration. The more attractive alternative of letting the restarted processes "recover" their state at the time of the crash and resume from there became a possibility with the recent advent of non-volatile random access memory. In particular, research over the past four years has led to a number of such "recoverable" algorithms, but none of them meet the gold standard set by MCS in the sense that they lack at least two of the three properties described above.

In this course, Prasad will describe the ongoing research that has led to the first recoverable algorithm that meets the gold standard set by MCS.

Materials: exercises, video

Prof. Prasad Jayanti


From crash to Byzantine fault tolerance, and beyond

In this lecture, Rodrigo will present the two main system and fault models that have been used for the last four decades: the crash fault model, which captures the effects of faults that cause a process or a machine to crash, and the Byzantine fault model, which captures arbitrary failure modes. He will discuss how to design storage protocols under these two models. The lecture will conclude with a discussion on why we might need to revisit these two models in the future.

Materials: slides, exercises, video

Prof. Rodrigo Miragaia Rodrigues


Algorand: Consensus and smart contracts

Blockchains stand to revolutionize the way modern society operates. They can secure all kinds of traditional transactions, such as payments, in the exact order in which the transactions occur; and enable totally new transactions, such as cryptocurrencies and smart contracts. They can remove intermediaries and usher in a new paradigm for trust. As currently implemented, however, blockchains scale poorly and cannot achieve their enormous potential.

Algorand is the first permissionless blockchain that is truly secure, scalable and decentralized. It works in a highly asynchronous environment, dispenses with "proof of work" and "miners" and requires only a negligible amount of computation. Its transaction history does not "fork" even during a network partition, guaranteeing the immediate finality of a transaction the moment the transaction enters the blockchain. In this talk, the lecturer will introduce Algorand's core technology, recent development, and roadmap.

Materials: video

Prof. Jing Chen