COSC 373: Distributed Algorithms
course materials for Spring 2022
Welcome to the Spring 2022 (and inaugural) edition of COSC 373: Distributed Algorithms! Here, you will find links to course materials and assignments. Please start by reading the course syllabus.
Meetings
- Lecture: T/Th 10:00–11:20, SCCE A131
- Office Hours: TBD
Resources
Primary Texts:
- Distributed Algorithms by Hirvonen and Suomela available online
- see also Jukka Suomela’s course website
- Distributed Network Algorithms by Pandurangan available online
- Principles of Distributed Computing (Lecture Notes) by Wattenhofer available online
Standard References:
- Distributed Algorithms by Lynch (Chapters 1 through 4)
- Distributed Computing: A Locality-Sensitive Approach by Peleg
Lecture Materials and Assignments
Lecture Materials
- Lecture 01 (02/08)
- Read: course syllabus
- Watch: distributed algorithms introduction by Jukka Suomela. Our course is similar in spirit to Jukka’s course, but will differ somewhat in the choice of topics and presentation.
- Lecture 01 Slides (pdf)
- Lecture 02 (02/10)
- Read: College Admissions and the Stability of Marriage by Gale and Shapley
- Lecture 02 Slides (pdf)
- Lecture 03 (02/15)
- Read: Hirvonen and Suomela, PN Model Sections 3.1–3.3 (available here)
- Watch: PN Model video by Jukka Suomela
- Lecture 03 Slides (pdf)
- Lecture 04 (02/17)
- Read: Hirvonen and Suomela, Section 3.5 Maximal Matching in Two-Colored Graphs (available here)
- Lecture 04 Slides (pdf)
- Lecture 05 (2/22)
- Lecture 06 (2/24)
- Lecture 07 (3/01)
- Lecture 07 Slides (pdf)
- Read: Hirvonen and Suomela CONGEST Model Sections 5.1–5.6 (available here)
- Lecture 08 (3/03)
- Lecture 08 Slides (pdf)
- Watch: All Pairs Shortest Paths (YouTube link)
- Read: Hirvonen and Suomela All Pairs Sortest Paths Section 5.7 (available here)
- Lecture 09 (3/08)
- Lecture 09 Slides (pdf)
- Read: Pandurangan Section 7.1 Gallager-Humblet-Spira (GHS) Algorithm (available here)
- Lecture 10 (3/10)
- Lecture 10 Slides (pdf)
- Read: Hirvonen and Suomela CONGEST Model Sections 5.1–5.6 (available here)
- Lecture 11 (3/22)
- Lecture 12 (3/24)
- Lecture 13 (3/29)
- Lecture 14 (3/31)
- Lecture 15 (4/05)
- Lecture 16 (4/07)
- Lecture 17 (4/12)
- Lecture 18 (4/14)
Assignments
- Assignment 1 (due: Friday, 2/25 by 5:00pm)
- Assignment 2 (due: Friday, 3/11 by 5:00pm)
- Assignment 3 (due: Friday, 4/01 by 5:00pm)
- Assignment 4 (due: Friday 4/15 by 5:00pm)
Quizzes
- Quiz 01 (due: Friday, 3/04 by 5:00pm)
- Quiz 02 (due: Friday, 3/25 by 5:00pm)
Quiz 03 (forthcoming) (due: Friday, 4/08 by 5:00pm)- Quiz/Exam 04 (due: Friday, 4/22 by 11:59pm)