Lecture Summary and Readings
CS 425/ECE 428 Distributed Systems (Spring 2018)

Unless otherwise noted, the section/chapter numbers in the Readings below refer to the textbook sections/chapters (5th edition).
Readings that are explicitly identified as RECOMMENDED are NOT required for the purposes of exams. All other readings are REQUIRED.
Some of the topics listed for a lecture may potentially be covered in subsequent lectures.
Lecture Date TopicsRequired Readings Other information
1 1/16/2018 Course handout. Course overview. What is distributed computing?
Challenges in distributed computing using examples of distributed computing problems, such as reliability through replication (e.g., geo-replicated storage), group communication, clock synchronization, leader election, mutual exclusion.
Replicated computation (independent and correlated failures, crash versus Byzantine failure, consensus on ordering of requests).
Replicated storage (consistency models)
Clock synchronization (impact of variable network delays)
Mutual exclusion (impact of lossy links)
MP0 posted.
2 1/18/2018 Happened-before relation. Logical time. Vector clock. Chapter 14 (Time and Global States) excluding Section 14.6 (Distributed debugging omitted).
Slides: PowerPoint, PDF
3 1/23/2018 Lower bound on vector clock length. Clock synchronization. Cristian's algorithm. Chapter 14 (Time and Global States) excluding Section 14.6 (Distributed debugging omitted).
Slides: Vector length bound: PowerPoint, PDF
Slides: Clocks: PowerPoint, PDF
Homework 1
Homework 1 posted
4 1/25/2018 Clock synchronization: NTP. Multicast (FIFO ordering, total ordering using a sequencer, causal ordering, reliable multicast). Section 15.4 except the ISIS total ordering algorithm.
Slides: Multicast: PowerPoint, PDF
5 1/30/2018 Multicast (FIFO ordering, total ordering using a sequencer, causal ordering, reliable multicast). Global states, consistent and inconsistent cuts, distributed snapshots. Section 15.4 except the ISIS total ordering algorithm.
Chapter 14 (Time and Global States) excluding Section 14.6 (Distributed debugging omitted).
Slides: Multicast: PowerPoint, PDF
Slides: Snapshots: PowerPoint, PDF
Homework 2 posted
Homework 2 posted
6 2/1/2018 Consistent cuts and distributed snapshot. Shared memory: algorithms and consistency models. Shared memory notes I
Shared memory figures I
Lecture PPTX, PDF
slides on sockets/multi-threading: pdf, ppt
7 2/6/2018 Shared memory: algorithms and consistency models. Permutations. Sequential consistency. Shared memory notes I
Shared memory figures I
Lecture PPTX, PDF
8 2/8/2018 Linearizability. Linearization points. Sequential consistency. Happened-before for shared memory. Eventual consistency. CAP theorem. Eventual consistency (reading assignment). REQUIRED READING ASSIGNMENT: Replicated data consistency explained through baseball (PDF version), Doug Terry, CACM, December 2013. (1-hour video presentation by Doug Terry provides examples to illustrate the various consistency models discussed in the paper).
Shared memory notes I
Shared memory figures I
Lecture PPTX, PDF
9 2/13/2018 Consensus with crash faults (two algorithms: one using sets of values, one without using sets -- see slides provided for this lecture) Section 15.5 (Consensus). Algorithm 1 (PDF). Algorithm 2 (from the textbook) (PDF)
10 2/15/2018 Crash-tolerant consensus in synchronous and asynchronous systems. Asynchronous approximate consensus with crash failures. Section 15.5 (Consensus).
Notes on approximate consensus
Slides: Approximate consensus & lower bound for Byzantine broadcast: PDF
11 2/20/2018 Impossibility of consensus in asynchronous system in presence of failures (FLP impossibility result). Paxos protocol. FLP paper (proof of FLP result not included for exams): Impossibility of distributed consensus with one faulty process
FLP impossibility slides: PDF
Paxos Made Simple, Leslie Lamport.
12 2/22/2018 Impossibility of consensus in asynchronous system in presence of failures (FLP impossibility result). Paxos protocol. FLP paper (proof of FLP result not included for exams): Impossibility of distributed consensus with one faulty process
FLP impossibility slides: PDF
Paxos Made Simple, Leslie Lamport.
13 2/27/2018 Byzantine faults. Byzantine broadcast (Byzantine Generals). Mutual exclusion using message-passing and shared memory. Slides: Byzantine broadcast: PDF
Section 15.2
slides: shared memory mutex (PDF)
slides: message-passing mutex (PDF)
14 3/1/2018 Mutual exclusion using message-passing and shared memory. Section 15.2
slides: shared memory mutex (PDF)
slides: message-passing mutex (PDF)
3/5/2018: Mid-term exam 1. For exam scope, location and schedule information, click here
15 3/6/2018 (no lecture) No lecture today to compensate for mid-term exam 1 on March 5.
16 3/8/2018 Mutual exclusion using message-passing. Link reversal routing algorithm. Link reversal slides: PowerPoint, PDF
Section 15.2
slides: message-passing mutex (PDF)
17 3/13/2018 Hypercube topology. Chord peer-to-peer network -- distributed hash table (DHT). Required reading assignment: Sections 1, 2, 3 and 4 (except Section 4.4) of Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, SIGCOMM 2001. You may skip the theoretical proofs from this paper.
P2P networks slides: PowerPoint, PDF
18 3/15/2018 Hypercube topology. Chord peer-to-peer network -- distributed hash table (DHT). Transactions and Concurrency Control: ACID properties, serial equivalence (serializability), conflicts, locks and deadlocks. Required reading assignment: Sections 1, 2, 3 and 4 (except Section 4.4) of Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, SIGCOMM 2001. You may skip the theoretical proofs from this paper.
P2P networks slides: PowerPoint, PDF
Sections 16.1, 16.2, 16.4, 16.5
Transactions slides: PowerPoint, PDF
19 3/27/2018 Transactions and Concurrency Control: locks and deadlocks. Optimistic concurrency control (forward and backward validation). Sections 16.1, 16.2, 16.4, 16.5
Transactions slides: PowerPoint, PDF (optimistic concurrency control is not discussed in these slides).
figures
20 3/29/2018 Optimistic concurrency control (forward and backward validation). Security: symmetric key cryptography, public-private key pairs, encryption, decryption, digital signatures, digital certificates. Sections 16.1, 16.2, 16.4, 16.5
Relevant material from Chapter 11 on topics listed in the previous column in security.
slides
21 4/3/2018 Digital signature.
Exam 1 returned in class.
The following topic is NOT included for Exam 2: Equality function computation.
22 4/5/2018 Equality function computation
4/9/2018: Mid-term exam 2 For exam scope, location and schedule information, see course homepage.
23 4/10/2018 No lecture today to compensate for mid-term exam 2 on April 9, 2018.
24 4/12/2018 Distance vector routing. Dynamic source routing (DSR). Slides 14-6 to 14-10on distance vector routing in this set.
Section 3.3.5 (Routing) from the textbook.
Slides 39-51 on DSR in this set.
25 4/17/2018 Efficient timestamps for star graphs. Reading assignment: Sections 1 and 3 of Effectiveness of Delaying Timestamp Computation (you may omit the proofs in this paper) timestamp slides
26 4/19/2018 Discussion of efficient timestamps (continued from last lecture).
Byzantine vector consensus.
Sections 1 and 2 of Byzantine Vector Consensus in Complete Graphs. You won't be tested on the proofs in this paper. Slides: PowerPoint, PDF
27 4/24/2018 Bitcoin lecture by Prof Andrew Miller. Please watch video of this lecture. No other reading is assigned on Bitcoin.
28 4/26/2018 Linearizability for concurrent objects (such as concurrent queue) Notes on linearizability
29 5/1/2018 CAP Theorem Sections 1 and 2 (except the Proof Sketch) of "Perspectives on the CAP Theorem" by Gilbert and Lynch
5/11/2018: Final exam For exam scope, location and schedule information, see course homepage.
Unless otherwise noted, the section/chapter numbers in the Readings above refer to the textbook sections/chapters (5th edition).
Readings that are explicitly identified as RECOMMENDED are NOT required for the purposes of exams. All other readings are REQUIRED.


Return to CS 425/ECE 428 home page