Distributed Algorithms

Module aims

The module 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

Upon successful completion of this module you will be able to:

  • design, program and evaluate a range of distributed algorithms running natively in virtualised environments
  • analyse and reason about the correctness of distributed algorithms
  • describe and reason about basic timing, failure and communication models and the guarantees they provide  

Module syllabus

  • Core concepts
  • Reliable broadcast
  • FIFO, Causal and Total order broadcast
  • Consensus
  • Leader Election
  • Group membership
  • Distributed Shared memory
  • Peer-to-peer Overlay networks

Teaching methods

Classroom sessions will include traditional lectures and some supervised problem solving, which are designed to reinforce understanding. Many of the latter will be lab sessions using Docker virtualised environments. These problems are not assessed, although specimen solutions will be provided. Past exam paper questions will also be included in the problem sets in order to help prepare you for the final exam. 

The Piazza Q&A web service will be used as an open online discussion forum for the module.                                                    

Assessments

There will be two coursework exercises designed to reinforce the material covered in lectures and give you hands-on experience of implementating and analysing real distributed algorithms. These courseworks together count for 20% of the marks for the module. There will be a final written exam, worth 80% of the marks, which will test both theoretical and practical aspects of the subject.  

There will be detailed feedback on the coursework exercises which will include written feedback on your submissions and class-wide feedback explaining common pitfalls and suggestions for improvement.

Reading list

Module leaders

Dr Naranker Dulay
Dr Anandha Gopalan