Distributed Systems


Class Information
Lectures
Reading List


Class Information
Instructor
Course Description
This course is an introduction to distributed systems. The lectures will cover fundamental concepts in distributed systems showing how they are applied when building reliable distributed systems and services. Topics include:
  • Internet communication protocols. Client Server paradigm, RPC, Corba.
  • How and why computers systems fail. How to overcome failures in a distributed system. Failures models. The distributed commit problem.
  • Clock synchronization and synchronous systems.
  • Dynamic membership. Replicating data with malicious failures. Impossibility of asynchronous consensus.
  • Group communication systems, properties and dynamic group membership. Causal and total order.
  • Virtually synchronous algorithms and tools: replicated data, state transfer, load-balancing, primary-backup and coordinator-cohort fault tolerance.
  • Transactional model and implementation of a transactional storage systems. Distributed transactions and multiphase commit.
  • Distributed hash tables.
  • Application of distributed systems concepts to real systems. GFS, HDFS, BigTable, HBase, Spanner. Chubby. Zookeeper. Zab. MapReduce.
Grade
The grade will be based on several written homework assignments (HW), programming projects (PP), one midterm (MT), final exam (FE), and class participation (CP) as follows:
Grade = 10%*HW + 35%*PP + 20%*MT + 30*FE + 5%CP.
Programming projects
Programming language required is C, platform is Linux. We will be using Turret for testing and grading. There will be a Turret tutorial during the class lectures. Turret allows users to develop a variety of test cases and helps with deigning robust distributed systems.
Textbooks and reading list
Academic Integrity

Academic Honesty and Ethical behavior are required in this course, as it is in all courses at Northeastern University. There is zero tolerance to cheating.

You are encouraged to talk with the professor about any questions you have about what is permitted on any particular assignment.


Lectures

Lecture slides will be posted below. Homework and projects will be handed in class and/or posted on piazza. All class communication will take place on piazza.

Week Topics Homework Project
Week 1 Topic 1 - Introduction. Basic communication services.
Topic 2 - Time in distributed systems (Lamport clocks, vector clocks, NTP). Global states and distributed snapshots.
Week 2 Topic 2 - cont.
Turret tutorial, slides will be posted on piazza.
Week 3 Topic 3 - Consensus: synchronous systems, asynchronous systems, byzantine failures (including randomized solutions).
Hw1 assigned
Week 4 Topic 3 - cont . Prj1 assigned
Week 5 Topic 4 Distributed commit (2PC and 3PC)
Week 6 Topic 5 - Process Groups: Leader election, membership, reliable multicast, virtual synchrony.
Review for Midterm.
Hw2 assigned
Week 7 MIDTERM in class
Week 8 Topic 5 - cont. Prj2 assigned
Week 9 Topic 6 - Gossip protocols
Week 10 (Oct. 27)
Topic 7 - Quorums. Paxos. Viewstamped replication. BFT. Hw3 assigned
Week 11 Topic 7 - cont. Prj3 assigned
Week 12 Topic 8 - Distributed hash tables.
Topic 9 - Distributed file systems.
Week 13 Topic 10 - GFS, HDFS.
Topic 11 - BigTable, HBase, Spanner
Week 14 Topic 12 - Chubby. Zookeeper. Zab
Topic 13 - MapReduce. Mesos. Yarn.



Reading List

  1. J. Gray. Why Do Computers Stop and What can be done about it? 1985.
  2. Saltzer, Reed, Clark. End to end arguments in System Design. TOCS 1990.
  3. D. Oppenheimer, A.Ganapathi and D. A. Patterson. Why do Internet services fail, and what can be done about it? 2003.
  4. L. Lamport for "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM, July 1978, 21(7):558-565. E.W. Dijkstra Prize 2000, SIGOPS Hall of Fame.
  5. J. Halpern and Y. Moses Knowledge and Common Knowledge in a Distributed Environment E.W. Dijkstra Prize 2009.
  6. T. Chandra and S. Toueg. Unreliable Failure Detectors for Reliable Distributed Systems, 1996.
  7. K. M. Chandy and L. Lamport, Distributed Snapshots: Determining Global States of Distributed Systems. ACM Transactions on Computer Systems, Vol. 3, No. 1, February, 1985, pp. 63-75. SIGOPS Hall of Fame.
  8. M.J.Fischer, N.A.Lynch and M.S. Paterson. Impossibility of Distributed Consensus with One Faulty Process. ACM SPDS 1983. E.W. Dijkstra Prize, 2001.
  9. L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem ACM Transactions on Programming Languages and Systems 4(3):382-401, July 1982.
  10. M. Ben-Or. Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocol. PODC '83.
  11. K. P. Birman and T. A. Joseph. Exploiting virtual synchrony in distributed systems. In Proceedings of the ACM Symposium on OS Principles, pages 123--138, Austin, TX, 1987.
  12. L. E. Moser, Y. Amir, P. M. Melliar-Smith, D. A. Agarwal, Extended Virtual Synchrony, The 14th IEEE International Conference on Distributed Computing Systems (ICDCS) 1994.
  13. Bernstein, Goodman and Hadzilakos. Distributed Recovery
  14. D. Skeen. Non-blocking Commit Protocols
  15. D. Skeen. Determining the Last Process to Fail
  16. F.B. Schneider. The State Machine Approach. SIGOPS Hall of Fame.
  17. T. Bressoud and F.B. Schneider Hypervisor-based Fault-Tolerance.
  18. E. Elnozahy, L. Alvisi, Y.M.Wang, and D.B. Johnson. A Survey of Rollback Recovery Protocols in Message Passing Systems
  19. L. Lamport: Paxos Made Simple
  20. L. Lamport: The Part-Time Parliament SIGOS Hall of Fame
  21. K.P. Birman, M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu, and Y. Minsky. Bimodal Multicast.
  22. D. Malkhi and M. Reiter Byzantine Quorum Systems
  23. L. Lamport, R. Shostak, and M. Pease The Byzantine Generals Problem E.W. Dijkstra Prize, 2005.
  24. M. Castro and B. Liskov Practical Byzantine Fault-Tolerance
  25. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, H. Balakrishnan, Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, SIGCOMM 2001.
  26. Google File System. S, Ghemawat, H. Gobioff and S.-T. Leung. SOSP 2003.
  27. The Chubby Lock Service for Loosely-Coupled Distributed Systems. Mike Burrows, OSDI 2006



Copyright© 2014 Cristina Nita-Rotaru. Send your comments and questions to Cristina Nita-Rotaru