Algorithms and Distributed Systems


The core goal of this course is to consolidate the knowledge of the students in the area of distributed systems, by gaining a better understanding of the problems and associated algorithms that are used in the design of systems widely in use now-a-days. This tackled by studying the fundamental ideas associated with key algorithms that are underlying the conception of current systems but also that are expected to play a key role in the conception of future ones. 

The course has a strong algorithmic component, which is entwined with a set of programming projects, which put in practice the fundamental concepts learned in lectures, exposing student to key subtleties associated with the implementation of many of these algorithms.


• Basic concepts to the analysis and synthesis of distributed algorithms.

• Fundamental abstractions for building distributed systems and the algorithms that are used to realize them.

• Techniques for improving the reliability and scalability of distributed systems.


• Designing distributed algorithms and applying them to build distributed systems.

• Analysing distributed algorithms.

• Programming distributed systems.

General characterization





Responsible teacher

João Carlos Antunes Leitão, Nuno Manuel Ribeiro Preguiça


Weekly - 4

Total - 56

Teaching language



Fundamental knowledge of distributed systems and Java programming.


Main course reading:

• N. Lynch. Distributed Algorithms Morgan Kauffman, 1996.

• C. Cachin, R. Guerraoui, L. Rodrigues "Introduction to Reliable and Secure Distributed Programming", 2nd ed, Springer, 2011.

Selected research papers.


Complementary reading:

• H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2nd Ed.), Wiley 2004.

• S. Mullender (editor) Distributed Systems, Second Edition, ACM Press, Addison-­Wesley, MA, 1994.

• A.S. Tanenbaum and M. van Steen. Distributed Systems. Principles and Paradigms. (2nd Ed.) Prentice Hall, 2007.

• Rodrigo Rodrigues, Peter Druschel. Peer-­to-­Peer Systems. Communications of the ACM. Vol. 53 N10, pp 72-­82.

Teaching method

Lectures presenting fundamental concepts and collaborative design of solutions for problem/algoirhtms.

Laboratory classes focused on case studies and mecanisms/techiniques to implement and develop distributed algorithms and systems, based on a group project.

Individual homeworks.

Evaluation method

2 midterm tests (or allternatively an exame that replaces the tests): 45%

project (in three phases, and conducted in groups of 3 students): 45%

Individual homeworks (provided in lectures, and hand delivered in the start of the following lecture): 10%

Components resuts are rounded up to the 2 decimal place, and final grade rounded up to units.

Subject matter

1. Distributed computation models:

    1. Modelling processes, faults, crypto primitives and communication.

    2. Synchronous, asynchronous and partially synchronous models.

    3. Communication Primitives (Best-effort, exactly once, Broadcast).

2. Peer-to-Peer Systems:

    1. Unstructured Overlay networks.

    2. Gossip Protocols.

    3. Structured Overlay networks.

    4. Consistent Hashing and Routing.

    5. Case studies.

3. Consensus:

    1. Consensus in Synchronous Systems.

    2. Consensus in Asynchronous Systems & FLP.

    3. Paxos and some variants.

4. Replication and Fault Tolerance:

    1. Specifying replicated systems.

    2. Active Replication and Passive Replication.

    2. Strong Consistency: State Machine Replication.

    3. Weak Consistency: CAP theorem, eventual consistency, causal consistency.

    4. Case studies.

5. Distributed transactions:

    1. Two-phase commit.

    2. Three-phase commit.


Programs where the course is taught: