Course Logistics
Clemens 322
thayes2@buffalo.edu
Davis 113R
First meeting: Monday, August 24.
What this course is about
We will study the design and analysis of algorithms for parallel and distributed systems. We will see how algorithm design changes when many processors cooperate or when machines communicate over a network.
Topics include parallel computation, message-passing algorithms, clocks and causality, distributed snapshots and leader election, fault tolerance and consensus, peer-to-peer systems, and blockchains. Depending on the model, we will care about running time, work, communication, synchronization, and other relevant costs.
Semester Schedule
The schedule is tentative; topics may shift by a class or two. University dates below are based on UB's Fall 2026 academic calendar.
| Week | Dates | Topics | Assessment / other |
|---|---|---|---|
| 1 | Aug 24–28 | Parallel computation models; PRAM (CREW/CRCW); work and span | Homework 1 assigned |
| 2 | Aug 31–Sep 4 | Parallel algorithms: prefix/scan, reductions, sorting networks | Homework practice |
| 3 | Sep 7–11 | Message-passing models and network topologies | Monday, Sep 7: Labor Day holiday; Assessment 1 |
| 4 | Sep 14–18 | Lamport clocks, vector clocks, causal ordering | Homework practice |
| 5 | Sep 21–25 | Global state and snapshots; distributed mutual exclusion | Assessment 2 |
| 6 | Sep 28–Oct 2 | Distributed leader election; review for Midterm 1 | Midterm 1 |
| 7 | Oct 5–9 | Crash and Byzantine fault models; synchronous consensus | Homework practice |
| 8 | Oct 12–16 | Asynchronous consensus; FLP impossibility result | Oct 12–13: Fall Break; classes resume Wed Oct 14; Assessment 3 |
| 9 | Oct 19–23 | Crash fault tolerance; Paxos, Raft, and distributed commit | Homework practice |
| 10 | Oct 26–30 | Byzantine fault tolerance; Byzantine agreement protocols | Assessment 4 |
| 11 | Nov 2–6 | Peer-to-peer networks; DHTs (including Chord); review for Midterm 2 | Midterm 2 |
| 12 | Nov 9–13 | Blockchain basics; Merkle trees; UTXO and account models | Homework practice |
| 13 | Nov 16–20 | Blockchain consensus; proof of work and proof of stake | Assessment 5 |
| 14 | Nov 23–27 | Distributed ledgers, smart contracts, and scalability | Nov 25–28: Thanksgiving Break; Monday Nov 23 is the only class meeting this week |
| 15 | Nov 30–Dec 4 | Consistency models: eventual consistency and linearizability; cumulative review | Assessment 6 and final-exam review |
| Last class | Dec 7 | Final review / wrap-up | UB's last day of classes |
| Finals | Dec 9–16 | Final examination period | Comprehensive Final Exam; exact day/time per UB final-exam schedule |
UB's standard Fall 2026 calendar has its last day of classes on Monday, December 7, a reading day on Tuesday, December 8, and final examinations from December 9 through December 16.
Assessment
Homework is practice and is not graded. You may use notes, the internet, and AI tools while working on it. The in-class assessments and exams test whether you can solve related problems on your own.
| Component | Weight | Purpose |
|---|---|---|
| In-class assessments (6) | 20% | Short, individual problems based on recent homework and lectures. |
| Top Hat checks | 10% | Low-stakes questions during class that provide practice and feedback. |
| Midterm 1 | 20% | In-class exam covering the first part of the course. |
| Midterm 2 | 20% | In-class exam covering the middle part of the course. |
| Final exam | 30% | Comprehensive in-class final exam. |
| Homework | 0% | Regular practice for the in-class assessments and exams. |
How homework and assessments fit together
A typical cycle is: learn a topic in lecture, work through related homework, and then solve new problems on an in-class assessment.
Important: In-class assessments and exams are individual work. No internet, AI tools, notes, or collaboration are permitted unless explicitly authorized.
Exams
There are two midterm exams and one comprehensive final exam. Expect questions on algorithm design, analysis, correctness, impossibility results, and the computational model under discussion.
Course Policies
Prerequisite background
You should already be comfortable with asymptotic notation, recurrence equations, basic data structures, and standard sequential algorithms, including fundamental graph and tree algorithms. This course builds on that material rather than reteaching it from scratch.
Academic integrity
All graded in-class work must be your own work. Homework may use outside resources, including AI assistance. AI assistance is not permitted on an in-class assessment or exam unless explicitly authorized.
All students are expected to follow University at Buffalo and department policies concerning academic integrity.
Course materials
Please do not redistribute course-specific materials, assessments, solutions, or recordings without permission.
Resources
Textbook
Algorithms Sequential & Parallel, 3rd edition, R. Miller and L. Boxer, Cengage Learning, 2013.
Lecture notes and problem sets will be posted through the course LMS.
Communication
Use the course Piazza space for questions of general interest to the class. Use email for private matters.