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

• 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 Topics, 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
     • t + 1 rondas
     • Early stoping
  4. Indistinguibilidad
  5. Fallas bizantinas
  6. Consenso con fallas bizantinas
  • Bibliografı́a:
    1. "Distributed Computing: Fundamentals, Simulations and Advanced Topics, 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 Topics, 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 distributed 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 reliable distributed systems. Journal of the ACM (JACM), 43(2), 225-267.
    2. Kshemkalyani, A. D., & Singhal, M. (2011). Distributed computing: principles, algorithms, and systems. Cambridge University Press.
• Blockchains
  1. Introducción a la criptografía
  2. Bitcoin y Ethereum
  3. Relación entre las blockchains y la computación distribuida
  • Bibliografía:
    1. Nakamoto, S. (2008). Bitcoin whitepaper. URL: https://bitcoin.org/bitcoin.pdf
    2. Buterin, V. (2014). A next-generation smart contract and decentralized application platform. white paper, 3(37).

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

Los porcentajes de evaluación son los siguientes:

• Tareas (1 por semana) 40%
• Exámenes (1 al mes) 30%
• Prácticas (1 cada 2 semanas, 5~6 prácticas durante el semestre) 20%
• Exposición (1 al final de semestre) 10%

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 (promedio mínimo de todos los exámenes con 6). Tendremos 4 exámenes, uno al mes. Las tareas serán dejadas los días martes y serán entregadas al siguiente martes, por lo que serán semanales y sin prórroga debido a que llevamos un calendario. También existirá la opción de presentar un examen final, pero renunciando a la calificación que se haya obtenido previamente.