Distributed Systems
(CS 4730)

This site is maintained for public access, if you are enrolled in the class see the Canvas webpage for detailed information.

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 in-class exercises (EE), at home quizes (QQ), and several programming projects (PP). There is no final exam. For grade computation see canvas.
Programming projects
Programming language required is C, platform is Linux. We will be using docker to manage your distributed applications.
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 Projects
Week 1 Module 1 - Introduction. Class policy. Docker. Networking refresh.
Project 1 assigned
Week 2 Module 2 -Time in distributed systems (Lamport clocks, vector clocks, NTP). Global states and distributed snapshots. Failure detectors.
Week 3 Module 3 - Consensus: synchronous systems, asynchronous systems, byzantine failures (including randomized solutions). Project 2 assigned.
Week 4 Module 4 - Process Groups: Leader election, membership, reliable multicast, virtual synchrony.
Week 5 Module 5 Distributed commit (2PC and 3PC)
Project 3 assigned
Week 6 Module 6 - Quorums. Paxos. Viewstamped replication. BFT.
Week 7 Module 6 cont.
Week 8
Module 7 - Peer-to-peer overlays. Gossip protocols. Distributed Hash Tables 		Project 4 assigned
Week 9 SPRING BREAK
Week 10
Module 8 - Blockchains, digital currencies, credit systems, smart contracts, distributed ledgers.
Week 11 Topic 9 - GFS, HDFS.
Week 12 Topic 10 - BigTable, HBase, Spanner. Dynamo Project 5 assigned.
Week 13 Topic 11 - MapReduce. Hadoop. Spark. Mesos. Yarn.
Week 14 Topic 12 - Infrastructure for ML. TensorFlow, GraphLab.
Topic 13 - Edge computing.
Week 15 Class summary: Ten things to remember.



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