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
Additional material
Courses
- Introduction, assumptions, Election (version of October 2018)
- Time in distributed systems - Consistent Snapshots and Cuts (version of October 2013, same for 2016)
- Fault Recovery by checkpointing and message logging updated oct 2017 Correctionzpaths.pdf:
- Failure detectors and consensus: (oct 2017) Correction homerwork
- Mutual exclusion (Oct 2017).pdf Correction homerwork
- Group Communications (version of Oct/Nov. 2017)
- 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:
- zab.pdf: the tricky consensus/atomic broadcast underlying algorithm of the zookeeper system to maintain consistent replica
to top