C2 – The Problem of Consensus in Distributed Systems

Agreement and consensus in distributed systems, the impossibility results, and how consensus is made possible in practice.

course of the deck

Distributed Systems (Module 1) (2nd cycle, 2022/2023) — Andrea Omicini

used in the lectures

same deck in other editions

reference publication

Paxos Made Live: An Engineering Perspective (paper in proceedings, 2007) — Tushar D. Chandra, Robert Griesemer, Joshua Redstone

Revisiting the Paxos algorithm (book chapter, 1997) — Roberto De Prisco, Butler W. Lampson, Nancy A. Lynch

Distributed Commit With Bounded Waiting (paper in proceedings, 1982) — Danny Dolev, H. Raymond Strong

Impossibility of distributed consensus with one faulty process (article in journal, 1985) — Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson

ZooKeeper: Wait-free Coordination for Internet-scale Systems (paper in proceedings, 2010) — Patrick Hunt, Mahadev Konar, Flavio P Junqueira, Benjamin Reed

The Part-Time Parliament (article in journal, 1998) — Leslie Lamport

Paxos Made Simple (article in journal, 2001) — Leslie Lamport

Fast Paxos (article in journal, 2006) — Leslie Lamport

There is More Consensus in Egalitarian Parliaments (paper in proceedings, 2013) — Iulian Moraru, David G. Andersen, Michael Kaminsky

In Search of an Understandable Consensus Algorithm (paper in proceedings, 2014) — Diego Ongaro, John K. Ousterhout

A Simple Totally Ordered Broadcast Protocol (paper in proceedings, 2008) — Benjamin Reed, Flavio P. Junqueira

Paxos Made Moderately Complex (article in journal, 2015) — Robbert Van Renesse, Deniz Altinbuken

related talk

Distributed Consensus: Making Impossible Possible (QCon London 2016, 29/03/2016) — Heidi Howard