Distributed Systems
(CS 7610)

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:
  • 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: files systems (GFS, HDFS), databases (BigTable, HBase, Spanner), lock services (Chubby, Zookeeper, Zab), computational services (MapReduce, Spark).
  • Applications of distributed systems to blockchains, digital currencies, credit, systems, smart contracts, and distributed ledgers.
Grade
The grade will be based on several written homework assignments (HW), programming projects (PP), a final project (FP), and class participation (in class, piazza, office hours, etc) (CP) as follows:
Grade = 24%*HW + 40%*PP + 26%*FP + 10%CP.
Programming projects
Programming language required is C, platform is Linux. For the final project, any programming language can be used.
Reading list and resources
  • Reading will be assigned during each lecture, see also the list at the end of the page.
  • Lectures for the undergraduate introduction to C course I taught at Purdue: [www]
  • Socket programming: [www]
  • Unix programming links: [www]

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. Preliminary plan and topics below.

Week Topics Homework Project
Week 1 Topic 1 - Introduction. Class policy.
Week 2 Topic 2 - Time in distributed systems (Lamport clocks, vector clocks, NTP). Global states and distributed snapshots. Failure detectors.
Topic 3 - Consensus: synchronous systems, asynchronous systems, byzantine failures (including randomized solutions). 		Hw1 assigned
Week 3 Topic 3 cont.
Topic 4 - Process Groups: Leader election, membership, reliable multicast, virtual synchrony.
Hw1 due Hw1 due. Project 1 assigned.
Week 4 Topic 5 Distributed commit (2PC and 3PC)
Topic 6 - Quorums. Paxos. Viewstamped replication. BFT.
Week 5 Topic 6 cont. No class on Wednesday. Project 1 due Sunday Oct 6
Week 6 Topic 6 cont.
Hw2 assigned. 		Project 2 assigned.
Week 7 No class on Monday - Columbus Day.
Topic 7 - Peer-to-peer overlays. Gossip protocols. Distributed Hash Tables 		Hw2 due.
Week 8 Topic 8 - Blockchains, digital currencies, credit systems, smart contracts, distributed ledgers. Project 2 due
Week 9 Topic 8 cont. Final project assigned/selected.
Week 10
Topic 9 - GFS, HDFS.

Topic 10 - BigTable, HBase, Spanner. Dynamo 		Hw3 assigned.
Week 11 Topic 11 - MapReduce. Hadoop. Spark. Mesos. Yarn. Topic 12 - Chubby. Zookeeper. Hw3 due.
Week 12 Topic 12 - cont. Topic 13 - Infrastructure for ML. TensorFlow, GraphLab.
Week 13 Topic 14 - Edge computing. Class summary: Ten things to remember.
Week 14 Final Project presentations.
Final project presentations will take place in class.



Reading List

  1. Why Do Computers Stop and What can be done about it? J. Gray. 1985.
  2. End to end arguments in System Design. Saltzer, Reed, Clark. TOCS 1990.
  3. Why do Internet services fail, and what can be done about it? 2003. D. Oppenheimer, A.Ganapathi and D. A. Patterson.
  4. Time, Clocks, and the Ordering of Events in a Distributed System, L. Lamport 1978, SIGOPS Hall of Fame.
  5. Virtual Time and Global States of Distributed Systems", Mattern, F. 1988.
  6. Distributed Snapshots: Determining Global States of Distributed Systems. K. M. Chandy and L. Lamport,, 1985, SIGOPS Hall of Fame.
  7. Unreliable Failure Detectors for Reliable Distributed Systems, T. Chandra and S. Toueg. , 1996.
  8. Knowledge and Common Knowledge in a Distributed Environment, J. Halpern and Y. Moses , E.W. Dijkstra Prize 2009.
  9. Impossibility of Distributed Consensus with One Faulty Process. M.J.Fischer, N.A.Lynch and M.S. Paterson. , 1983. E.W. Dijkstra Prize, 2001.
  10. The Byzantine Generals Problem, L. Lamport, R. Shostak, and M. Pease, 1982.
  11. Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocol. M. Ben-Or. 1983.
  12. Exploiting virtual synchrony in distributed systems. K. P. Birman and T. A. Joseph, 1987.
  13. Extended Virtual Synchrony, L. E. Moser, Y. Amir, P. M. Melliar-Smith, D. A. Agarwal,1994.
  14. Distributed Recovery, Bernstein, Goodman and Hadzilakos.
  15. Non-blocking Commit Protocols, D. Skeen.
  16. Determining the Last Process to Fail, D. Skeen.
  17. The State Machine Approach. F.B. Schneider. , SIGOPS Hall of Fame.
  18. Hypervisor-based Fault-Tolerance, T. Bressoud and F.B. Schneider
  19. A Survey of Rollback Recovery Protocols in Message Passing Systems, E. Elnozahy, L. Alvisi, Y.M.Wang, and D.B. Johnson.
  20. Paxos Made Simple, L. Lamport.
  21. The Part-Time Parliament L. Lamport , SIGOS Hall of Fame
  22. Paxos for System Builders, J. Kirsch and Y. Amir (the technical report) .
  23. Viewstamped Replication Revisited, B. Liskov and J. Cowling
  24. From Viewstamped replication to Byzantine replication. B Liskov.
  25. Bimodal Multicast, K.P. Birman, M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu, and Y. Minsky
  26. Byzantine Quorum Systems, D. Malkhi and M. Reiter
  27. Practical Byzantine Fault-Tolerance, M. Castro and B. Liskov
  28. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, H. Balakrishnan, , 2001.
  29. Google File System. S, Ghemawat, H. Gobioff and S.-T. Leung. SOSP 2003.
  30. The Chubby Lock Service for Loosely-Coupled Distributed Systems. Mike Burrows, OSDI 2006
  31. Bigtable: A Distributed Storage System for Structured Data. 2008. ACM Trans. Comput. Syst. 26, 2 (Jun. 2008), 1-26
  32. Spanner, Google?s globally distributed database. OSDI 2012.
  33. MapReduce: Simplified Data Processing on Large Clusters OSDI 2004
  34. Mesos: A Platform for Fine-Grained Resource Sharing in the Data Center, NSDI 2011
  35. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing, NSDI 2012, best paper
  36. Apache Hadoop YARN: Yet Another Resource Negotiator SOCC 2013 (best paper)
  37. Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud, VLDB 2012
  38. Pregel: A System for Large-Scale Graph Processing, SIGMOD 2010
  39. TensorFlow: A System for Large-Scale Machine Learning OSDI 2016
  40. Bitcoin: A Peer-to-Peer Electronic Cash System, Satoshi Nakamoto
  41. Majority is not Enough: Bitcoin Mining is Vulnerable Ittay Eyal, and Emin Gün Sirer
  42. Hyperledger fabric: a distributed operating system for permissioned blockchains, EuroSys 2018.


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