SPTDC 2023
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.
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.
Prof. Alexey Gotsman
IMDEA
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.
Structure:
- 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
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.
Prof. Prasad Jayanti
Dartmouth
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.
Prof. Rodrigo Miragaia Rodrigues
IST
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
Algorand