CS 142, Fall 2019

Distributed Computing
Instructors Richard Murray (CMS) Mani Chandy (CMS) Lectures: MW, 9-10 am, 213 Annenberg Office hours: by appointment	Teaching assistants Prithvi Akella (ME), Tung Phan (ME) Problem solving sessions: Fri, 9 am, 213 Annenberg Office hours: Sun, 5-6 pm, Mon, 5-6 pm and Tue, 5-6 pm; 243 Annenberg Online resources: Piazza] (Q&A forum), Moodle (HW submission)

---

Course description CS 142. Distributed Computing. 9 units (3-0-6); first term. Prerequisites: CS 24, CS 38. Fundamental concepts for the design and analysis of distributed systems and algorithms, including reasoning about distributed programs, handling the lack of global time and global state, achieving distributed consensus in the presence of faults and asynchrony, and designing fault-tolerance for distributed systems. Review of state-of-the-art distributed systems, particularly cloud computing systems. Instructor: Murray/Chandy.

Course announcements 9 Oct 2019: HW #2 has been posted; due 16 Oct (Wed) at 2 pm 2 Oct 2019: HW #1 has been posted; due 9 Oct (Wed) at 2 pm 29 Sep 2019: Monday lecture posted + Piazza signups created (if you didn't get added, sign up using the link above) 21 Sep 2019: web site under construction; use with care

Course syllabus and schedule

Lecture Schedule

Date	Topic	Reading/Homework
W1 (30 Sep)	Motivation, course admin Logic and computation Propositional logic, guarded command programs	Sivilotti, Chapters 1 and 2 HW #1 due on 9 Oct Mon lecture slides Wed lecture slides Fri recitation slides
W2 (7 Oct)	Specifications and proofs Program properties (invariants, safety, liveness) Simple examples and proofs of correctness	Sivilotti, Chapters 3 and 4 HW #2 due on 16 Oct Mon lecture slides Wed lecture slides
W3 (14 Oct)		HW #3 due on 23 Oct Mon lecture slides Wed lecture slides
W4 (21 Oct)	Time, clocks Gossip algorithms	Sivilotti, Chapter 5 and 6 HW #4 due on 30 Oct Mon lecture slides Wed lecture slides
W5 (28 Oct)	Mutual exclusion	Midterm office hours: Fri, 4-6 pm (213 ANB) and Sun, 4-6 pm (107 ANB) Sivilotti, Chapter 7 Midterm: out 30 Oct, due 5 Nov Mon lecture slides Fri lecture slides
W6 (4 Nov) KMC	Dining philosophers	Sivilotti, Chapter 8 HW #5 due on 13 Nov Mon lecture slides Wed lecture slides
W7 (11 Nov) RMM/KMC	Specifications, refinement, program composition Snapshots	Chandy and Misra, Chapter 7 Chandy and Misra, Chapter 12 (optional) Sivilotti, Chapter 9 HW #6 due on 20 Nov Mon lecture slides Wed lecture slides
W8 (18 Nov) KMC	Byzantine agreement and the PAXOS algorithm	Sivilotti, Ch 12 HW #7 due on 27 Nov Mon lecture slides - Snapshots Mon lecture slides - Byzantine Agreement Wed lecture slides Paxos Made Simple (Lamport, 2001) HW #8 due on 6 Dec (Fri) Mon lecture slides No office hours on 27 Nov (Sun) Office hours: 5 Dec (Thu), 5-6 pm, 243 ANB
W9 (25 Nov) KMC
W10 (2 Dec)	Distributed consensus and distributed ledger	Bitcoin: A Peer-to-Peer Electronic Cash System Bitcoin and Cryptocurrency Technologies, Narayanan et al, 2017. Chapter 2 Mon lecture slides Wed lecture slides Fri review slides Final: out 6 Dec, due 13 Dec @ 5 pm Finals week office hours 8 Dec (Sun), 5-6 pm, 106 ANB 9 Dec (Mon), 5-6 pm, 243 ANB 10 Dec (Tue), 5-6 pm, 243 ANB

Grading

The final grade will be based on homework sets, a midterm exam, and a final exam:

• Homework (50%): Homework sets will be handed out weekly and due on Wednesdays by 2 pm (submitted via Moodle). Each student is allowed up to two extensions of no more than 2 days each over the course of the term. Homework turned in after Friday at 2 pm or after the two extensions are exhausted will not be accepted without a note from the health center or the Dean.
• Midterm exam (20%): A midterm exam will be handed out at the beginning of midterms period (25 Oct) and due at the end of the midterm examination period (1 Nov). The midterm exam will be open book (textbook and course notes OK: access to the Internet is not allowed).
• Final exam (30%): The final exam will be handed out on the last day of class (1 Dec) and due at the end of finals week. The final exam will be open book (textbook and course notes OK: access to the Internet is not allowed).

Collaboration Policy

• Collaboration on homework assignments is encouraged. You may consult outside reference materials, other students, the TA, or the instructor, but you cannot consult homework solutions from prior years and you must cite any use of material from outside references. All solutions that are handed in should be written up individually and should reflect your own understanding of the subject matter at the time of writing.
• No collaboration is allowed on the midterm or final exams.

Course Text and References

The primary course text is

• P. Sivilotti, Introduction to Distributed Systems, Course notes, 2007.

The following additional references may also be useful:

• K.M. Chandy and J. Misra, Parallel Program Design: A Foundation, Addison-Wesley, 1988
• M. Singhal and N. G. Shivaratri. Advanced Concepts in Operating Systems. McGraw-Hill, 1994