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.
  • Applications of distributed systems to machine learning.
Grade
The grade will be based on several written homework assignments (HW), programming projects (PP), and a final project (FP). Final project grade is composed of project proposal, project presentation and demo, and project report. Grade is computed as follows: Grade = 30%*HW + 40%*PP + 30%*FP.
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]
  • Docker tutorial for 7610 by Asad Salman: [ 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 for public access as the class progresses. There are no slides currently posted. Class platform is canvas available through mynortheastern. All additional material for the class and all class communication will take place on canvas. For the most updated information check canvas.

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.
Week 3 Topic 3 - Consensus: synchronous systems, asynchronous systems, byzantine failures (including randomized solutions).
Week 4 Topic 4 - Process Groups: Leader election, membership, reliable multicast, virtual synchrony.
Week 5 Topic 5 Distributed commit (2PC and 3PC)
Week 6 No class on Monday - Columbus Day.
Topic 6 - Quorums. Paxos. Viewstamped replication. BFT.
Week 7 Topic 6 cont.
Week 8
Topic 7 - Peer-to-peer overlays. Gossip protocols. Distributed Hash Tables
Week 9 Topic 8 - Blockchains, digital currencies, credit systems, smart contracts, distributed ledgers.
Week 10
Topic 9 - GFS, HDFS.

Topic 10 - BigTable, HBase, Spanner. Dynamo
Week 11 Topic 11 - MapReduce. Hadoop. Spark. Mesos. Yarn. Topic 12 - Chubby. Zookeeper.
Week 12 Topic 15 - Microservices. AWS Lambda, OpenWhisk.
Week 13 Topic 13 - Infrastructure for ML. TensorFlow, GraphLab.
Week 14 Topic 14 - Edge computing. Class summary: Ten things to remember.
Final Project presentations.

Week 14 Final Project presentations.



Reading List

This is a collection of must-read in distributed systems.
  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. Hyperledger fabric: a distributed operating system for permissioned blockchains, EuroSys 2018.
  41. Scaling Distributed Machine Learning with the Parameter Server, OSDI 2014
  42. Bitcoin: A Peer-to-Peer Electronic Cash System, Satoshi Nakamoto
  43. Majority is not Enough: Bitcoin Mining is Vulnerable Ittay Eyal, and Emin GŁn Sirer <>



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