Sistemas Distribuidos en Red

• Horas semanales
• Competencias
• Objetivos
• Contenidos
• Actividades
• Metodología docente
• Método de evaluación
• Bibliografía
• Capacidades previas

Profesorado

Responsable

• Jordi Guitart Fernandez ( )

Horas semanales

Competencias

Competencias Técnicas

Competencias técnicas comunes

• CT5 - Analizar, diseñar, construir y mantener aplicaciones de forma robusta, segura y eficiente, escogiendo el paradigma y los lenguajes de programación más adecuados.
  • CT5.6 - Demostrar conocimiento y capacidad de aplicación de los principios fundamentales y de las técnicas básicas de la programación paralela, concurrente, distribuida y de tiempo real.
• CT6 - Demostrar conocimiento y comprensión del funcionamiento interno de un computador y del funcionamiento de las comunicaciones entre ordenadores.
  • CT6.4 - Demostrar conocimiento y capacidad de aplicación de las características, las funcionalidades y la estructura de los Sistemas Distribuidos, de las Redes de Computadores y de Internet que permita su uso y su administración, así como el diseño y la implementación de aplicaciones basadas en ellas.

Competencias Técnicas de cada especialidad

Especialidad tecnologías de la información

• CTI1 - Definir, planificar y gestionar la instalación de la infraestructura TIC de la organización.
  • CTI1.3 - Seleccionar, desplegar, integrar y gestionar sistemas de información que satisfagan las necesidades de la organización con los criterios de costo y calidad identificados.
• CTI3 - Diseñar soluciones que integren tecnologías de hardware, software y comunicaciones (y capacidad de desarrollar soluciones específicas de software de sistemas) para sistemas distribuidos y dispositivos de computación ubícua.
  • CTI3.1 - Concebir sistemas, aplicaciones y servicios basados en tecnologías de red, incluyendo Internet, web, comercio electrónico, multimedia, servicios interactivos y computación ubicua.
  • CTI3.2 - Implementar y gestionar sistemas ubicuos (mobile computing systems).
  • CTI3.4 - Diseñar software de comunicaciones.

Competencias Transversales

Lengua extranjera

• G3 [Avaluable] - Conocer el idioma inglés con un nivel adecuado de forma oral y por escrito, y con consonancia con las necesidades que tendrán los graduados y graduadas en ingeniería informática. Capacidad de trabajar en un grupo multidisciplinar y en un entorno multilingüe, y de comunicar, tanto por escrito como de forma oral, conocimientos, procedimientos, resultados e ideas relacionadas con la profesión de ingeniero técnico en informática.
  • G3.1 - Comprender y utilizar eficazmente manuales, especificaciones de productos y otra información de carácter técnico escrita en inglés.

Objetivos

1. Entender la definición de sistema distribuido y sus posibles aplicaciones, además de los desafíos que se deben afrontar para su diseño e implementación.
   Competencias relacionadas: CTI3.1, CTI3.4, CT6.4, CTI1.3,
   Subcompetences:
   • Conocer las posibles aplicaciones de un sistema distribuido
   • Poner ejemplos de sistemas distribuidos
   • Entender los desafíos para diseñar e implementar un sistema distribuido: heterogeneidad, ausencia de visión global, seguridad, coordinación, asincronía, apertura, transparencia, tolerancia a fallos, escalabilidad
   • Entender la definición de sistema distribuido
2. Conocer las arquitecturas de sistema básicas en los sistemas distribuidos.
   Competencias relacionadas: CTI3.1, CTI3.4, CT6.4, CT5.6,
   Subcompetences:
   • Conocer las arquitecturas de sistema básicas en los sistemas distribuidos: centralizadas (cliente-servidor), descentralizadas (peer-to-peer), híbridas
