This course is intended to consolidate the knowledge of students in the area of distributed systems. The course has a strong algorithmic component, with some formal exposition and analysis, while also including a strong connection to the practical realisation of these algorithms and their use in the construction of practical systems. The course also provides an introduction to the techniques and algorithms that support the construction of large scale distributed systems which have become increasing relevant now-a-days.

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.

Knowledge:

• 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.

Application:

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

• Analysing distributed algorithms.

• Programming distributed systems.

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. Case studies.

Main course reading:

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

• C. Cachin, R. Guerraoui, L. Rodrigues "Introduction to Reliable and Secure Distributed Programming", 2nded, 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, pp72-­82.

Although the course has no additional requirements beyond those related with the degree structure, the following aspects should be taken into consideration by students that aims at taking this course:

• Successful completion of the distributed systems course (highly recommended).
• Solid knowledge on computer networks (recommended).
• Solid knowledge in Java programming (recommended).
• Knowledge regarding the operation of operative systems based on Linux (highly beneficial).