| 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 t-Resilient 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 test-and-set. | |||
| 9 | 2/12/2013 | RMW (read-modify-write) 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. 2-processor case. n-processor 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 | Mid-term exam I | |||
| 14 | 2/28/2013 | Distributed shared memory. Memory consistency models. | Slides by Prof. Sarita Adve | A tutorial | |
| 15 | 3/5/2013 | Fault-tolerant simulations of read/write objects | Chpater 10 (proofs of correctness of simulation algorithms omitted) slides by Prof. Welch | ||
| 16 | 3/7/2013 | Fault-tolerant 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 -- make-up 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 | Mid-term exam II | |||
| 23 | 4/9/2013 | Ben-Or's Randomized consensus algorithm. Topological approach to computability in distributed computing. |
The correctness proof of Ben-Or'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. System-level diagnosis under the PMC (Preparata-Metze-Chien) model: Necessary and sufficient conditions for t-diagnosability (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 V-V1-V2 to a node in V1-V2 or a node in V2-V1. 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 | System-level diagnosis. Communication complexity/capacity of Byzantine consensus/broadcast. | Sections 1, 2, 3, 4 and 5 of Complexity of Multi-Value 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 left-side column of fifth page of
Completeness theorems for non-cryptographic fault-tolerant distributed computation, Ben-Or, Goldwasser, Wigderson, 1988. Sections 1, 2, 3 of Transactional memory: architectural support for lock-free 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, C-Y 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 multi-party computation made simple, Ueli Maurer, 2006. | |
| Make-up 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 Multi-Value Byzantine Agreement, Liang and Vaidya, 2010. Sections 1 and 2 of Byzantine Broadcast in Point-to-Point Networks using Local Linear Coding Sections 1, 2, 3, 4 of Multiparty Equality Function Computation in Networks with Point-to-Point Links | ||
| 29 | 4/30/2013 | Talks by Ali El Gamal and Junle Qian |
Sections 1 and 2 (pages 225-235) 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 |