3. Conocer los mecanismos básicos de comunicación en un sistema distribuido: invocación de operaciones remotas, comunicación basada en mensajes, comunicación basada en eventos y comunicación basada en canales (streams), y escribir aplicaciones distribuidas que se comuniquen mediante el envío de mensajes.
   Competencias relacionadas: CTI3.1, CTI3.4, CT6.4, CTI1.3, CT5.6,
   Subcompetences:
   • Conocer los paradigmas de comunicación básicos en los sistemas distribuidos: invocación remota de procedimiento, paso de mensajes, colas de mensajes, comunicación de grupos, publicación/subscripción, espacios de datos compartidos, memoria compartida, código móvil, orientado a stream
   • Escribir aplicaciones distribuidas que se comuniquen mediante el envío de mensajes
   • Conocer el mecanismo de comunicación basada en streams: modos de transmisión, calidad de servicio
   • Conocer el mecanismo de comunicación basada en eventos: sistemas de publicación/subscripción
   • Conocer los diferentes tipos de comunicación en un sistema distribuido: directa vs. indirecta (desacoplamiento espacial y temporal), persistente vs. transitoria, síncrona vs. asíncrona, discreta vs. continua
   • Conocer el mecanismo de comunicación basada en mensajes: transitoria (Sockets) vs. persistente (MOM)
   • Conocer el mecanismo de comunicación mediante la invocación de procedimientos remotos (RPC): operación básica, paso de parámetros, extensiones del modelo básico, tratamiento de fallos, invocación de métodos remotos (RMI)
4. Entender la problemática del tiempo y la ordenación de eventos en un sistema distribuido y explicar e implementar los mecanismos de relojes lógicos para atacar esta problemática y los algoritmos para sincronizar relojes físicos en un sistema distribuido.
   Competencias relacionadas: CTI3.1, CT6.4, CTI1.3, CT5.6,
   Subcompetences:
   • Entender la problemática del tiempo y la ordenación de eventos en un sistema distribuido
   • Explicar e implementar los algoritmos para sincronizar relojes físicos en un sistema distribuido: Cristian (NTP), Berkeley
   • Explicar e implementar los mecanismos de relojes lógicos para atacar esta problemática: relación happened-before, relojes lógicos de Lamport (escalares, vectoriales)
5. Describir, comparar e implementar los algoritmos para la coordinación de procesos en un sistema distribuido, incluyendo la coordinación necesaria para garantizar exclusión mutua, elección de líder, comunicación en grupo multicast, y consenso.
   Competencias relacionadas: CTI3.1, CT6.4, CTI1.3, CT5.6,
   Subcompetences:
   • Describir, comparar e implementar los algoritmos para la coordinación de procesos en un sistema distribuido para garantizar exclusión mutua: algoritmos basados ​​en permiso (centralizado, Lin, Maekawa, Ricart & Agrawala), algoritmos basados ​​en token (token ring)
   • Describir, comparar e implementar los algoritmos para la coordinación de procesos en un sistema distribuido para la comunicación en grupo multicast: multicast fiable básico, multicast fiable escalable, multicast ordenado (FIFO, causal, total), atomic multicast
   • Describir, comparar e implementar los algoritmos para la coordinación de procesos en un sistema distribuido para la elección de líder: Bully, Ring
6. Comprender la aplicación de la replicación en un sistema distribuido, además de la problemática que se introduce a nivel de consistencia, y describir los modelos de consistencia correspondientes y su implementación.
   Competencias relacionadas: CTI3.1, CT6.4, CTI1.3, CTI3.2, CT5.6,
   Subcompetences:
   • Describir implementaciones concretas de modelos de consistencia: protocolos basados ​​en primario (remote-write, local-write) y protocolos de escritura replicada (replicación activa, protocolos basados ​​en quórum)
   • Comprender la aplicación de la replicación en un sistema distribuido, además de la problemática que se introduce a nivel de consistencia
   • Describir los modelos de consistencia relajada centrados en los datos: uso de variables de sincronización
   • Describir los modelos de consistencia centrados en el cliente: eventual, monotonic-read, monotonic-write, read-your-writes, writes-follow-reads
   • Conocer los detalles de implementación de los modelos de consistencia en relación a la ubicación de las réplicas (permanentes, iniciadas por el servidor, iniciadas por el cliente) y la propagación de actualizaciones (push-pull protocols)
   • Describir los modelos de consistencia fuerte centrados en los datos: estricta, secuencial, causal, FIFO
