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