Curso: Análisis y Diseño de Algoritmos Distribuidos en Redes

Diagrama de temas

General

Objetivo: El objetivo del curso es estudiar la algoritmia de la computación distribuida, es decir, cómo resolver problemas y realizar tareas eficientemente en un ambiente de computación distribuida.
El curso está basado en el libro "Design and Analysis of Distributed Algorithms" de Nicola Santoro: https://people.scs.carleton.ca/~santoro/DADA.html


Este año (2024) el curso también se realizará de forma remota via zoom, y semi-interactiva, es decir que sólo habrá algunas clases de consulta durante el semestre y la actividad principal será en el EVA del curso, sus foros, etc. Las sesiones de zoom serán los martes y jueves de 16 a 18hs: https://salavirtual-udelar.zoom.us/j/86275946690?pwd=VWVIVllEcmpYTEE5NncxeUNpckpiQT09 Las clases están grabadas y disponibles en OpenFING: https://open.fing.edu.uy/courses/adadr Todos aquellos que se inscriban en el curso en bedelía, por favor háganlo también en este EVA.

Tema 1
Tema 2

Destacado
Tema 3
- Simulador
- Grabación de la presentación del simulador 2024 URL
- Entrega Problema 2.9.4 (Ranking) Tarea
  
  .Considere un grafo generico donde cada entidad x tiene un valor inicial v(x); estos valores no son necesariamente distintos. El rank de una entidad x será el rank de su valor, esto es, rank(x) = 1 + |{y en v:v( y ) < v( x )}| (la entidad que tenga el menor valor tendrá rank 1). Diseñe un protocolo eficiente para determinar el rank de todas las entidades, pruebe su correctitud y analice su complejidad. Implemente el protocolo en el simulador.
  
  Se asume:
  - Links bidireccionales
  - Confiabilidad total
  - Mensajes en orden
  - Iniciador único
Tema 4
- clase 6 - ring Archivo
- clase 7 - hypercube Archivo
- clase 8 - complete Archivo
- clase 9 - megamerger Archivo
- Presentación de Megamerger 2024 URL
- Entrega Ejercicio 3.10.1 Tarea
- Entrega Ejercicio 3.10.2 Tarea
- Entrega Ejercicio 3.10.29 - IMPLEMENTAR EN SIMULADOR Tarea
- Entrega Ejercicio 3.10.74 Tarea
- Entrega Ejercicio 3.10.81 Tarea
- Para la resolución del ejercicio 3.10.74 pueden ser útiles los siguientes papers:
  Chan, M.Y., Chin, F.Y.L. Distributed election in complete networks. Distrib Comput 3, 19–22 (1988). https://doi.org/10.1007/BF01788564
  (accesible mediante el Portal Timbó: https://foco.timbo.org.uy/home)
  Yehuda Afek and Eli Gafni. 1985. Time and message bounds for election in synchronous and asynchronous complete networks. In Proceedings of the fourth annual ACM symposium on Principles of distributed computing (PODC '85). Association for Computing Machinery, New York, NY, USA, 186–195. https://doi.org/10.1145/323596.323613
  (accesible directamente en la Digital Library de ACM)
  Para entender megamerger y la resolución del ejercicio 3.10.81puede ser útil usar este simulador
  https://github.com/bidiu/mega-merger/releases/tag/0.9.1
Tema 5
- clases 10, 11 y 12 Archivo
- Entrega Ejercicio 4.6.7 Tarea
- Entrega Ejercicio 4.6.8 Tarea
- Entrega Ejercicio 4.6.14 Tarea
- Entrega Ejercicio 4.6.40 Tarea
- Sparser: A Paradigm for Running Distributed Algorithms Archivo
  
  Y. Afek, M. Ricklin, Sparser: A Paradigm for Running Distributed Algorithms, Journal of Algorithms, Volume 14, Issue 2, 1993, Pages 316-328, ISSN 0196-6774, https://doi.org/10.1006/jagm.1993.1016.
- Efficient Protocols for Computing the Optimal Swap Edges of a Shortest Path Tree Archivo
  
  Flocchini, P., Enriques, A.M., Pagli, L., Prencipe, G., Santoro, N. (2004). Efficient Protocols for Computing the Optimal Swap Edges of a Shortest Path Tree. In: Levy, JJ., Mayr, E.W., Mitchell, J.C. (eds) Exploring New Frontiers of Theoretical Informatics. IFIP International Federation for Information Processing, vol 155. Springer, Boston, MA. https://doi.org/10.1007/1-4020-8141-3_14
Tema 6
- Laboratorio 2024 Archivo