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

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: 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

Final Exam

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.
  • 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 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 15, 2017 at 11:00pm
  • Project 2 - Due December 3, 2017 at 11:00pm
  • Pseudocode and Resources

  • Wuu Bernstein Replicated Dictionary Algorithm
  • Raymond's Algorithm
  • Maekawa's deadlock-free algorithm, with corrections
  • Video explaining Chandy-Lamport algorithm
  • Slides on Two Generals Problem
  • Slides on Paxos and Project 2 Details
  • Byzantine agreement algorithm
  • Concurrency Control and Recovery in Database System, Bernstein, Hadzilacos, and Goodman (2PC and 3PC in Chapter 7)
  • Papers

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