Class Time and Place: T F 12:00pm - 1:50pm, Low 3051
Instructor: Stacy Patterson sep AT cs.rpi.edu
Office Hours: T 2:00pm - 3:00pm or by appointment, Lally 301
TA: Samantha Lee lees29 AT rpi.edu
TA Office Hours: M 4:00pm - 5:00pm in AE 127, W 2:00pm - 3:00pm in Lally 209B
Due: Wednesday, Dec. 13, 2017 at 11:00pm, optional no-penalty extension until Friday, Dec. 15, 2017, at 11:00pm
Submit in Gradescope: https://gradescope.com
Final Exam Instructions - Read these first
Final Exam Questions - By downloading this exam, you agree to abide by the Final Exam Instructions linked above.
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 and peer-to-peer systems.
Project 0 - No due date
Project 1 - Due October 15, 2017 at 11:00pm
Project 2 - Due December 3, 2017 at 11:00pm
You will demonstrate your projects on AWS. You must sign up for an
AWS Educate or AWS Educate Starter account.
A credit card is needed to sign up for the Educate account, but not
the Starter acccount.
You should review the differences here and pick which account you prefer. Either account will give you more than enough AWS credit to test and demonstrate both projects for this class. To receive the AWS credit, you should use your RPI email address to sign up.
Do not use the Labs unless you are sure how this will impact your AWS credits. Last year, students exhausted their credits on the labs without realizing it.
Instructions on how to configure AWS security groups are here. You can find more detailed information on AWS. Be sure to terminate your instances when you are not using them to avoid unnecessary charges.
Some papers are behind a pay wall and can only be acccessed from the RPI network.
Time, clocks, and the ordering of events in a distributed system,
Leslie Lamport, Communications of the ACM, 1978.
Virtual time and global states of distributed systems, Friedemann Mat
tern, Parallel and Distributed Algorithms, 1989
Probabilistic clock synchronization, Flaviu Cristian, Distributed Computing, 1989.
Efficient solutions to the replicated log and dictionary problems, Gene T.J. Wu and Arthur R. Bertsein, 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 √ 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 distributed systems, K. Chandy and L. Lamport, ACM Transactions on Computer Systems, 1985.
Impossibility of Distributed Consensus with One Faulty Process, M. Fischer, N. Lynch, and M. Paterson, Journal of the ACM, 1985.
Paxos Made Simple, L. Lamport, ACM SIGACT News, 2001.
The Part-Time Parliament, L. Lamport, ACM Transactions on Computer Systems, 1998.
The Byzantine Generals Problem, L. Lamport, R. Shostak, and M. Pease, ACM Transactions on Programming Languages and Systems, 1982.
Perspectives on the CAP Theorem, S. Gilbert and N. Lynch, Computer, 2012.
Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, S. Gilbert and N. Lynch, ACM SIGACT News, 2002.
Dynamo: Amazon's Highly Available Key-value Store, G. DeCandia et al., Symposium on Operating Systems Principles, 2007.
Incentives Build Robustness in BitTorrent, B. Cohen, Workshop on Economics of Peer-to-Peer system, 2003.