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

Quinto Semestre, Computación Distribuida

ENLACE PRIMERA CLASE https://meet.google.com/skr-ewgq-ago

Código Classroom: w6h4p4o

Cómputación Distribuida 2021-1

En este curso veremos los principios de la computación distribuida, distintos modelos de sistemas distribuidos y algoritmos para estos. Aprenderemos a llevar a cabo simulaciones de estos algoritmos, por lo que programaremos en Python utilizando la biblioteca SimPy (https://simpy.readthedocs.io/en/latest/simpy_intro/index.html).

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

1. ¿Qué es una blockchain?
2. Bitcoin y consenso
3. Asset transfer object

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 serán los siguientes:

• Tareas (1 por semana) 30%
• Tarea exámen (1 al mes) 30%
• Prácticas (1 cada 2 semanas) 30%
• Exposición (1 al final del semestre) 30%

Entendemos perfectamente que estamos pasando por una situación extraordinaria y que debemos ser lo más comprensivos posible, por lo que la suma de los porcentajes es 120 :) pero importante: Para tener una calificación aprobatoria en el curso, es necesario tener promedio aprobatorio en las tareas examen. SIN PROMEDIO APROBATORIO EN LOS EXÁMENES NO SE PUEDE APROBAR EL CURSO. Las tareas se entregarán en google Classroom.

Clases

Las clases serán impartidas por google meet. Todo el equipo (prof y ayudantes) cuenta con una tableta de dibujo para poder compartir ideas de forma más sencilla. La clase será a la hora indicada en esta página.