Week 5: Consensus
- Lecture notes:
-
Consensus
-
Lecture slides
(6 per page)
- Supplemental notes – Paxos:
-
Leslie Lamport,
A Part-Time Parliament, ACM Transactions on Computer Systems 16, 2 (May 1998), 133-169.
The original Paxos Paper.
-
Leslie Lamport,
Paxos Made Simple,
Nov. 1, 2001.
-
Jonathan Kirsch and Yair Amir,
Paxos for System Builders, Technical Report CNDS-2008-2 - March 2008
Supplemental notes:
Discussion in answers.com.
Leslie Lamport, Robert Shostak, Marshall Pease,
The Byzantine Generals Problem,
SRI International
A paper on the Byzantine Generals Problem
The Byzantine Generals Problem
Notes from the University of Wisconsin - Madison
The Byzantine Generals Problem
Lampson, Butler,
How to Build a Highly Available System Using Consensus,
Microsoft Research, October 1, 1996
Iair Amir, Jonathan Kirsch,
Paxos for System Builders: An Overview,
Johns Hopkins University.
Iair Amir, Jonathan Kirsch,
Paxos for System Builders,
Johns Hopkins University, Technical Report CNDS-2008-2, March 2008.
Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson,
Impossibility of Distributed Consensus with One Faulty Process,
Journal of the Association for Computing Machinery, Volume 32, No. 2, April 1984, pp. 374-382.
Bracha, G. and Toueg, S.
Asynchronous Consensus and Broadcast Protocols, Journal of the ACM 32, 4 (October 1985), 824–840.
Buzzwords:
Validity, uniform agreement, integrity, termination, quorum
Paxos, Paxos leader, Paxos proposer, Paxos acceptor, Paxos learner,
leasing vs. locking, hierarchical leases.
