Lecture Summary and Readings
ECE 526 Distributed Algorithms (Spring 2013)

Lecture Date TopicsRequired ReadingsAlternative Readings for corresponding book chapters Other information
1 1/15/2013
  • Course handout. Course introduction.
  • Message passing and shared memory models. Synchrony and asynchrony. Fault models: Crash and Byzantine.
  • Happens before relation. Logical and vector clocks. Consistent state.
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.
  • Chapter 4 (Multual Exclusion in Shared Memory) of textbook
  • Slides set 1, set 2, set 3
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
  • Lower bound on number of read/write registers for any deadlock-free algorithm. Fast mutual exclusion.
  • Clock synchronization.
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/2013CLASS CANCELLED -- make-up class to be scheduled
21 4/2/2013 Leader election Section 3.4 (except Section 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

Return to ECE 526 home page