7. Conocer y comparar las características básicas de los servicios de resolución de nombres planos, estructurados y basados ​​en atributos, e implementar y evaluar uno de estos sistemas.
   Competencias relacionadas: CTI3.1, CT6.4, CTI1.3, CTI3.2,
   Subcompetences:
   • Implementar y evaluar un servicio DNS simple
   • Conocer y comparar las características básicas de los servicios de resolución de nombres planos: broadcasting, forwarding pointers, soluciones basadas en home, DHTs
   • Conocer y comparar las características básicas de los servicios de resolución de nombres estructurados: name spaces, resolución iterativa, resolución recursiva, DNS
   • Conocer y comparar las características básicas de los servicios de resolución de nombres basados ​​en atributos: servicios de directorio (LDAP)
8. Conocer y comparar las características básicas de los sistemas de ficheros distribuidos (e.g. NFS).
   Competencias relacionadas: CTI3.1, CT6.4, CTI1.3, CTI3.2,
   Subcompetences:
   • Comprender la semántica de compartición de ficheros: semántica UNIX, semántica de sesión, ficheros inmutables, semántica transaccional
   • Conocer y comparar las características básicas del sistema de ficheros distribuido NFS
   • Conocer y comparar las características básicas del sistema de ficheros distribuido Coda
   • Conocer las arquitecturas de los sistemas de ficheros distribuidos: modelo de acceso remoto, modelo upload / download, idea básica de las arquitecturas en cluster (stripping + replicación)
9. Conocer y comparar las características básicas de los sistemas distribuidos basados ​​en web: servidores web, servidores de aplicaciones, Web Services, Content Distribution Networks (CDN), e implementar y evaluar uno de estos sistemas.
   Competencias relacionadas: CTI3.1, CTI3.4, CT6.4, CTI1.3, CT5.6,
   Subcompetences:
   • Implementar y evaluar un servidor web simple
   • Conocer los mecanismos de sincronización en los sistemas distribuidos basados ​​en Web
   • Conocer los protocolos de comunicación en los sistemas distribuidos basados ​​en Web: HTTP, SOAP, WSDL
   • Conocer los mecanismos de caching y replicación en los sistemas distribuidos basados ​​en Web: Proxies, Content Distribution Networks (CDN): Akamai, esquemas de redirección (URL rewriting, DNS redirection)
   • Conocer las arquitecturas de los sistemas distribuidos basados ​​en Web: cliente/servidor, servlets, clusters de servidores, Web Services
   • Conocer los servicios de nombres en los sistemas distribuidos basados ​​en Web: URL, DNS, UDDI
10. Comprender el modelo de computación Peer-to-Peer (P2P), comparar las características de los sistemas P2P no estructurados y los estructurados basados ​​en DHTs, e implementar y evaluar uno de estos sistemas.
    Competencias relacionadas: CTI3.1, CT6.4, CTI1.3, CT5.6,
    Subcompetences:
    • Comprender el modelo de computación Peer-to-Peer (P2P), sus ventajas y sus aplicaciones
    • Comparar las características de los sistemas P2P no estructurados centralizados: BitTorrent
    • Comparar las características de los sistemas P2P estructurados basados ​​en DHTs: Chord: organización del anillo, inserción de elementos, búsqueda de elementos con tablas de finger, inserción de nodos
    • Implementar y evaluar un sistema P2P estructurado
    • Comparar las características de los sistemas P2P no estructurados jerárquicos: FastTrack
    • Comparar las características de los sistemas P2P no estructurados descentralizados con búsqueda por inundación: Gnutella
