Instructor: Kartik Nayak (kartik@cs.duke.edu)
Teaching Assistant: Manan Gandhi (manan.gandhi@duke.edu)
When: 4:40 PM – 5:55 PM Tuesdays and Thursdays
Where: LSRC D106
Office Hours: Wednesday 4-5 pm or by appointment
Synopsis:
Consensus and state machine replication are central to distributed systems. At its core, consensus allows a set of servers, even if some of them are faulty, to provide the same abstraction as that of a single server executing commands. The servers need to maintain two essential properties: (i) safety: (non-faulty) servers execute the same ordered set of commands, (ii) liveness: a command sent by a client is eventually executed by the (non-faulty) servers. Companies such as Google and Amazon deploy such protocols to ensure up-time despite crash faults. In a slightly different vein, in cryptocurrencies such as Bitcoin, participants agree on an ordered set of monetary transactions despite some arbitrarily malicious participants.
In this course, we will learn consensus protocols under different settings. The course will be roughly partitioned into two halves: traditional consensus protocols, and the protocols inspired by Bitcoin. We will focus on the different settings under which these protocols will be run: (i) Timing models: synchrony, asynchrony, partial synchrony, (ii) Fault models: crash faults, omission faults, Byzantine faults, (ii) adversarial adaptivity: static, adaptive. We will learn certain impossibility results as well as well-known protocols in this space (such as Paxos, PBFT, Dolev-Strong). We will then discuss Bitcoin (and Nakamoto consensus), which allows consensus even when participants may not know each other. We will cover variants of the Nakamoto protocol, proof-of-stake, attacks on Bitcoin, as well as works on anonymity and privacy.