CSCI 4510/6510 - Distributed Systems and Algorithms - Fall 2018

General Information

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

Final Exam

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.
  • 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
    Intro Slides

    Prerequisites

  • CSCI-2300: Intro. to Algorithms
  • CSCI-4210: Operating Systems
  • Project Information

  • Project 0 - No due date
  • Project 1 - Due October 14, 2018 at 11:00pm
  • Project 2 - Due December 5, 2018 at 11:00pm
  • Pseudocode and Resources

  • Wuu Bernstein Replicated Dictionary Algorithm (with corrections)
  • Maekawa's deadlock-free algorithm, with corrections
  • Raymond's Algorithm
  • Example of Raymond's Algorithm from class
  • Video explaining Chandy-Lamport algorithm
  • Slides on Two Generals Problem
  • Slides on Paxos
  • Slides on Paxos Implementation Details
  • Byzantine agreement algorithm
  • Papers

    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.
  •