11. Conocer los paradigmas más importantes de computación distribuida (computación voluntaria, Grid y Cloud) y sus características.
    Competencias relacionadas: CTI3.1, CT6.4, CTI1.3,
    Subcompetences:
    • Conocer el paradigma Cloud de computación distribuida, sus características y sus aplicaciones: Utility computing, tipo de Clouds (público, privado, comunitario, híbrido), diferencia respecto al Grid, servicios Cloud (IaaS, PAAS, SaaS), tecnologías base de implementación, infraestructura Cloud (datacenters), obstáculos para la consolidación del Cloud
    • Conocer el paradigma Grid de computación distribuida, sus características y sus aplicaciones: Virtual organizations (VO), arquitectura OGSA, diferencia respecto a la computación cluster y distribuida
    • Conocer el paradigma de computación distribuida voluntaria: BOINC
12. Conocer los paradigmas de Mobile y Ubiquitous Computing y su problemática.
    Competencias relacionadas: CTI3.1, CT6.4, CTI3.2,
    Subcompetences:
    • Conocer los paradigmas de Mobile y Ubiquitous Computing y su problemática: volatilidad, asociación, interoperabilidad, sensores y context-awareness, adaptación
13. Comprender artículos, enunciados, y en general cualquier fuente de información de carácter técnico escrita en inglés
    Competencias relacionadas: G3.1,

Contenidos

1. Conceptos de sistemas distribuidos
   Definición de sistema distribuido. Posibles aplicaciones de un sistema distribuido. Ejemplos de sistemas distribuidos. Desafíos para diseñar e implementar un sistema distribuido: heterogeneidad, ausencia de visión global, seguridad, coordinación, asincronía, apertura , transparencia, tolerancia a fallos, escalabilidad. Arquitecturas de sistema básicas en los sistemas distribuidos: centralizadas (cliente-servidor), descentralizadas (peer-to-peer), híbridas
2. Comunicación entre procesos
   Tipos de comunicación en un sistema distribuido: directa vs. indirecta (desacoplamiento espacial y temporal), persistente vs. transitoria, síncrona vs. asíncrona, discreta vs. continua. Paradigmas de comunicación básicos en los sistemas distribuidos: invocación remota de procedimiento, paso de mensajes, colas de mensajes, comunicación de grupos, publicación/subscripción, espacios de datos compartidos, memoria compartida, código móvil, orientado a stream. Invocación de procedimientos remotos (RPC): operación básica, paso de parámetros, extensiones del modelo básico, tratamiento de fallos, invocación de métodos remotos (RMI). Comunicación basada en mensajes: transitoria (Sockets) vs. persistente (MOM). Comunicación basada en eventos: sistemas de publicación/subscripción. Comunicación basada en streams: modos de transmisión, calidad de servicio
3. Tiempo y ordenación
   Tiempo y ordenación de eventos en un sistema distribuido. Relojes lógicos: relación happened-before, relojes lógicos de Lamport (escalares, vectoriales). Algoritmos para sincronizar relojes físicos en un sistema distribuido: Cristian (NTP), Berkeley.
4. Coordinación y consenso
   Coordinación de procesos en un sistema distribuido para garantizar exclusión mutua: algoritmos basados ​​en permiso (centralizado, Lin, Maekawa, Ricart & Agrawala), algoritmos basados ​​en token (token ring). Coordinación de procesos en un sistema distribuido para la elección de líder: Bully, Ring. Coordinación de procesos en un sistema distribuido para la comunicación en grupo multicast: multicast fiable básico, multicast fiable escalable, multicast ordenado (FIFO, causal, total), atomic multicast.
5. Consistencia y replicación
   Replicación y consistencia en un sistema distribuido. Modelos de consistencia fuerte centrados en los datos: estricta, secuencial, causal, FIFO. Modelos de consistencia relajada centrados en los datos: uso de variables de sincronización. Modelos de consistencia centrados en el cliente: eventual, monotonic-read, monotonic-write, read-your-writes, writes-follow-reads. Ubicación de las réplicas (permanentes, iniciadas por el servidor, iniciadas por el cliente) y propagación de actualizaciones (push-pull protocols). Implementaciones de modelos de consistencia: protocolos basados ​​en primario (remote-write, local-write) y protocolos de escritura replicada (replicación activa, protocolos basados ​​en quórum)
