Teaching Guide Information

Presentation

We are witnessing an explosion of devices that can connect us to each other and connect among themselves. This has created many opportunities to develop distributed network applications. These are applications where data and computation are distributed among many devices and where, in principle, all the devices send and receive data and benefit from the computation of the group. Applications range from Home Automation to Cryptocurrencies. Complementary to this evolution we are also seeing many computing services being moved to cloud environments. These are computational environments where computation is distributed into, many times, tens of thousands of computers to serve millions of users. Hence, it is becoming essential for any computer professional to have a good understanding of what it means to program in a distributed environment.

The goals of this course are to introduce students to some of the core foundational concepts in distributed computing and study different distributed algorithms. The emphasis will be on algorithms in which computational nodes communicate  asynchronously exchanging messages. There will be lectures where algorithms will be introduced and student will be able to solidify the concepts through several small and medium programming  projects and exercises. The course starts with the introduction of simple traversal algorithms and ends with Byzantine Consensus, the basis of public blockchain implementations.

Associated skills

Transversal competences

CT3. Applying with flexibility and creativity the acquired knowledge and adapting it to new contexts and situations.

Specific competences

CE7. Mastering the concepts and principles of a computer’s inner functioning
as well as of the communication among computers, which allows the analysis
and assessment of computer structures, including parallel and distributed
platforms.

CE11.Solving complex computational problems using the principles and
techniques of intelligent systems.

Learning outcomes

RA.CE7.4 Detect and assess the principles and techniques of parallel and
distributed programming.

RA.CE7.5 Analyze the features, structures and techniques associated with
distributed systems.

RA.CE11.6 Use advanced algorithms considering distribution and
complexity aspects.

Sustainable Development Goals

There will be some discussion of the environmental impact of data centers and crypto currencies.

Prerequisites

Students must have knowledge of basic graph concepts such as the ones covered in “Linear Algebra and Discrete Mathematics”, understanding of asymptotic complexity analysis notation as  is covered in “Programming Fundamentals”, as well as programming skills as the ones covered in “Data Structures and Algorithms” and in “Development of Distributed Applications” or “Protocols and Distributed Applications”.

Contents

1. Preliminaries

• Motivation: Routing/Broadcasting/Multicasting/Skype/File Sharing, Fault tolerance, ZooKeeper, Hadoop - NLP

• Our computational model: General overview of distributed computation, Asynchronous computational model using message passing, Clocks, Safety and liveness

• Notions of computational complexity in distributed algorithms

2. Waves

3. Leader elections

4. Spanning trees

5. Anonymous networks

6. Fault tolerance/ Consensus

7. A topic on advanced applications of Byzantine Consensus such Blockchains or Privacy

Teaching Methods

Evaluation

Bibliography and information resources

The course will mostly follow the book “Distributed Algorithms, An Intuitive Approach” by Wan Fokkink.

Other references for optional topics:

Lindell, Yehuda. Secure multiparty computation. Communications of the ACM 64.1 (2020): 86-96.

Gilad, Y., Hemo, R., Micali, S., Vlachos, G., & Zeldovich, N. (2017, October). Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th symposium on operating systems principles (pp. 51-68).

Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan. 2003. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Trans. Netw. 11, 1 (February 2003), 17-32.

Información de la Guía Docente

Presentación

Estamos presenciando una explosión de dispositivos que pueden conectarnos entre sí y conectarse entre sí. Esto ha creado muchas oportunidades para desarrollar aplicaciones de red distribuida. Se trata de aplicaciones donde los datos y la computación se distribuyen entre muchos dispositivos y donde, en principio, todos los dispositivos envían y reciben datos y se benefician del cómputo del grupo. Las aplicaciones van desde la automatización del hogar hasta las criptomonedas. Como complemento a esta evolución, también estamos viendo que muchos servicios informáticos se han trasladado a entornos en la nube. Se trata de entornos computacionales donde la computación se distribuye muchas veces entre decenas de miles de ordenadores para dar servicio a millones de usuarios. Esto sugiere que cualquier profesional de la informática se beneficia al tener una buena comprensión de lo que significa programar en un entorno distribuido.

