|
Distributed Systems
| 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
- Reading will be assigned during each lecture, see also the list at the end of the page.
-
Reliable Distributed Systems: Technologies, Web Services and Applications. Ken Birman.
2005, XXXVI, 668 p. 145 illus., Hardcover
ISBN: 0-387-21509-3
-
UNIX Network Programming, Volume 1, Second Edition: Networking APIs: Sockets and XTI, Prentice Hall, 1998, ISBN 0-13-490012-X.
W. Richard Stevens
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 |
- J. Gray. Why Do Computers Stop and What can be done about it? 1985.
- Saltzer, Reed, Clark. End to end arguments in System Design. TOCS 1990.
- D. Oppenheimer, A.Ganapathi and D. A. Patterson. Why do Internet services fail, and what can be done about it? 2003.
- 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.
- J. Halpern and Y. Moses Knowledge and Common Knowledge in a Distributed Environment E.W. Dijkstra Prize 2009.
- T. Chandra and S. Toueg. Unreliable Failure Detectors for Reliable Distributed Systems, 1996.
- 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.
- 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.
- L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem
ACM Transactions on Programming Languages and Systems 4(3):382-401, July 1982.
- M. Ben-Or. Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocol. PODC '83.
- 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.
- 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.
- Bernstein, Goodman and Hadzilakos. Distributed Recovery
- D. Skeen. Non-blocking Commit Protocols
- D. Skeen. Determining the Last Process to Fail
- F.B. Schneider. The State Machine Approach. SIGOPS Hall of Fame.
- T. Bressoud and F.B. Schneider Hypervisor-based Fault-Tolerance.
- E. Elnozahy, L. Alvisi, Y.M.Wang, and D.B. Johnson. A Survey of Rollback Recovery Protocols in Message Passing Systems
- L. Lamport: Paxos Made Simple
- L. Lamport: The Part-Time Parliament SIGOS Hall of Fame
- K.P. Birman, M. Hayden, O. Ozkasap, Z. Xiao, M. Budiu, and Y. Minsky. Bimodal Multicast.
- D. Malkhi and M. Reiter Byzantine Quorum Systems
- L. Lamport, R. Shostak, and M. Pease The Byzantine Generals Problem E.W. Dijkstra Prize, 2005.
- M. Castro and B. Liskov Practical Byzantine Fault-Tolerance
- Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, H. Balakrishnan,
Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, SIGCOMM 2001.
- Google File System. S, Ghemawat, H. Gobioff and S.-T. Leung. SOSP 2003.
- 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
|
|