Algorithms and Distributed Systems
Code
10644
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Informática
Credits
6.0
Teacher in charge
João Carlos Antunes Leitão, Nuno Manuel Ribeiro Preguiça
Weekly hours
4
Total hours
56
Teaching language
Português
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.
Prerequisites
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).
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. Case studies.
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.
Evaluation method
Course evaluation policy:
* Evaluation Componentes:
• "Attendance" evaluation with a weight of 45% in the final grade.
• Four individual home works with a weight of 10% in the final grade.
• Two theoretical quizzes or one repeat exam with a total weight of 45% in the final grade. Both quizzes have the same weight for this component.
• Final grades are rounded to the nearest integer. Intermediate grades are rounded to the decimal point.
Attendance Evaluation:
* This component has the following aspects:
• Project with several stages to be completed in groups of three students.
• A presencial discussion in the end of the semester, with a final score between zero and one (Discussion grades are individual).
The attendance final grade is computed through the following equation:
• Atendance grade = Project grade * Discussion score.
In the project description there will be a description of the multiple stages of the project and tweir relative weight for the project grade.
Home works:
• The home works, which will be four distributed along the semester, will be presented in the end of lectures, and should be delivered to the course professor by the start of the following lecture (in exceptional cases these can be delivered by e-mail before the start of the following lecture).
• Home works should be solved individually by each student.
Requirements for approavel in the course:
1. Attendance grade greater or equal than 8,5;
2. Either the average of the two theoretical quizzes or the repeat exam greater or equal than 8.5, and
3. Final course grade greater or equal than 9,5.
Course grade improvement:
A re-exam for improving the course grade is possible in order to improve the quizzes/exam component of the grade (which is worth 45%). The attendance evaluation and home works grades shall remain unchanged in case of students taking the course grade improvement exam.