Distributed Systems: an algorithmic approach

Master 2 Informatique, Specialite IFI (Ingenierie et Fondements de l'Informatique), parcours CSSR, and UBINET, since academic year 2009/2010

General Objectives

• Be capable to understand the problems that arise in the context of distributed systems, such as those due to asynchrony between processes only relying on non-shared memory and message passing, in presence or not of failure.
• Be able to understand typical solutions, and design simple algorithms in such context

Content / Keywords

• Distributed systems
• Fault tolerance
• Concurrency
• Time in distributed systems, logical clocks
• Typical solutions for typical problems: mutual exclusion, deadlock detection, termination detection, election, consensus, group communication, etc.

Reference books

• Distributed Systems : An Algorithmic Approach by Sukumar, Ghosh, http://www.cs.uiowa.edu/~ghosh/16611F.html
• Distributed systems, Principles and Paradigms, A. Tanenbaum, M. Van Steen, 2nd edition http://www.cs.vu.nl/~steen/books/ds2/
• Introduction to Reliable Distributed Programming http://books.google.fr/books?hl=fr&lr=&id=lLHC-0DsZRwC&oi=fnd&pg=PA1&dq=Introduction+to+Reliable+Distributed+Programming&ots=RD1Bgpw7SC&sig=oDYVliOzPrJM6Ogr7cBQHQdK-tA
• Distributed Algorithms for Message-Passing Systems by M. Raynal, Springer 2013

Additional material

• A very didactic paper of F. Mattern
• A very didactic paper of S. Krakowiak (in French)
• A comprehensive summary (in French!) about group communications
• A research paper (in French) about how the Proactive (proactive.inria.fr) java library implements fault-recovery for active objects
• French talk on Failure Detection and Consensus (Hugues.ppt: )
• French paper on self-stabilization (AlgoDistribuee.pdf: ) (focus on section 5 and 6)
• French talk on Group Communications, Transactions (2PC and 3PC) and consensus (cours-accord.pdf:)
• Course from Yale University http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf
• Course of our Eurecom colleagues that include some topics in distributed algorithmics http://www.eurecom.fr/~michiard/teaching/clouds.html (distributed storage and distributed coordination)

Courses

1. Introduction, assumptions, Election (version of October 2018)
2. Time in distributed systems - Consistent Snapshots and Cuts (version of October 2013, same for 2016)
3. Fault Recovery by checkpointing and message logging updated oct 2017 Correctionzpaths.pdf:
4. Failure detectors and consensus: (oct 2017) Correction homerwork
5. Mutual exclusion (Oct 2017).pdf Correction homerwork
6. Group Communications (version of Oct/Nov. 2017)
7. Global state collection: termination, deadlock - Distributed transactions (version of 2015)

Exercises (in class, or at home)

1 Distributed systems assumptions - Simple examples - Election problem

2 Logical Clocks - Causality relation - Snapshot

3 TD about fault tolerance -- 2015: Lamport snapshot: correction Lamport

4 Homework about fault detection (Eventually Perfect Failure Detector strange algorithm) -- 2015: DOC101115-10112015171333.pdf:

5 Group Communications

6 Global state collection - Distributed Transactions

EXAM was on Nov. 08/11/2010. ALL DOCUMENTS allowed

EXAM was on Nov. 21/11/2011. ALL DOCUMENTS allowed !

EXAM was on Nov. 19/11/2012. ALL DOCUMENTS allowed !

EXAM was on Nov. 21/11/2013. ALL DOCUMENTS allowed !

EXAM was on Nov. 17/11/2014. ALL DOCUMENTS allowed ! You also find a nice correction part 1, and nice correction part 2 from a student. EXAM was on Nov. 13/11/2017.

-- FrancoiseBaude

Additional material about ZOOKEEPER:

• ZooKeeper.pdf: the original high level (user oriented) view

• zab.pdf: the tricky consensus/atomic broadcast underlying algorithm of the zookeeper system to maintain consistent replica

• A concise presentation from Brown Univ : Brownuniv-ZooKeeper-notes.pdf

• A concise presentation from TU/Delft : TUDelft-coordination_zookeeper.pdf

• Concise lecture notes: very clear even without the slides! https://pdos.csail.mit.edu/6.824/notes/l-zookeeper.txt

to top