Lecture Summary and Readings
CS 425/ECE 428 Distributed Systems (Spring 2016)
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/quizzes. 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 (optional reading)
1 1/19/2016 Course handout. Course overview. What is distributed computing?
Networking Primer (TCP/IP, routing, network byte order, sockets).
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)
Group communication (maintaining group membership, how to order delivery of group multicasts).
Clock synchronization (impact of variable network delays)
Mutual exclusion (impact of lossy links) 		MP0 posted.
2 1/21/2016 Logical time. Vector clock. Chapter 14 (Time and Global States) excluding Section 14.6 (Distributed debugging omitted).
slides: logicalclocks.ppt
3 1/26/2016 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
slides: clocks.ppt
4 1/28/2016 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
5 2/2/2016 Multicast (FIFO ordering, total ordering using a sequencer, causal ordering, reliable multicast).
Shared memory: algorithms and consistency models. 		Section 15.4 except the ISIS total ordering algorithm.
slides: multicast
Shared memory notes I (revised)
Shared memory figures I (revised)
Lecture PPTX
6 2/4/2016 Shared memory: algorithms and consistency models. Permutations. Linearizability. Linearization points. Sequential consistency. Happened-before for shared memory. Shared memory notes I (revised)
Shared memory figures I (revised)
Lecture PPTX 		slides on sockets/multi-threading: pdf, ppt
7 2/9/2016 Network protocol stack. Review of shared memory consistency models. Linearization points. Shared memory notes I (revised)
Shared memory figures I (revised)
Lecture PPTX 		slides on sockets/multi-threading: pdf, ppt
8 2/11/2016 Linearization points. Eventual consistency (Reading assignment). Consensus with crash faults (two algorithms: one using sets of values, one without using sets -- see slides provided for this lecture)
9 2/16/2016 T.A. presentations: Socket programming & Multi-threading (related to programming assignments). SOCKETS AND MULTI-THREADING WILL NOT BE INCLUDED IN THE SCOPE OF THE EXAMS. Some related slides: MP1 discussion, Multi-threading, TCP sockets.
Also see the Piazza message related to this lecture.
10 2/18/2016 Crash-tolerant consensus in synchronous and asynchronous systems. Asynchronous approximate consensus with crash failures. (Byzantine broadcast NOT included for mid-term exam I.) Section 15.5 (Consensus).
Notes on approximate consensus
Algorithm 1. Algorithm 2 (from the textbook)
Approximate consensus & lower bound for Byzantine broadcast (Byzantine broadcast NOT included for mid-term exam I)
11 2/23/2016 Impossibility of consensus in asynchronous system in presence of failures (FLP impossibility result). Reliable multicast. Global states. Consistent and inconsistent cuts. Distributed snapshots.
Byzantine Generals (Byzantine generals NOT included for mid-term exam I) 		FLP impossibility slides
Reliable multicast from Section 15.4.
Multicast slides
Chapter 14 (Time and Global States) excluding Section 14.6 (Distributed debugging omitted).
Snapshots slides
Byzantine generals slides (Byzantine generals NOT included for mid-term exam I) 		FLP paper: Impossibility of distributed consensus with one faulty process
12 3/1/2016 Snapshot algorithm. Mutual exclusion (mutex) using shared memory. Mutual exclusion using message-passing: Leader-based and ring-based algorithms, Ricard-Agrawala algorithm. slides: shared memory mutex
slides: message-passing mutex
Section 15.2
13 3/3/2016 Mutual exclusion using message-passing (Maekawa's algorithm). Mutual exclusion using shared memory (test-and-set, Bakery algorithm, 2-processor algorithm). slides: shared memory mutex
14 3/8/2016 Mutual exclusion using shared memory. Failure detectors. Leader election. CAP theorem. Eventual consistency. Last-writer-wins rule. Read-Write quorums for eventual consistency.
  • slides: shared memory mutex
  • Sections 15.1 and 15.3
  • Paper by Doug Terry (see readings for Lecture 8)
  • Last-write-wins rule is explained in the last paragraph on page 6 of the shared memory notes
  • Read (R)-Write (W) quorum for eventual consistency: When a write(X,v) operation is issues, W replicas of X are written before the operation completes -- at each updated replica, the time at which the X is written is also stored. For a read(X) operation, variable X at R replicas is read, and the value with the largest of the R timestamps is returned.
Relevant slides from Fall 2015 offering of this course were used in this lecture.
15 3/10/2016 Read (R)-Write(W) Quorum for eventual consistency. Composability of linearizability. Happened-before for shared memory, and concurrent operations. Causal consistency. Hypercube topology. Shared memory notes I (revised)
Shared memory figures I (revised)
16 3/15/2016 Hypercube topology. Chord peer-to-peer network -- distributed hash table (DHT).
  • slides for p2p networks
  • Information on hypercube may be found on many online sources. Click here for one such source (omit the simulation techniques described there). You need to know how the nodes of a hypercube are numbered, how to find a route between two nodes, the relationship between the network diameter, node degree, and number of nodes in a hypercube.
  • 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.
17 3/17/2016 Transactions and Concurrency Control: ACID properties, serial equivalence (serializability), conflicts, locks and deadlocks. Sections 16.1, 16.2, 16.4, 16.5
Slides: set 1
18 3/29/2016 Optimistic concurrency control (forward and backward validation). Sections 16.5 Transactions slides set 2
Link reversal: slides 108-115 in this set
19 3/31/2016 Two-phase commit. Paxos. Sections 17.1, 17.2, 17.3.1
Paxos made simple 		slides on Paxos
20 4/5/2016 Paxos. Link reversal routing algorithm. Link reversal slides
21 4/7/2016 Symmetric and public-key cryptography. Encryption. Digital signatures. Digital certificates. (The topics on security are NOT included for mid-term exam II, but will be included for the final exam.) Relevant material in Chapter 11 in the textbook and these slides
22 4/12/2016 Self-Stabilization Solution with K-state Machines (K>N) and text prior to that in this paper by Dijkstra.
23 4/14/2016 Review for mid-term exam II
24 (no lecture today) 4/19/2016 No lecture today
25 4/21/2016 Conflict-free data types (CRDT) -- CRDT not included for the final exam video on CRDT
26 4/26/2016 Eiger key-value store (Eiger is NOT included for the final exam). Mid-term exam II solutions. Solutions for mid-term exam II video on Eiger
27 4/28/2016 Distance vector and link state routing (this topic was discussed previously, but the reading material was not listed previously) Recommended exercises (posted on April 27)
Section 3.3.5. Slides 5 to 13 in this set 		talk on Spanner
28 5/3/2016 Spanner (Spanner is NOT included for final exam). Review of some course material. Map-Reduce




Return to CS 425/ECE 428 home page