CS 142, Fall 2019

From MurrayWiki
Revision as of 02:29, 27 August 2019 by Murray (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Distributed Computing

Instructors

  • Richard Murray (CMS)
  • Mani Chandy (CMS)
  • Lectures: MW, 2-3 pm, 105 Annenberg
  • Office hours: by appointment

Teaching assistants

  • TBD
  • Problem solving sessions: Fri, 2-3 pm, 105 Annenberg
  • Office hours: TBD
  • 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

  • 6 Nov 2017, 5:30 pm: updated copies of lecture 7.1 slides with some small corrections are posted.
  • 11 Oct 2017, 4 pm: updated copies of lecture slides with some small corrections are posted (including Mani's alternative version of the proof for FindMax).
  • 4 Oct 2017: If you are having trouble submitting your set via Moodle, try this link: https://courses.caltech.edu/course/view.php?id=2761

Course syllabus and schedule

Lecture Schedule

There will be 2-3 one hour lectures per week, with the specific days varying from week-to-week. The lecture days for each week will be announced in class and posted here at least 1 week in advance.

Reading:

  • Opt = optional reading (useful if you are confused and trying to understand the basic concepts)
  • Rec = recommended reading (this is what the homework is based on)
  • Adv = advanced reading (more detailed results, useful if you are interested in learning more)
Date Topic Reading/Homework
W1 (30 Sep)
  • Logic and computation
  • Motivation, course admin
  • Propositional logic, guarded command programs
  • Sivilotti, Chapters 1 and 2
  • HW #1 due on 4 Oct
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 11 Oct
W3 (14 Oct)
  • HW #3 due on 18 Oct
W4 (21 Oct)
  • Time, clocks
  • Gossip algorithms
  • Sivilotti, Chapter 5 and 6
  • HW #4 due on 25 Oct
W5 (28 Oct)
  • Introduction to snapshots (not covered on midterm)
  • Note: No lecture on Friday
  • Midterm office hours: TBD
  • Sivilotti, Chapter 9
  • Midterm: out 25 Oct, due 31 Oct
W6 (4 Nov)
  • Mutual exclusion
  • Sivilotti, Chapter 7
  • HW #5 due on 8 Nov
W7 (11 Nov)
  • Specifications, refinement, dining philosophers
  • Sivilotti, Chapter 8
  • Chandy and Misra, Ch 7 & 12
  • HW #6 due on 15 Nov
W8 (18 Nov)
  • Byzantine agreement and the PAXOS algorithm
  • Sivilotti, Ch 12
  • Paxos Made Simple (Lamport, 2001)
  • HW #7 due on 22 Nov
W9 (25 Nov)
W10 (2 Dec)
  • Distributed consensus and distributed ledger
  • No class on 27 Nov (Wed)
  • Modified office hours: TBD
  • Bitcoin: A Peer-to-Peer Electronic Cash System
  • Bitcoin and Cryptocurrency Technologies, Narayanan et al, 2017. Chapter 2
  • HW #8 due on 3 Dec (Sun)
  • Final: out 1 Dec, due 8 Dec @ 2 pm

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