CSCI 4963/6963 - Distributed Systems and Algorithms - Fall 2016

General Information

Class Time and Place: M TR 12:00pm - 1:50pm, Sage 5510 Greene 120 Sage 4101
Instructor: Stacy Patterson     sep AT cs.rpi.edu
Office Hours: M 2:00pm - 3:00pm or by appointment, Lally 301
TA: Erika Mackin     mackie2 AT rpi.edu
TA Office Hours: W 11:00am - 12:00pm in AE 127 and F 2:00pm - 3:00pm in AE 119 (lounge)

Final Exam

Due: Friday, Dec. 9, 2016 at 10:00pm, optional no-penalty extension until Saturday, Dec. 10, 2016, at 10:00pm
Submission Link: Final Exam Submission

  • Final Exam Instructions - Read these first
  • Final Exam Cover Sheet
  • 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
    Slides: Intro to Distributed Systems

    Prerequisites

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

  • Project 1 - Due October 16, 2016 at 10:00pm
  • Project 2 - Due November 29, 2016 at 10:00pm
  • Pseudocode and Resources

  • Maekawa's deadlock-free algorithm, with corrections
  • Video explaining Chandy-Lamport algorithm
  • Wuu Bernstein Replicated Dictionary Algorithm
  • Broadcast algorithms
  • Leader Election algorithms
  • Slides on Two Generals Problem
  • Concurrency Control and Recovery in Database System, Bernstein, Hadzilacos, and Goodman (2PC and 3PC in Sec. 7.3)
  • Slides on 3 Phase Commit
  • Synod Algorithm and Invariants
  • Slides on Paxos
  • Paxos Quiz Questions from 2015
  • Byzantine agreement algorithm
  • Slides on P2P Systems
  • 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 Mattern, Parallel and Distributed Algorithms, 1989
  • Probabilistic clock synchronization, Flaviu Cristian, Distributed Computing, 1989.
  • 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.
  • Efficient solutions to the replicated log and dictionary problems, G. Wuu and A. Bernstein, Proceedings of the third annual ACM symposium on Principles of Distributed Computing, 1984.
  • 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.
  • 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.
  •