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
Rodrigo Seromenho Miragaia Rodrigues
Weekly hours
4
Total hours
56
Teaching language
Português
Objectives
The central 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 algorithms that are used by the systems that are in use today, and by learning the fundamental ideas that were useful in their design, and that might be useful in the design of the distributed systems that will be used in the future. The course has a strong algorithmic component, but is also accompanied by a set of programming projects, which put in practice the fundamental concepts learned in lectures.
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 in to build distributed systems
• Analyzing distributed algorithms
• Programming distributed systems
Subject matter
1. Distributed computation models
1.1. Modeling processes, faults, crypto primitives and communication.
1.2. Synchronous, asynchronous and partially synchronous models.
2. Replication, fault tolerance, and respective fundamental abstractions
2.1. Broadcast communication
2.2. Basic abstractions to support replication: consensus and variants
2.3. Quorum protocols. Byzantine replication.
2.4. Specifying replicated systems: different consistency levels
3. Scalability
3.1. Peer-to-peer systems
3.2. Other techniques for scaling distributed systems. The HDFS case study
4. Distributed transactions
4.1. Two-phase commit
4.2. Three-phase commit
4.3. Logging for fault tolerance
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
edition, 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 No. 10, Pages
72-82.
Evaluation method
Course evaluation policy
Components
- "Attendance" evaluation with a weight of 50%.
- Two theoretical quizzes or one repeat exam with a total weight of 50%. Both quizzes have the same weight.
- Final grades are rounded to the nearest integer. Intermediate grades are rounded to the decimal point.
"Attendance" evaluation
This comprises two mandatory components:
- Project with several stages to be completed in groups of three.
- Practical quizzes which are: individual, broken into stages, focused on the project, done during a subset of the labs, graded with marks between 0 and 1.
The grade for this part of the evaluation is computed as follows:
- Attendance grade = Project grade * practical quiz grade
In the project description we will detail the stage breakdown.
Requirements for passing 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 worth 50%. The attendance evaluation shall be unchanged in case of students taking the course grade improvement exam.