6. Sistemas de nombres
   Servicios de resolución de nombres planos: broadcasting, forwarding pointers, soluciones basadas en home, DHTs. Servicios de resolución de nombres estructurados: name spaces, resolución iterativa, resolución recursiva, DNS. Servicios de resolución de nombres basados ​​en atributos: servicios de directorio (LDAP)
7. Sistemas de ficheros distribuidos
   Arquitecturas de los sistemas de ficheros distribuidos: modelo de acceso remoto, modelo upload / download, idea básica de las arquitecturas en cluster (stripping + replicación). Semántica de compartición de ficheros: semántica UNIX, semántica de sesión, ficheros inmutables, semántica transaccional. Características básicas del sistema de ficheros distribuido Coda
8. Sistemas distribuidos basados ​​en Web
   Arquitecturas de los sistemas distribuidos basados ​​en Web: cliente/servidor, servlets, clusters de servidores, Web Services. Protocolos de comunicación en los sistemas distribuidos basados ​​en Web: HTTP, SOAP, WSDL. Servicios de nombres en los sistemas distribuidos basados ​​en Web: URL, DNS, UDDI. Sincronización en los sistemas distribuidos basados ​​en Web. Caching y replicación en los sistemas distribuidos basados ​​en Web: Proxies, Content Distribution Networks (CDN): Akamai, esquemas de redirección (URL rewriting, DNS redirection)
9. Sistemas Peer-to-Peer (P2P)
   Modelo de computación Peer-to-Peer (P2P): ventajas y aplicaciones. Sistemas P2P no estructurados centralizados: BitTorrent. Sistemas P2P no estructurados descentralizados con búsqueda por inundación: Gnutella. Sistemas P2P no estructurados jerárquicos: FastTrack. Sistemas P2P estructurados basados ​​en DHTs: Chord: organización del anillo, inserción de elementos, búsqueda de elementos con tablas de finger, inserción de nodos; Kademlia: organización del árbol y estado del nodo, búsqueda e inserción de nodos, búsqueda e inserción de elementos.
10. Sistemas de computación distribuida
    Paradigma de computación distribuida voluntaria: BOINC. Paradigma Grid de computación distribuida, sus características y sus aplicaciones: Virtual organizations (VO), arquitectura OGSA, diferencia respecto a la computación cluster y distribuida. Paradigma Cloud de computación distribuida, sus características y sus aplicaciones: Utility computing, tipo de Clouds (público, privado, comunitario, híbrido), diferencia respecto al Grid, servicios Cloud (IaaS, PAAS, SaaS), tecnologías base de implementación, infraestructura Cloud (datacenters), obstáculos para la consolidación del Cloud
11. Sistemas móviles y ubicuos
    Sistemas móviles y ubicuos: volatilidad, asociación, interoperabilidad, sensores y context-awareness, adaptación

Actividades

Actividad Acto evaluativo

Metodología docente

Método de evaluación

Bibliografía

Básica:

• Distributed systems - Steen, M. van ; Tanenbaum, A.S, Pearson Educación, 2017. ISBN: 9781543057386
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004112739706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Distributed systems: concepts and design - Coulouris, G.; [et al.], Addison-Wesley/Pearson Education, 2012. ISBN: 9780273760597
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000675069706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Distributed systems: an algorithmic approach - Ghosh, S, Chapman and Hall/CRC, 2014. ISBN: 9781466552982
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001569699706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementaria:

• Programming Erlang: software for a concurrent world - Armstrong, J, Pragmatic Bookshelf , 2013. ISBN: 9781937785536
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004002229706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Erlang programming - Cesarini, F.; Thompson, S, O'Reilly , 2009. ISBN: 9780596518189
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003712929706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Slides for SDX Lectures - Guitart, J., , .
  https://mwiki.fib.upc.edu/grau-sdx/
• Seminar Assignments for SDX - Guitart, J., , .
  https://mwiki.fib.upc.edu/grau-sdx/

Capacidades previas