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

Quinto Semestre, Computación Distribuida

Las clases serán impartidas en sesiones de Google Meet y se llevará la organización en un grupo de Classroom los cuáles se darán a conocer en la primer sesión.

Liga meet: https://meet.google.com/oog-akca-yca

Código classroom: ndjn2vo

Cómputación Distribuida 2023-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) y en Java para el caso de Kafka.

Temario

Introducción

1. Definición formal de sistema distribuido.
2. ¿Cómo se mide complejidad en sistemas distribuidos?
3. Definición del modelo síncrono, gráfica arbitraria, sin fallas (SANF)
4. Algoritmos sobre el modelo SANF

• Broadcast, convercast
• Spanning Trees, BFS, DFS
• Bellman–Ford’s
• Vertex coloring, Maximal Independent Set
• Leader election en anillos

Bibliografı́a:
1. ”Distributed Algorithms for Message-Passing Systems” de Michel Raynal

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

• t + 1 rondas
• 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

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
10. Problemas con soluci´on en el modelo asíncrono

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

• ¿Qué es una blockchain?
• Prueba de trabajo
• Bitcoin y consenso
• Otros blockchain
• Asset transfer object

Herramientas de desarrollo y su relación con el cómputo distribuido

• Github
• Docker
• Kafka

Exposiciones
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:

• 16 Tareas (1 por semana) 30%
• 3 Exámenes (1 al mes aproximadamente) 30%
• Investigación: exposición + reporte 25%
• 8 Prácticas de laboratorio 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 3 exámenes. Habrá una sola reposición de examen.