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
• model and reason about the correctness of distributed algorithms
• use and reason about basic timing, failure and communication models and the guarantees they provide

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.

Reading list

Supplementary

• Distributed algorithms

  Lynch, Nancy A., 1948-

  San Francisco, CA : Morgan Kaufmann Publishers

• Distributed computing : principles, algorithms, and systems

  Kshemkalyani, Ajay D.

  Cambridge University Press

• Elements of distributed computing

  Garg, Vijay K. (Vijay Kumar), 1963-

  New York, Chichester : Wiley-Interscience

• Introduction to Reliable and Secure Distributed Programming

  Cachin, Christian.

  2nd ed., Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer

• Introduction to Reliable and Secure Distributed Programming

  Rodrigues, Luís

  2nd edition, Springer

• Specifying Systems: The Tla+ Language and Tools for Hardware and Software Engineers

  Lamport, Leslie

• Logic in computer science : modelling and reasoning about systems

  Huth, Michael, 1962- author.

  Second edition., Cambridge University Press

Module leaders

Dr Naranker Dulay