Ciencias de la Computación (plan 2013) 2025-1

Quinto Semestre, Computación Distribuida

Temario de Computación Distribuida

1. Introducción a los sistemas distribuidos
   • Sistemas distribuidos síncronos y asíncronos
   • Sistemas de paso de mensaje y complejidades
2. Algoritmos básicos sobre árboles generadores
   • Algoritmos de difusión y convergencia
   • Algoritmos sobre un árbol generador
   • Algoritmos BFS y DFS distribuidos
3. Elección de líder en anillos
   • Problema de elección de líder
   • Algoritmos de elección de líder síncronos y asíncronos
4. Consenso con tolerancia a fallas
   • Problema del ataque coordinado y problema de los generales
   • Algoritmo de consenso en presencia de fallas
   • Modelo con fallas bizantinas
   • Difusión confiable en presencia de procesos bizantinos
   • Algoritmo del consenso polinomial en presencia de fallas bizantinas
5. Relojes en sistemas distribuidos
   • Relojes lógicos
   • Relojes físicos
   • Relojes vectoriales
   • Problema de sincronización de relojes
6. Detectores de fallas
   • Detector de fallas de la clase S
   • La clase de detectores de fallos de cuórum
7. Sincronizadores
   • Sincronizadores alfa, beta y gamma
   • Aplicación de sincronizadores a elección de líder y BFS

Evaluación del curso

• 30% Tareas
• 30% Exámenes
• 40% Laboratorio (Python)

Referencias

1. James Aspnes. Notes on theory of distributed systems, 2022.
2. H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. Wiley Series on Parallel and Distributed Computing. Wiley, 2004.
3. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996.
4. David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, USA, 2000.
5. Michel Raynal. Distributed Algorithms for Message-Passing Systems. 07 2013.
6. Michel Raynal. Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach. Springer International Publishing, 2018.
7. Roger Wattenhofer. Principles of Distributed Computing. 2016. https://disco.ethz.ch/courses/podc_allstars/lecture/podc.pdf.