Lecture  Date  Topics  Required Readings  Alternative Readings for corresponding book chapters  Other information 
1  1/15/2013 


 
2  1/17/2013  Distributed snapshots. Checkpointing and rollback recovery. Consensus with crash failures. 
 A Simple Bivalency Proof that tResilient Consensus Requires t + 1 Rounds, Aguilera and Toueg, Information Processing Letters, August 1999.  
3  1/22/2013  f+1 lower bound on number of rounds. Consensus with Byzantine failures: 3f+1 lower bound on number of nodes. Phase King algorithm for Byzantine consensus. 
 
4  1/24/2013  Phase King algorithm for Byzantine consensus. Byzantine General's problem. Impossibility of consensus in asynchronous systems with failure (FLP result). 

slides from the web  Byzantine Generals slides from the web  impossibility proof  
5  1/29/2013  Consensus. Average consensus. Matrix representation of linear iterations for consensus and average consensus: row stochastic matrices for consensus, and doubly stochastic matrices for average consensus. 
 Via internet search, you will be able to find many papers that address consensus and average consensus.  
6  1/31/2013  Coefficents of ergodicity for stochastic matrices. Proof of correctness of convergence and average consensus. Using column stochastic matrices, and use of "parallel iterations" to achieve average consensus using "ratio" of the two parallel iterations.  
7  2/5/2013  Average consensus over lossy links. Iterative computation of PageRank. Algorithms for approximate Byzantine consensus in a complete graph with 3f+1 nodes. A simpler iterative approximate Byzantine consensus algorithm for complete graphs with 5f+1 nodes. 
 
8  2/7/2013  Asynchronous Byzantine consensus. Mutual exclusion (mutex) in shared memory. Mutex using testandset.  
9  2/12/2013  RMW (readmodifywrite) variables. Mutex using a virtual queue structure. Lower bound on number of memory states for mutex with bounded waiting. Bakery algorithm using read/write registers. Bounded waiting mutex for two processors, using variables W[0], W[1] and priority.  
10  2/14/2013 

Sections 6.3.2 through 6.3.6 of textbook. slides on clock synchronization  
11  2/19/2013  Clock synchronization. 2processor case. nprocessor case.  
12  2/21/2013  Totally ordered broadcast. Distributed shared memory. Memory consistency models. 
Sections 9.1, 9.2 and 9.3 of the textbook. For totally ordered broadcast, see relevant sections in Chapter 8 of the textbook. slides on shared memory  
13  2/26/2013  Midterm exam I  
14  2/28/2013  Distributed shared memory. Memory consistency models.  Slides by Prof. Sarita Adve  A tutorial  
15  3/5/2013  Faulttolerant simulations of read/write objects 
Chpater 10 (proofs of correctness of simulation algorithms omitted) slides by Prof. Welch  
16  3/7/2013  Faulttolerant simulations of read/write objects 
Chpater 10 (proofs of correctness of simulation algorithms omitted) slides by Prof. Welch  
17  3/12/2013  Byzantine vector consensus  Byzantine vector consensus, Vaidya and Garg, 2013.  
18  3/14/2013 
Byzantine vector consensus (conclusion of the proof) Please also attend the 10:00 a.m. seminar by Matei Zaharia in room 2405 Siebel Center.  
19  3/26/2013  Leader election in a ring.  Sections 3.1, 3.2, 3.3 of the textbook.  
20  3/28/2013  CLASS CANCELLED  makeup class to be scheduled  
21  4/2/2013  Leader election  Section 3.4 (except Section 3.4.2.3) of the textbook.  
22  4/4/2013  Midterm exam II  
23  4/9/2013  BenOr's Randomized consensus algorithm. Topological approach to computability in distributed computing. 
The correctness proof of BenOr's randomized consensus algorithm,
Marcos K. Aguilera, Sam Toueg. Section 1 through 6.1 of Computability in Distributed Computing: a Tutorial by Maurice Herlihy, Sergio Rajsbaum, and Michel Raynal (slides)  
24  4/11/2013  Computability in Distributed Computing. Systemlevel diagnosis under the PMC (PreparataMetzeChien) model: Necessary and sufficient conditions for tdiagnosability (centralized and distributed diagnosis). Centralized diagnosis: given two sets V1 and V2 of size at most t each, there must be a directed link (edge) from VV1V2 to a node in V1V2 or a node in V2V1. Distributed diagnosis: node connectivity of the test graph must be at least t. 
Material up to and including proof of Theorem 1
from Characterization of Connection Assignment of Diagnosable Systems,
Hakimi and Amin.  
25  4/16/2013  Systemlevel diagnosis. Communication complexity/capacity of Byzantine consensus/broadcast.  Sections 1, 2, 3, 4 and 5 of Complexity of MultiValue Byzantine Agreement, Liang and Vaidya, 2010.  slides, PPT slides  
26  4/18/2013  Talks by Fred Douglas and Long Kai (Transactional memory) 
First four pages and leftside column of fifth page of
Completeness theorems for noncryptographic faulttolerant distributed computation, BenOr, Goldwasser, Wigderson, 1988. Sections 1, 2, 3 of Transactional memory: architectural support for lockfree data structures, Maurice Herlihy and J. Eliot B. Moss, 20th annual international symposium on computer architecture (ISCA'93).  
27  4/23/2013  Talks by Zhuotao Liu and Jiangxiong Gao  From the following paper, you may omit the Appendix, the proofs of Theorems 3, 6 and proofs of Lemmas 4, 5: Broadcast in Radio Networks Tolerating Byzantine Adversarial Behavior, CY Koo, PODC 2004. 
NOT REQUIRED FOR EXAM:
Sequential Specification of Transactional Memory Semantics  
28  4/25/2013  Talks by Philbert Lin and Srikanth Srungarapu  Paxos made simple  NOT INCLUDED FOR EXAM: Secure multiparty computation made simple, Ueli Maurer, 2006.  
Makeup class  4/25/2013 
Communication complexity/capacity of Byzantine consensus/broadcast. Communication complexity of equality function. 
Sections 1, 2, 3, 4 and 5 of
Complexity of MultiValue Byzantine Agreement, Liang and Vaidya, 2010. Sections 1 and 2 of Byzantine Broadcast in PointtoPoint Networks using Local Linear Coding Sections 1, 2, 3, 4 of Multiparty Equality Function Computation in Networks with PointtoPoint Links  
29  4/30/2013  Talks by Ali El Gamal and Junle Qian 
Sections 1 and 2 (pages 225235) of Unreliable failure detectors for reliable distributed systems 
NOT INCLUDED FOR EXAM:
On the Complexity of Radio Communication and Deterministic Broadcasting Time in Radio Networks of Unknown Topology 