I639@[Distributed Algorithms]

LectureFDefago

Aims

This lecture will cover the theoretical foundations underlying distributed systems. In particular, it will present the basic concepts, fundamental problems and their solutions, as well as important impossibility results. We will also discuss the applications of the concepts to emerging fields.

Contents

Distributed system models, causality, agreement problems, global predicate evaluation, anonymous networks, fault-tolerant broadcast and multicast, consensus, quorums, self-stabilization

Textbook

1. Gerard Tel. Introduction to distributed algorithms (2nd ed.), Cambridge University Press, 2000.
2. Lecture notes distributed during the lecture.
3. Copies or reference of some relevant scientific articles

Reference Books

1.Sape Mullender (ed.). Distributed Systems (2nd ed.), Addison-Wesley, 1993.
2.Shlomi Dolev. Self-stabilization. MIT Press, 2000.

Related Lectures

Students who attend this lecture need to have an initial understanding of networking, operating systems, concurrent or parallel programming, and mathematical logic.

Schedule

  1. Introduction; Model (transition systems and algorithms, safety, liveness, and fairness, complexity metrics)
  2. Causality (ordering of events, Lamport logical clocks, Fidge-Mattern vector clocks)
  3. Election algorithms (ring networks, arbitrary networks, Korach-Kutten-Moran algorithm)
  4. Termination detection (computation tree and forests, wave-based solutions, other solutions)
  5. Anonymous networks (deterministic algorithms, probabilistic election, computing the network size)
  6. Distributed snapshots (Chandy-Lamport algorithm, Lai-Yang algorithm, deadlock detection)
  7. Sense of direction; synchrony (election in rings, hypercubes, election in synchronous networks, synchronizers)
  8. Fault tolerance in asynchronous systems (Fischer-Lynch-Paterson impossibility of consensus, deterministically achievable case, probabilistic consensus, weak termination)
  9. Failure detector oracle (unreliable failure detectors, Consensus with <>S, weakest failure detector, Omega and Paxos consensus)
  10. Broadcast and multicast algorithms (Reliable, FIFO, causal, totally ordered broadcast/multicast algorithms)
  11. Partial synchrony (partial synchrony, timed asynchronous model, other models)
  12. Self-stabilizing algorithms (graph algorithms, methodology for stabilization, composition theorem)
  13. Quorums (voting, probabilistic quorums, Byzantine quorums)
  14. Wider horizons (distributed algorithms for cooperative autonomous mobile systems)
  15. Examination