CSCI 4963/6963 - Distributed Systems - Fall 2015

General Information

Class Time and Place: TF 12:00pm - 1:50pm, JEC 3207
Instructor: Stacy Patterson     sep AT cs.rpi.edu
Office Hours: T 2:00pm - 3:00pm or by appointment, in Lally 301

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, pervasive computing, and peer-to-peer systems.

Grading for this course will based on in-class quizzes and programmig projects.

Course Syllabus

No class on Friday, Oct. 16

Prerequisites

  • CSCI-2300: Intro. to algorithms
  • CSCI-4210: Operating Systems
  • Quiz Averages

  • Quiz 1: 23.04 / 30
  • Quiz 2: 21.36 / 30
  • Quiz 3: 18.56 / 30
  • Quiz 4: 21.96 / 30
  • Quiz 5: 24.63 / 30
  • Project Information

  • Project 1 - Due: Sunday, Oct. 25, 2015 at 11:00pm
  • Project 1 sample test cases
  • You will demonstrate your project on AWS. You should sign up for AWS Educate to get your $35 credit for use of Aamazon's cloud infrastructure. This should be enough for you to test and demo both projects. You should not do your development in AWS. If you have used your credits for another class or project, talk to the professor about getting additional credits.

  • Project 1 Demo Timeslots - Email me your list of 3 timeslots
  • Project 1 Homework Server Turnin

  • Project 2 - Due Sunday, Dec. 6, 2015 at 11:00pm
  • Project 2 Demo Timeslots - Email me your list of 3 timeslots
  • Project 2 Homework Server Turnin

  • Slides and Notes

  • Intro. to Distributed Systems - 9/1/2015
  • Lecture 2 - 9/4/2015
  • Raymond's Algorithm - 9/15/2015
  • Lecture Slides - 9/18/2015
  • Modifications for Maekawa 2.0 - 9/18/2015
  • Lecture Slides - 9/22/2015
  • Lecture Slides - 9/25/2015
  • Lecture Slides - 09/29/2015
  • Lecture Slides - 10/02/2015
  • Lecture Slides - 10/09/2015
  • Lecture Slides - 10/20/2015
  • Lecture Slides - 10/23/2015
  • Lecture Slides - 10/27/2015
  • Lecture Slides - 10/30/2015
  • Lecture Slides - 11/03/2015 - Paxos
  • Lecture Slides - 11/06/2104 - Paxos Review
  • Lecture Slides - 11/13/2105
  • Lecture Slides - 11/17/2105
  • Lecture Slides - 11/20/2105
  • Lecture Slides - 11/24/2105
  • Lecture Slides - 12/01/2105
  • Lecture Slides - 12/04/2105
  • Papers

  • 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 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.
  • 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.
  • 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.
  • The Byzantine Generals Problem, L. Lamport, R. Shostak, and M. Pease, ACM Transactions on Programming Languages and Systems, 1982.
  • The Part-Time Parliament, L. Lamport, ACM Transactions on Computer Systems, 1998.
  • Paxos Made Simple, L. Lamport, ACM SIGACT News, 2001.
  • Paxos Made Live, T. Chandra, R. Griesemer, and J. Redstone, ACM Symposium on Principles of Distributed Systems, 2007.
  • Pseudocode for Quiz 5
  • Concurrency Control and Recovery in Database Systems, P. Bernstein, V. Hadzilacos, and N. Goodman
  • Perspectives on the CAP Theorem, S. Gilbert and N. Lynch, Computer, 2012.
  • 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.
  • Chord: a scalable peer-to-peer lookup protocol for Internet applications, I. Stoica, et al., IEEE/ACM Transactions on Networking, 2003.
  •