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: Linh Tran (tranl3@rpi.edu)
Lectures: MR 12pm - 1:50pm
Quiz Schedule
Quizzes will be held during the scheduled lecture time.
- Quiz 1: Thursday 1/25/24
- Quiz 2: Thursday 2/15/24
- Quiz 3: Thurdsay 3/14/24
- Quiz 4: Monday 4/1/24
- Quiz 5: Thursday 4/18/24
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)
- Submitty (for course materials, discussion forum, and projects)
Projects
The projects 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. See the Project 1 description for more information on how to configure your projects.
- 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 the name of the container image for this class.
- Example knownhosts.json file
- Examples projects with build.sh and run.sh scripts: Python Go Rust
Project 1
Project 2
Project 3 (due April 10)
Extra Credit Project (due April 18)
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.
- Concurrency Control and Recovery in Database Systems, Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman, 1987. 2PC and 3PC are in Chapter 7.
- 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, Leslia Lamport, Robert Shostak, and Marshall Pease, ACM Transactions on Programming Languages and Systems, 1982.
- Foundations of Distributed Consensus and Blockchains, Elaine Shi, 2020.
- Dynamo: amazon’s highly available key-value store, Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall and Werner Vogels, ACM SIGOPS Operating Systems Review, 2007.
Back Quizzes
These quizzes are provided to give you some idea of the types of questions that may be asked. The specific topics and the order in which they are presented may vary somwhat from year to year.