Distributed Algorithms
Module aims
The module will cover the key concepts, problems and results in distributed algorithms. It will provide an introduction on how to model and reason about distributed algorithms and practical experience of programming them. The module builds on (i) OS concepts including processes, threads and scheduling, (ii) concurrency concepts including synchronisation, deadlock, race conditions, (iii) discrete maths including sets, logic and logical reasoning, (iv) functional programming.
Learning outcomes
Upon successful completion of this module you will be able to:
- program and evaluate a range of distributed algorithms including Byzantine variants
- model and reason about the correctness of distributed algorithms
- use and reason about basic timing, failure and communication models and the guarantees they provide
- extend outcomes above to Byzantine failures and algorithms
Module syllabus
- Core concepts
- Introduction to Tools for concurrent message passing (Elxiir) and formal specifications (TLA+)
- Regular and Uniform Reliable broadcast
- FIFO, Causal and Total order broadcast
- Consensus
- Leader Election
Teaching methods
The module will taught through lectures and supervised lab sessions. The labs are designed to reinforce the material covered in the lectures and provide hands-on experience of analysing and programming distributed algorithms. The labs can be completed with a classmate and are not assessed. A range of tutorial questions and solutions will be also be provided.
An online forum will be used for discussions related to the module.
Assessments
There will be one assessed coursework exercise. This will involve the implementation, analysis and evaluation of a distributed algorithm such as Raft or Multi-Paxos using the tools used in the supervised lab sessions. The cousework can be completed jointly with a classmate. Submission includes the code and a short report. These coursework counts for 30% of the marks for the module. The final written exam counts for 70% of the marks for the module.
Coursework feedback and a mark will be returned to each the submitting student as typed text and/or a marked-up pdf of the report. Class-wide feedback will given during a lecture session explaining common pitfalls and suggestions for improvement and future study.