Lecture | Date | Topics | Required 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. |
|
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). |
|
|
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 |