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: Matthew Obetz obetzm AT rpi.edu
TA Office Hours: W 9:00am - 10:00am, R 6:00pm - 7:00pm, AE 127
Due: Wednesday, Dec. 12, 2018 at 11:00pm, optional no-penalty extension until Friday, Dec. 14, 2018, 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, edge computing, and peer-to-peer systems.
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.
Timestamps in Message-Passing Systems That Preserve the Partial Ordering, Colin J. Fidge, Australian Computer Science Communications, 1988.
(Relevant section: Asynchronous Communication pages 58-59)
Efficient solutions to the replicated log and dictionary problems, Gene T.J. Wuu and Arthur R. Berntsein, Principles of Distributed Computing, 1984.
A optimal algorithm
for mutual exclusion in computer networks, Glenn Ricart and Ashok K. Agrawa
la, Communications of the ACM, 1981.
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
A tree-based algorithm for distributed mutual exclusion, Kerry Raymond, ACM Transactions on Computer Systems, 1989.
Distributed snapshots: determining global states of distributed systems, K. Chandy and L. Lamport, ACM Transactions on Computer Systems, 1985.
Paxos Made Simple, L. Lamport, ACM SIGACT News, 2001.
The Part-Time Parliament, L. Lamport, ACM Transactions on Computer Systems, 1998.
Impossibility of Distributed Consensus with One Faulty Process, M. Fischer, N. Lynch, and M. Paterson, Journal of the ACM, 1985.
Concurrency Control and Recovery in Database System, Bernstein, Hadzilacos, and Goodman (2PC and 3PC in Chapter 7)
The Byzantine Generals Problem, L. Lamport, R. Shostak, and M. Pease, ACM Transactions on Programming Languages and Systems, 1982.
Elections in a Distributed Computing System, H. Garica-Molina, IEEE Transactions on Computers, 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.
Chord: a scalable peer-to-peer lookup protocol for Internet applications, I. Stoica, et al.,
IEEE/ACM Transactions on Networking, 2003.