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

Quinto Semestre, Computación Distribuida

Código del clasroom: hax1fah

Cómputación Distribuida 2020-1

En este curso veremos los principios de la computación distribuida, distintos modelos de sistemas distribuidos y algoritmos para estos. Este es un curso más teórico que práctico, por lo que no tendremos sesiones de laboratorio.

Temario

Introducción
1. ¿Qué es un sistema distribuido?
2. ¿Cómo se mide complejidad en sistemas distribuidos?

Bibliografı́a:
1. ”Distributed Computing Pearls” de Gadi Teubenfel

Construcciones básicas
1. Definición del modelo (sı́ncrono, gráfica árbitraria, sin fallas)
2. Broadcast, convercast
3. Spanning trees, BFS, DFS
4. Leader election en anillos
5. Vertex coloring, MIS
Bibliografı́a:
1. ”Distributed Computing: A Locality-Sensitive Approach” de David Peleg
2. ”Distributed Computing: Fundamentals, Simulations and Advanced Top-
ics, Second Edition” de Hagit Attiya y Jennifer Welch

Tolerancia a fallos
1. Consenso en gráficas completas sin fallas
2. Modelo sı́ncrono con tolerancia a fallos
3. Consenso en sistemas propensos a fallas
(a) t + 1 rondas
(b) Early stoping
4. Indistinguibilidad
5. Fallas bizantinas
6. Consenso con fallas bizantinas
Bibliografı́a:
1. ”Distributed Computing: Fundamentals, Simulations and Advanced Top-
ics, Second Edition” de Hagit Attiya y Jennifer Welch
2. ”Distributed Algorithms for Message-Passing Systems” de Michel Raynal
3. ”Distributed Computing Pearls” de Gadi Teubenfel

Sistemas ası́ncronos
1. Relojes y hora universal
2. Relación de causalidad
3. La relación happens before
4. Relojes de Lamport
5. Relojes vectoriales
6. Cortes consistentes
7. Snapshots
8. Algoritmo de sincronización de relojes (opcional)
9. Consenso en modelos ası́ncronos
Bibliografı́a:
1. ”Distributed Computing: Fundamentals, Simulations and Advanced Top-
ics, Second Edition” de Hagit Attiya y Jennifer Welch
2. ”Distributed Algorithms for Message-Passing Systems” de Michel Raynal
3. Lamport, L. (1978). Time, clocks, and the ordering of events in a dis-
tributed system. Communications of the ACM, 21(7), 558-565.

Detectores de fallos
1. Introducción y jerarquı́a
2. Detector eventualmente perfecto (♦P )
3. Detector fuerte (S)
4. Algoritmo del consenso usando detectores de fallos
5. Reducciones entre detectores de fallos
Bibliografı́a:
1. Chandra, T. D., & Toueg, S. (1996). Unreliable failure detectors for reli-
able distributed systems. Journal of the ACM (JACM), 43(2), 225-267.
2. Kshemkalyani, A. D., & Singhal, M. (2011). Distributed computing: prin-
ciples, algorithms, and systems. Cambridge University Press.

Blockchains
Seminario impartido por Miguel Piña

Expos
Los alumnos presentarán diferentes tópicos avanzados en equipos y presentarán
un trabajo escrito al finalizar el semestre.

Evaluación
Los porcentajes de evaluación son los siguientes:
• Tareas 50%
• Exámenes 30%
• Exposición 20%
Para tener una calificación aprobatoria en el curso, es necesario tener promedio aprobatorio en los exámenes. SIN PROMEDIO APROBATORIO EN LOS EXÁMENES NO SE PUEDE APROBAR EL CURSO. Tendremos 4 exámenes, uno al mes. Las tareas se serán entregadas al ayudante los dı́as martes y el lunes anterior se les dejará la siguiente tarea, por lo que serán semanales y sin prórroga debido a que llevamos un calendario.