Distributed Algorithms

Module aims

The course aims to cover the key concepts, problems and results in distributed algorithms. It will provide an introduction on how to reason about the correctness of distributed algorithms and practical experience of programming them.
 

Learning outcomes

  • To have a good understanding of the important theoretical concepts and limitations for a range of distributed algorithms.
  • To be able to reason about the correctness of distributed algorithms.
  • To gain practical experience in programming and evaluating distributed algorithms.

Module syllabus

Communication, Timing and Fault Models.
Synchrony, Clocks, Failure Detectors, Leader Election
Algorithm classes, Properties and Proofs.
Reliable Broadcast Algorithms
Shared Memory Algorithms
Consensus Algorithms
Group Membership Algorithms
Self-Stabilisation Algorithms
Conflict-Free Replicated Data Types
 

Pre-requisites

Concurrency, Maths (Basic proof techniques e.g. induction; Posets)

Teaching methods

27 one-hour periods mixing lecture, tutorial and lab activities.

Assessments

Exam plus three lab exercises. Lab exercises will be carried out in groups of 3 and will involve programming and evaluating distributed algorithms in a distributed infrastructure.
 

Module leaders

Dr Naranker Dulay
Dr Anandha Gopalan