Difference between revisions of "CS 142, Fall 2019"

From MurrayWiki
Jump to: navigation, search
m (Lecture Schedule)
 
(42 intermediate revisions by 2 users not shown)
Line 8: Line 8:
 
* Richard Murray (CMS)
 
* Richard Murray (CMS)
 
* Mani Chandy (CMS)
 
* Mani Chandy (CMS)
* Lectures: MW, 9-10 am, 105 Annenberg
+
* Lectures: MW, 9-10 am, 213 Annenberg
 
* Office hours: by appointment
 
* Office hours: by appointment
 
| width=50% |  
 
| width=50% |  
 
=== Teaching assistants ===
 
=== Teaching assistants ===
 
* Prithvi Akella (ME), Tung Phan (ME)
 
* Prithvi Akella (ME), Tung Phan (ME)
* Problem solving sessions: Fri, 9 am, 105 Annenberg
+
* Problem solving sessions: Fri, 9 am, 213 Annenberg
* Office hours: TBD
+
* Office hours: Mon, 5-6 pm and Tue, 5-7 pm; 243 Annenberg
* Online resources: [[http:piazza.com/caltech/fall2019/cs142|Piazza]] (Q&A forum), [https://courses.caltech.edu/course/view.php?id=3539 Moodle] (HW submission)
+
* Online resources: [https://piazza.com/caltech/fall2019/cs142 Piazza]] (Q&A forum), [https://courses.caltech.edu/course/view.php?id=3539 Moodle] (HW submission)
 
|}
 
|}
 
<hr>
 
<hr>
Line 21: Line 21:
 
|- valign=top
 
|- valign=top
 
| width=50% |
 
| width=50% |
 +
 
=== Course description ===
 
=== 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.  
 
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.  
 
| width=50% |
 
| width=50% |
 
=== Course announcements ===
 
=== Course announcements ===
* 6 Nov 2017, 5:30 pm: updated copies of lecture 7.1 slides with some small corrections are posted.
+
* 9 Oct 2019: HW #2 has been posted; due 16 Oct (Wed) at 2 pm
* 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).
+
* 2 Oct 2019: HW #1 has been posted; due 9 Oct (Wed) at 2 pm
* 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
+
* 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
 
|}
 
|}
  
Line 33: Line 35:
  
 
=== Lecture 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)
 
  
 
