Algorithms and Distributed Systems
Objectives
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.
General characterization
Code
10644
Credits
6.0
Responsible teacher
João Carlos Antunes Leitão, Nuno Manuel Ribeiro Preguiça
Hours
Weekly - 4
Total - 56
Teaching language
Inglês
Prerequisites
Fundamental knowledge of distributed systems and Java programming.
Bibliography
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.