Algorithms and Distributed Systems
Objectives
A unidade curricular (UC) visa consolidar e desenvolver os conhecimentos na área de Sistemas Distribuídos para a compreensão e construção de sistemas distribuídos e descentralizados complexos. Procura-se um bom domínio dos problemas e ideias fundamentais que estão na base do desenho de sistemas atuais, de uso corrente, e das técnicas que potencialmente serão importantes para os sistemas a desenvolver no futuro.
A UC tem uma forte componente algorítmica, mas é também acompanhada de projetos de programação que coloca em prática os conceitos fundamentais que são nela ensinados, permitindo aos alunos tomarem consciência sobre algumas subtilezas relacionadas com a implementação de algoritmos aprendidos na UC.
Saber:
• Conceitos de base para a análise e síntese de algoritmos distribuídos.
• Abstrações fundamentais para a construção de sistemas distribuídos e a sua realização algorítmica.
• Técnicas para melhorar a fiabilidade e a escalabilidade dos sistemas distribuídos.
Saber Fazer:
• Construção de algoritmos distribuídos e a sua aplicação no desenvolvimento de sistemas distribuídos.
• Análise de algoritmos distribuídos.
• Programação de sistemas distribuídos.
General characterization
Code
10644
Credits
6.0
Responsible teacher
Alexander Andrew Davidson, João Carlos Antunes Leitão
Hours
Weekly - 4
Total - 56
Teaching language
Portuguê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): 55%
- each midterm has the same weight for this component.
- midterms will be made in person if conditions allow for it.
- if midtems can be in person, each student can take up to two A4 pages, manuscripted with whatever information they want. These are delivered at the end of the midterm and must be identified with name and number.
project (in two phases, and conducted in groups of 3 students): 35%
- first phase has a weight of 40% in this component, and the second phase a weight of 60%.
Individual homeworks (provided in lectures, and delivered before the start of the following lecture): 10%
- each homework has the same weight for this component.
Components resuts are rounded up to the 2 decimal place, and final grade rounded up to units.
The course has mandatory frequency. To get approval at frequency the student must have a final grade >= 8.5 at the project.
Tools based on generative AI can only be used for acelerating the writting of small pieced of repetitive code and not to build the main logic of projects. Violations of the rule will yield a zero in the practical component.
Subject matter
1. Distributed computation models:
1.1. Modelling processes, faults, crypto primitives and communication.
1.2. Synchronous, asynchronous and partially synchronous models.
1.3. Communication Primitives (Best-effort, exactly once, Broadcast).
2. Peer-to-Peer Systems:
2.1. Unstructured Overlay networks.
2.2. Gossip Protocols.
2.3. Structured Overlay networks.
2.4. Consistent Hashing and Routing.
2.5. Case studies.
3. Consensus:
3.1. Consensus in Synchronous Systems.
3.2. Consensus in Asynchronous Systems & FLP.
3.3. Paxos and some variants.
4. Replication and Fault Tolerance:
4.1. Specifying replicated systems.
4.2. Active Replication and Passive Replication.
4.3. Strong Consistency: State Machine Replication.
4.4. Weak Consistency: CAP theorem, eventual consistency, causal consistency.
4.5. Case studies.
5. Distributed transactions:
5.1. Two-phase commit.
5.2. Three-phase commit.