{| class="mw-collapsible wikitable" border=1 cellpadding=5
 
{| class="mw-collapsible wikitable" border=1 cellpadding=5
Line 49: Line 44:
 
| W1 (30 Sep)
 
| W1 (30 Sep)
 
|  
 
|  
 +
* Motivation, course admin
 
* Logic and computation
 
* Logic and computation
* Motivation, course admin
 
 
* Propositional logic, guarded command programs
 
* Propositional logic, guarded command programs
 
|  
 
|  
 
* Sivilotti, Chapters 1 and 2
 
* Sivilotti, Chapters 1 and 2
* HW #1 due on 9 Oct
+
* {{CS 142 pdf|fa19|hw1-fa19.pdf|HW #1}} due on 9 Oct
<!--
+
* {{CS 142 pdf|fa19|L1-1_intro-30Sep2019.pdf|Mon lecture slides}}
* Mon lecture slides
+
* {{CS 142 pdf|fa19|L1-2_computation-02Oct2019.pdf|Wed lecture slides}}
* Wed lecture slides
+
* {{CS 142 pdf|fa19|L1-3_predicates-04Oct2019.pdf| Fri recitation slides}}
* Fri lecture slides
+
-->
+
 
|- valign=top
 
|- valign=top
 
| W2 (7 Oct)  
 
| W2 (7 Oct)  
Line 68: Line 61:
 
|  
 
|  
 
* Sivilotti, Chapters 3 and 4
 
* Sivilotti, Chapters 3 and 4
* HW #2 due on 16 Oct
+
* {{CS 142 pdf|fa19|hw2-fa19.pdf|HW #2}} due on 16 Oct
 +
* {{CS 142 pdf|fa19|L2-1_reasoning-07Oct2019.pdf|Mon lecture slides}}
 +
* {{CS 142 pdf|fa19|L2-2_safety-09Oct2019.pdf|Wed lecture slides}}
 
<!--
 
<!--
* Mon lecture slides
 
* Wed lecture slides
 
 
* Fri lecture slides
 
* Fri lecture slides
 
-->
 
-->
Line 77: Line 70:
 
| W3 (14 Oct)
 
| W3 (14 Oct)
 
|
 
|
* HW #3 due on 23 Oct
+
* {{CS 142 pdf|fa19|hw3-fa19.pdf|HW #3}}  due on 23 Oct
 +
* {{CS 142 pdf|fa19|L3-1_progress-14Oct2019.pdf|Mon lecture slides}}
 +
* {{CS 142 pdf|fa19|L3-2_examples-16Oct2019.pdf|Wed lecture slides}}
 
<!--
 
<!--
* Mon lecture slides
 
* Wed lecture slides
 
 
* Fri lectures slides
 
* Fri lectures slides
 
-->
 
-->
Line 90: Line 83:
 
|  
 
|  
 
* Sivilotti, Chapter 5 and 6
 
* Sivilotti, Chapter 5 and 6
* HW #4 due on 30 Oct
+
* {{CS 142 pdf|fa19|hw4-fa19.pdf|HW #4}}  due on 30 Oct
<!--
+
* {{CS 142 pdf|fa19|L4-1_clocks-21Oct2019.pdf|Mon lecture slides}}
* Mon lecture slides
+
* {{CS 142 pdf|fa19|L4-2_diffusing-23Oct2019.pdf|Wed lecture slides}}
* Wed lecture slides
+
-->
+
 
|- valign=top
 
|- valign=top
 
| W5 (28 Oct)
 
| W5 (28 Oct)
Line 100: Line 91:
 
* Mutual exclusion
 
* Mutual exclusion
 
||
 
||
* Midterm office hours: TBD
+
* Midterm office hours: Fri, 4-6 pm (213 ANB) and Sun, 4-6  pm (107 ANB)
 
<!--
 
<!--
 
** Friday, 3-5 pm, 107 ANB
 
** Friday, 3-5 pm, 107 ANB
Line 107: Line 98:
 
* Sivilotti, Chapter 7
 
* Sivilotti, Chapter 7
 
* Midterm: out 30 Oct, due 5 Nov
 
* Midterm: out 30 Oct, due 5 Nov
<!--
+
* {{CS 142 pdf|fa19|L5-1_mutex-28Oct2019.pdf|Mon lecture slides}}
* Mon lecture slides
+
* {{CS 142 pdf|fa19|L5-2_mutex-01Nov2019.pdf|Fri lecture slides}}
* Wed lecture slides
+
-->
+
 
|- valign=top
 
|- valign=top
 
| W6 (4 Nov) <br> KMC
 
| W6 (4 Nov) <br> KMC
 
|  
 
|  
* Specifications, refinement, dining philosophers
+
* Dining philosophers
 
|  
 
|  
 
* Sivilotti, Chapter 8
 
* Sivilotti, Chapter 8
* Chandy and Misra, Ch 7 & 12|  
+
* {{CS 142 pdf|fa19|hw5-fa19.pdf|HW #5}} due on 13 Nov
* HW #5 due on 13 Nov
+
* {{CS 142 pdf|fa19|L6-1_philosophers-04Nov2019.pdf|Mon lecture slides}}
<!--
+
* {{CS 142 pdf|fa19|L6-2_philosophers-06Nov2019.pdf|Wed lecture slides}}
* Mon lecture slides
+
* Wed lecture slides
+
-->
+
 
|- valign=top
 
|- valign=top
| W7 (11 Nov)
+
| W7 (11 Nov) <br> RMM/KMC
 
|
 
|
 +
* Specifications, refinement, program composition
 
* Snapshots
 
* Snapshots
 
|
 
|
 +
* Chandy and Misra, Chapter 7
 +
* Chandy and Misra, Chapter 12 (optional)
 
* Sivilotti, Chapter 9
 
* Sivilotti, Chapter 9
* HW #6 due on 20 Nov
+
* {{CS 142 pdf|fa19|hw6-fa19.pdf|HW #6}}  due on 20 Nov
 +
* {{CS 142 pdf|fa19|L7-1_specifications-11Nov2019.pdf|Mon lecture slides}}
 +
* {{CS 142 pdf|fa19|L7-2_snapshots-13Nov2019.pdf|Wed lecture slides}}
 
<!--
 
<!--
* Mon lecture slides
 
 
* Wed lecture slides
 
* Wed lecture slides
 
-->
 
-->
Line 141: Line 131:
 
* Sivilotti, Ch 12
 
* Sivilotti, Ch 12
 
* Paxos Made Simple (Lamport, 2001)
 
* Paxos Made Simple (Lamport, 2001)
* HW #7 due on 27 Nov
+
* {{CS 142 pdf|fa19|hw7-fa19.pdf|HW #7}}  due on 27 Nov
 
<!--
 
<!--
 
* Mon lecture slides
 
* Mon lecture slides
 
* Wed lecture slides
 
* Wed lecture slides
 +
-->
 +
* {{CS 142 pdf|fa19|hw8-fa19.pdf|HW #8}}  due on 6 Dec (Fri)
 +
<!--
 
* Mon (25 Nov) lecture slides
 
* Mon (25 Nov) lecture slides
 +
* Wed (27 Nov) lecture slides
 
-->
 
-->
* No class on 27 Nov (Wed)
 
 
|- valign=top
 
|- valign=top
| W9 (25 Nov)  
+
| W9 (25 Nov) <br> KMC
 
|- valign=top
 
|- valign=top
 
| W10 (2 Dec)
 
| W10 (2 Dec)
Line 168: Line 161:
 
* Bitcoin: A Peer-to-Peer Electronic Cash System
 
* Bitcoin: A Peer-to-Peer Electronic Cash System
 
* Bitcoin and Cryptocurrency Technologies, Narayanan et al, 2017. Chapter 2
 
* Bitcoin and Cryptocurrency Technologies, Narayanan et al, 2017. Chapter 2
* HW #8 due on 3 Dec (Sun)
 
 
<!--
 
<!--
 
* Mon (2 Dec) lecture slides
 
* Mon (2 Dec) lecture slides
Line 189: Line 181:
 
=== Course Text and References ===
 
=== Course Text and References ===
 
The primary course text is  
 
The primary course text is  
* P. Sivilotti, Introduction to Distributed Systems, Course notes, 2007.
+
* P. Sivilotti, {{CS 142 pdf|fa19|sivilotti-distributed_systems.pdf|Introduction to Distributed Systems}}, Course notes, 2007.
 
The following additional references may also be useful:
 
The following additional references may also be useful:
 
* K.M. Chandy and J. Misra, Parallel Program Design: A Foundation, Addison-Wesley, 1988
 
* 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
  
 
[[Category:Courses]]
 
[[Category:Courses]]

Latest revision as of 04:48, 13 November 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: Mon, 5-6 pm and Tue, 5-7 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
W2 (7 Oct)
  • Specifications and proofs
  • Program properties (invariants, safety, liveness)
  • Simple examples and proofs of correctness
W3 (14 Oct)
W4 (21 Oct)
  • Time, clocks
  • Gossip algorithms
W5 (28 Oct)
  • Mutual exclusion
W6 (4 Nov)
KMC
  • Dining philosophers
W7 (11 Nov)
RMM/KMC
  • Specifications, refinement, program composition
  • Snapshots
W8 (18 Nov)
KMC
  • Byzantine agreement and the PAXOS algorithm
  • Sivilotti, Ch 12
  • Paxos Made Simple (Lamport, 2001)
  • HW #7 due on 27 Nov
  • HW #8 due on 6 Dec (Fri)
W9 (25 Nov)
KMC
W10 (2 Dec)
  • Distributed consensus and distributed ledger
  • Modified office hours: TBD
  • Bitcoin: A Peer-to-Peer Electronic Cash System
  • Bitcoin and Cryptocurrency Technologies, Narayanan et al, 2017. Chapter 2
  • Final: out 6 Dec, due 13 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

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