Los objetivos de este curso son presentar a los estudiantes algunos de los conceptos fundamentales básicos en computación distribuida y estudiar diferentes algoritmos distribuidos. El énfasis estará en los algoritmos en los que los nodos computacionales se comunican de forma asincrónica intercambiando mensajes. Habrá sesiones donde se introducirán algoritmos y el estudiante podrá solidificar los conceptos a través de varios proyectos y ejercicios de programación pequeños y medianos. El curso comienza con la introducción de algoritmos transversales simples y termina con Byzantine Consensus, la base de las implementaciones públicas de blockchain

Competencias asociadas

Competencias transversales

CT3. Aplicar con flexibilidad y creatividad los conocimientos adquiridos y de adaptarlos a contextos y situaciones nuevas.

Competencias específicas

CE7. Dominar los conceptos y principios del funcionamiento interno de un
ordenador así como de la comunicación entre ordenadores, que permita el
análisis y evaluación de estructuras de computadores, incluyendo plataformas
paralelas y distribuidas.

CE11.Solucionar problemas complejos de computación utilizando los principios
y técnicas de los sistemas inteligentes.

Resultados del aprendizaje

RA.CE7.4 Detecta y evalúa los principios y técnicas de la programación
paralela y distribuida.
RA.CE7.5 Analiza las características, estructuras y técnicas asociadas a
los sistemas distribuidos.

RA.CE11.6 Usa algoritmos avanzados considerando aspectos de
distribución y complejidad.

Objetivos de Desarrollo Sostenible

Habrá algunas discusiones sobre el impacto ambiental de los centros de datos y el uso de algunas de las criptomonedas.

Prerrequisitos

Los estudiantes deben tener conocimiento de los conceptos básicos de grafos, tales como los tratados en "Álgebra Lineal y Matemática Discreta", conocer la notación de complejidad asintótica usada en el análisis del algoritmos al nivel que se estudia en "Fundamentos de programación", así como los conocimientos de programación cubiertos en "Estructuras de Datos y Algoritmos ", y uno de los cursos: " Desarrollo de aplicaciones distribuidas "o" Protocolos y aplicaciones distribuidas”.

Contenidos

1. Preliminares:

• motivación: Enrutamiento / Broadcasting / Multicasting / Skype/File Sharing /  Tolerancia a fallos, ZooKeeper , Hadoop – Procesamiento de lenguaje natural
• Nuestro modelo computacional : Panorama general de la computación distribuida, modelo computacional asíncrono mediante el paso de mensajes , Relojes , propiedades “safety” y “liveness”
• Nociones de complejidad computacional en algoritmos distribuidos

2. Ondas

3. elecciones de Líder

4. árboles de expansión (spanning trees)

5. Redes anónimas

6. Consenso/Tolerancia a fallas

7. Un tema a elegir sobre aplicaciones avanzadas del consenso bizantino como Blockchains o Privacidad

Metodología docente

Evaluación

Habrá un examen a mitad del trimestre, un examen final y tareas de programación y ejercicios escritos.

La distribución de la nota final será: 

• Tareas 30%
• Examen a mitad de termino 30%
• Examen final 40%

Es necesario obtener por lo mínimo la mitad de la nota total en las tareas para pasar el curso

Bibliografía y recursos de información

El curso se seguirá en gran parte el libro “Distributed Algorithms, An Intuitive Approach” de Wan Fokkink.

Otras referencias:

Lindell, Yehuda. Secure multiparty computation. Communications of the ACM 64.1 (2020): 86-96.
Gilad, Y., Hemo, R., Micali, S., Vlachos, G., & Zeldovich, N. (2017, October). Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th symposium on operating systems principles (pp. 51-68).

Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, and Hari Balakrishnan. 2003. Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Trans. Netw. 11, 1 (February 2003), 17-32.