CSCI 4510/6510: Distributed Systems and Algorithms
General Information
Instructor: Stacy Patterson (sep@cs.rpi.edu)
Instructor Office Hours: T 1pm - 3pm in Lally 301
TA: Michael Zuo (zuom@rpi.edu)
TA Office Hours: T 3pm-4pm in Amos Eaton 118, W 11am - 1pm in Lally 02
Lectures: MR 12pm - 1:50pm
Course Description
This course explores the principles of distributed systems, emphasizing fundamental issues underlying the design of such systems: communication, coordination, synchronization, and fault-tolerance. We will study key algorithms and theoretical results and explore how these foundations play out in modern systems and applications like cloud computing, edge computing, and peer-to-peer systems.
- Course Syllabus
- Gradescope (for quiz grades and written homework submission)
- Submitty (for course materials, discussion forum, and coding homework submission)
Quiz Schedule
Quizzes will be held during the scheduled lecture time.
- Quiz 1: Thursday 9/12/24
- Quiz 2: Monday 9/30/24
- Quiz 3: Monday 10/21/24
- Quiz 4: Monday 11/11/24
- Quiz 5: Thursday 12/5/24
Review Problems
Homework
The coding homework will be evaluated using Submitty’s autograding feature for networked applications. Submitty uses Docker to deploy and test your application. It is not necessary for you to use Docker to test your code, but it is a good idea. Below are instructions for configuring and using Docker, as well as instructions for replicating the Submitty test environment on your own machine.
- Basic instructions for working Docker containers and networks.
- Submitty provides a tool to automatically create Docker containers and the Docker Network, and to deploy your code to these containers. The solution_directory should be your bin directory (after running build.sh), and replace submittyrpi/csci4510:default with submittyrpi/csci4510:spring24_java
- Example knownhosts.json file
- Examples project skeletons with build.sh for compilation and run.sh to run code: Java Python Go Rust
Homework 1 (due September 19, 2024)
- Code Specification
- Problem Set
- Description of Submitty Public Test Cases
- Description of Submitty Hidden Test Cases
Homework 2 (due October 16, 2024)
- Code Specification
- Problem Set
- Description of Submitty Public Test Cases
- Description of Submitty Hidden Test Cases
Homework 3 (due November 15, 2024)
Homework 4 (due December 8, 2024)
Papers and Readings
Some papers are behind a pay wall and can only be accessed from the RPI network.
- Time, clocks, and the ordering of events in a distributed system, Leslie Lamport, Communications of the ACM, 1978.
- Efficient solutions to the replicated log and dictionary problems, Gene T.J. Wuu and Arthur J. Bernstein, Proceedings of the third annual ACM symposium on Principles of distributed computing, 1984.
- A optimal algorithm for mutual exclusion in computer networks, Glenn Ricart and Ashok K. Agrawala, Communications of the ACM, 1981.
- A tree-based algorithm for distributed mutual exclusion, Kerry Raymond, ACM Transactions on Computer Systems, 1989.
- A sqrt(N) algorithm for mutual exclusion in decentralized systems, Mamoru Maekawa, ACM Transactions on Computer Systems, 1985.
- The Information Structure of Distributed Mutual Exclusion Algorithms, Beverly Sanders, ACM Transactions on Computer Systems, 1987.
- Distributed Snapshots: Determining Global States of a Distributed System, K. Mani Chandy and Leslie Lamport, ACM Transactions on Computer Systems, 1985.
- The Part-Time Parliament, Leslie Lamport, ACM Transactions on Computer Systems, 1998.
- Paxos Made Simple, Leslie Lamport, ACM SIGACT News, 2001.
- Elections in a Distributed Computing System, Héctor García-Molina, IEEE Transactions on Computers, 1982.
- Impossibility of Distributed Consensus with One Faulty Process , Michael J. Fischer, Nancy A. Lynch, Michael, S. Patterson, Journal of the ACM, 1985.
- The Byzantine Generals Problem, Leslie Lamport, Robert Shostak, and Marsall Pease, ACM Transactions on Programming Languages and Systems, 1982.
- Foundations of Distributed Consensus and Blockchains, Elaine Shi, 2020.