Lecture Summary and Readings
ECE 526 Distributed Algorithms (Fall 2016)

Lecture Date TopicsRequired Readings Other information
1 8/22/2016
  • Course handout. Course introduction.
  • Message passing and shared memory models. Synchrony and asynchrony. Fault models: Crash and Byzantine.
  • Fault-tolerant consensus.
 Chapters 1 and 5 of textbook
Slides: Chapter 1, Consensus		 How to Make Chord Correct, Pamela Zave.
2 8/24/2016 Crash fault-tolerant consensus: algorithm and f+1 round lower bound. Chapter 5 of textbook
Slides: Consensus
3 8/29/2016 Byzantine fault-tolerant consensus: exponential algorithm Chapter 5 of textbook
slides
4 8/31/2016 Byzantine fault-tolerant consensus: exponential algorithm, phase king Chapter 5 of textbook
slides
5 9/7/2016 Byzantine broadcast (Byzantine Generals problem). Crash and Byzantine tolerant consensus in undirected incomplete graphs. Approximate consensus with local communication; average consensus with local communication. Byzantine Generals (you may be able to find other reading on the topic online).
6 9/12/2016 Products of stochastic matrices (delta,lambda definitions). Average consensus with row stochastic transition matrices; with column stochastic transition matrices. Iterative Byzantine consensus. Lemma 2 and related definitions from Products of indecomposable, aperiodic, stochastic matrices
Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs (the proof of sufficiency can be sampled using a transition matrix presentation discussed in Matrix Representation of Iterative Approximate Byzantine Consensus in Directed Graphs)
7 9/14/2016 Iterative Byzantine consensus. Lemma 2 and related definitions from Products of indecomposable, aperiodic, stochastic matrices
Iterative Approximate Byzantine Consensus in Arbitrary Directed Graphs (the proof of sufficiency can be sampled using a transition matrix presentation discussed in Matrix Representation of Iterative Approximate Byzantine Consensus in Directed Graphs)
8 9/19/2016 FLP impossibility result. Causality and consistent cuts. impossibility of consensus with one faulty process, Fischer, Lynch and Paterson.
Chapter 6 of textbook.
9 9/21/2016 Vector timestamps. Causality and consistent cuts. Chapter 6 of textbook (including algorithm for finding the consistent cut).
Distributed Snapshots, by Chandy and Lamport.
10 10/3/2016 Distributed shared memory. Consistency models. Linerizability, sequential consistency, causal consistency shared memory notes and associated figures
Sections 9.1, 9.2 and 9.3 of textbook (shared memory)
DSM slides by Prof. Welch
11 10/5/2016 Shared memory: Fault-tolerant simulations Chapter 10 of textbook (fault-tolerant simulations)
slides by Prof. Welch
12 10/10/2016 Shared memory: Fault-tolerant simulations Chapter 10 of textbook (fault-tolerant simulations)
slides by Prof. Welch
13 10/12/2016 Shared memory: Fault-tolerant simulations. Atomic Snapshot Object. Clock synchronization. Chapter 6 of textbook (fault-tolerant simulations)
Clock sync slides by Prof. Welch
14 10/17/2016 Clock synchronization (excluding proofs for Byzantine clock synchronization). Wait-free consensus with read/write registers. Chapter 6 of textbook (fault-tolerant simulations)
Clock sync slides by Prof. Welch
Sections 1, 2 and 3 of Closed form bounds for clock synchronization under simple uncertainty assumptions, Biaz and Welch.
Slides on wait-free consensus with read/write registers
15 10/19/2016 FIFO Queues have consensus number 2 Material related to FIFO queues from Chapter 15 and slides on wait-free hierarchy
16 10/24/2016 Wait-free hierarchy. Shared memory mutex Chapter 15 (up to and including Section 15.3.2). slides on wait-free hierarchy
Chapter 4, Slides: mutex 1, mutex 2, mutex 3
17 10/26/2016 Mutex Chapter 4, Slides: mutex 1, mutex 2, mutex 3
18 11/2/2016 Mutex. Full link reversal algorithm Chapter 4, Slides: mutex 1, mutex 2, mutex 3
First 8 pages of notes by Prof. Soma Chaudhuri
19 11/7/2016Equality function computation Sections 1,2,3,6 of Multiparty Equality Function Computation in Networks with Point-to-Point Links
 Sections 1, 2 and 5 of Nearly complete graphs decomposable into large induced matchings and their applications
20 11/9/2016Equality function computation See readings for previous lecture
21 11/14/2016Consensus: Multi-valued Byzantine consensus. Ben-Or's algorithm. Sections 1 through 5 of Complexity of Multi-Value Byzantine Agreement
Sections 1, 2, 3, 4 of Correctness Proof of Ben-Or's Randomized Consensus Algorithm
22 11/16/2016Vector consensus with Byzantine faults. Asynchronous approximate Byzantine consensus with 3f+1 processes. Sections 1 and 2 of Byzantine Vector Consensus in Complete Graphs, Vaidya and Garg.
Section 2.1 of Multidimensional Approximate Agreement in Byzantine Asynchronous Systems
Section 3 of Optimal Resilience Asynchronous Approximate Agreement
23 11/28/2016Approximate asynchronous Byzantine consensus. CRDT for a counter. See readings listed under lectures 22 and 24.
24 11/30/2016 CRDT for a counter Presentation by Marc Shapiro on CRTD up to and including the discussion of a counter implemented as a CRDT (approximately first 42 minutes of the talk). For the purpose of this course, it will suffice to understand the implementation of a counter as a CRDT. If the explanation of the counter from the talk is not clear, you can find a discussion in Section 3.1 of this paper.
25 (Review lecture 3:00 - 4:15 pm, 3081 ECEB 12/2/2016
26 12/5/2016
27 12/7/2016




Return to ECE 526 home page