Sistemes Distribuïts en Xarxa

• Hores setmanals
• Competències
• Objectius
• Continguts
• Activitats
• Metodologia docent
• Mètode d'avaluació
• Bibliografia
• Capacitats prèvies

Professorat

Responsable

• Jordi Guitart Fernandez ( )

Hores setmanals

Competències

Competències Tècniques

Competències tècniques comunes

• CT5 - Analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, triant el paradigma i els llenguatges de programació més adequats.
  • CT5.6 - Demostrar coneixement i capacitat d'aplicació dels principis fonamentals i de les tècniques bàsiques de la programació paral·lela, concurrent, distribuïda i en temps real.
• CT6 - Demostrar coneixement i comprensió del funcionament intern d'un computador i del funcionament de les comunicacions entre ordinadors.
  • CT6.4 - Demostrar coneixement i capacitat d'aplicació de les característiques, de les funcionalitats i de l'estructura dels Sistemes Distribuïts i de les Xarxes de Computadors i d'Internet que en garanteixi l'ús i l'administració, així com el disseny i la implementació d'aplicacions basades en elles.

Competències Tècniques de cada especialitat

Especialitat tecnologies de la informació

• CTI1 - Definir, planificar i gestionar la instal·lació de la infraestructura TIC de l'organització.
  • CTI1.3 - Seleccionar, desplegar, integrar i gestionar sistemes d'informació que satisfacin les necessitats de l'organització amb els criteris de cost i qualitat identificats.
• CTI3 - Dissenyar solucions que integrin tecnologies de hardware, software i comunicacions (i capacitat de desenvolupar solucions específiques de software de sistemes) per a sistemes distribuïts i dispositius de computació ubiqua.
  • CTI3.1 - Concebre sistemes, aplicacions i serveis basats en tecnologies de xarxa, tenint en compte Internet, web, comerç electrònic, multimèdia, serveis interactius i computació ubiqua.
  • CTI3.2 - Implementar i gestionar sistemes ubics (mobile computing systems).
  • CTI3.4 - Dissenyar software de comunicacions.

Competències Transversals

Tercera llengua

• G3 [Avaluable] - Conèixer l'idioma anglès amb un nivell adequat de forma oral i escrita, i en consonància amb les necessitats que tindran els graduats i les graduades en Enginyeria Informàtica. Capacitat de treballar en un grup multidisciplinar i en un entorn multilingüe i de comunicar, tant per escrit com de forma oral, coneixements, procediments, resultats i idees relacionats amb la professió d'enginyer tècnic en informàtica.
  • G3.1 - Comprendre i utilitzar eficaçment manuals, especificacions de productes i altra informació de caràcter tècnic escrita en anglès.

Objectius

1. Entendre la definició de sistema distribuït i les seves possibles aplicacions, a més dels desafiaments que s'han d'afrontar pel seu disseny i implementació.
   Competències relacionades: CTI3.1, CTI3.4, CT6.4, CTI1.3,
   Subcompetences:
   • Conèixer les possibles aplicacions d'un sistema distribuït
   • Posar exemples de sistemes distribuïts
   • Entendre els desafiaments per dissenyar i implementar un sistema distribuït: heterogeneïtat, absència de visió global, seguretat, coordinació, asincronia, obertura, transparència, tolerància a fallades, escalabilitat
   • Entendre la definició de sistema distribuït
2. Conèixer les arquitectures de sistema bàsiques en els sistemes distribuïts.
   Competències relacionades: CTI3.1, CTI3.4, CT6.4, CT5.6,
   Subcompetences:
   • Conèixer les arquitectures de sistema bàsiques en els sistemes distribuïts: centralitzades (client-servidor), descentralitzades (peer-to-peer), híbrides
3. Conèixer els mecanismes bàsics de comunicació en un sistema distribuït: invocació d'operacions remotes, comunicació basada en missatges, comunicació basada en events i comunicació basada en canals (streams), i escriure aplicacions distribuïdes que es comuniquin mitjançant l'enviament de missatges.
   Competències relacionades: CTI3.1, CTI3.4, CT6.4, CTI1.3, CT5.6,
   Subcompetences:
   • Conèixer els paradigmes de comunicació bàsics en els sistemes distribuïts: invocació remota de procediment, pas de missatges, cues de missatges, comunicació de grups, publicació/subscripció, espais de dades compartits, memòria compartida, codi mòbil, orientat a stream
   • Escriure aplicacions distribuïdes que es comuniquin mitjançant l'enviament de missatges
   • Conèixer el mecanisme de comunicació basada en streams: modes de transmissió, qualitat de servei
   • Conèixer el mecanisme de comunicació basada en events: sistemes de publicació/subscripció
   • Conèixer els diferents tipus de comunicació en un sistema distribuït: directa vs. indirecta (desacoblament espacial i temporal), persistent vs. transitòria, síncrona vs. asíncrona, discreta vs. contínua
   • Conèixer el mecanisme de comunicació basada en missatges: transitòria (Sockets) vs. persistent (MOM)
   • Conèixer el mecanisme de comunicació mitjançant la invocació de procediments remots (RPC): operació bàsica, pas de paràmetres, extensions del model bàsic, tractament de fallades, invocació de mètodes remots (RMI)
4. Entendre la problemàtica del temps i l'ordenació d'events en un sistema distribuït i explicar i implementar els mecanismes de rellotges lògics per atacar aquesta problemàtica i els algorismes per sincronitzar rellotges físics en un sistema distribuït.
   Competències relacionades: CTI3.1, CT6.4, CTI1.3, CT5.6,
   Subcompetences:
   • Entendre la problemàtica del temps i l'ordenació d'events en un sistema distribuït
   • Explicar i implementar els algorismes per sincronitzar rellotges físics en un sistema distribuït: Cristian (NTP), Berkeley
   • Explicar i implementar els mecanismes de rellotges lògics per atacar aquesta problemàtica: relació happened-before, rellotges lògics de Lamport (escalars, vectorials)
5. Descriure, comparar i implementar els algorismes per la coordinació de processos en un sistema distribuït, incloent la coordinació necessària per garantir exclusió mútua, elecció de líder, comunicació en grup multicast, i consens.
   Competències relacionades: CTI3.1, CT6.4, CTI1.3, CT5.6,
   Subcompetences:
   • Descriure, comparar i implementar els algorismes per la coordinació de processos en un sistema distribuït per garantir exclusió mútua: algorismes basats en permís (centralitzat, Lin, Maekawa, Ricart & Agrawala), algorismes basats en token (token ring)
   • Descriure, comparar i implementar els algorismes per la coordinació de processos en un sistema distribuït per la comunicació en grup multicast: multicast fiable bàsic, multicast fiable escalable, multicast ordenat (FIFO, causal, total), atomic multicast
   • Descriure, comparar i implementar els algorismes per la coordinació de processos en un sistema distribuït per l'elecció de líder: Bully, Ring
6. Comprendre l'aplicació de la replicació en un sistema distribuït, a més de la problemàtica que s'introdueix a nivell de consistència, i descriure els models de consistència corresponents i la seva implementació.
   Competències relacionades: CTI3.1, CT6.4, CTI1.3, CTI3.2, CT5.6,
   Subcompetences:
   • Descriure implementacions concretes de models de consistència: protocols basats en primari (remote-write, local-write) i protocols d'escriptura replicada (replicació activa, protocols basats en quòrum)
   • Comprendre l'aplicació de la replicació en un sistema distribuït, a més de la problemàtica que s'introdueix a nivell de consistència
   • Descriure els models de consistència relaxada centrats en les dades: ús de variables de sincronització
   • Descriure els models de consistència centrats en el client: eventual, monotonic-read, monotonic-write, read-your-writes, writes-follow-reads
   • Conèixer els detalls d'implementació dels models de consistència en relació a la ubicació de les rèpliques (permanents, iniciades pel servidor, iniciades pel client) i la propagació d'actualitzacions (push-pull protocols)
   • Descriure els models de consistència forta centrats en les dades: estricta, seqüencial, causal, FIFO
7. Conèixer i comparar les característiques bàsiques dels serveis de resolució de noms plans, estructurats i basats en atributs, i implementar i avaluar un d'aquests sistemes.
   Competències relacionades: CTI3.1, CT6.4, CTI1.3, CTI3.2,
   Subcompetences:
   • Implementar i avaluar un servei DNS simple
   • Conèixer i comparar les característiques bàsiques dels serveis de resolució de noms plans: broadcasting, forwarding pointers, solucions basades en home, DHTs
   • Conèixer i comparar les característiques bàsiques dels serveis de resolució de noms estructurats: name spaces, resolució iterativa, resolució recursiva, DNS
   • Conèixer i comparar les característiques bàsiques dels serveis de resolució de noms basats en atributs: serveis de directori (LDAP)
8. Conèixer i comparar les característiques bàsiques dels sistemes de fitxers distribuïts (e.g. NFS).
   Competències relacionades: CTI3.1, CT6.4, CTI1.3, CTI3.2,
   Subcompetences:
   • Comprendre la semàntica de compartició de fitxers: semàntica UNIX, semàntica de sessió, fitxers immutables, semàntica transaccional
   • Conèixer i comparar les característiques bàsiques del sistema de fitxers distribuït NFS
   • Conèixer i comparar les característiques bàsiques del sistema de fitxers distribuït Coda
   • Conèixer les arquitectures dels sistemes de fitxers distribuïts: model d'accés remot, model upload/download, idea bàsica de les arquitectures en clúster (stripping+replicació)
9. Conèixer i comparar les característiques bàsiques dels sistemes distribuïts basats en web: servidors web, servidors d'aplicacions, Web Services, Content Distribution Networks (CDN), i implementar i avaluar un d'aquests sistemes.
   Competències relacionades: CTI3.1, CTI3.4, CT6.4, CTI1.3, CT5.6,
   Subcompetences:
   • Implementar i avaluar un servidor web simple
   • Conèixer els mecanismes de sincronització en els sistemes distribuïts basats en Web
   • Conèixer els protocols de comunicació en els sistemes distribuïts basats en Web: HTTP, SOAP, WSDL
   • Conèixer els mecanismes de caching i replicació en els sistemes distribuïts basats en Web: Proxies, Content Distribution Networks (CDN): Akamai, esquemes de redirecció (URL rewriting, DNS redirection)
   • Conèixer les arquitectures dels sistemes distribuïts basats en Web: client/servidor, servlets, clústers de servidors, Web Services
   • Conèixer els serveis de noms en els sistemes distribuïts basats en Web: URL, DNS, UDDI
10. Comprendre el model de computació Peer-to-Peer (P2P), comparar les característiques dels sistemes P2P no-estructurats i dels estructurats basats en DHTs, i implementar i avaluar un d'aquests sistemes.
    Competències relacionades: CTI3.1, CT6.4, CTI1.3, CT5.6,
    Subcompetences:
    • Comprendre el model de computació Peer-to-Peer (P2P), les seves avantatges i les seves aplicacions
    • Comparar les característiques dels sistemes P2P no-estructurats centralitzats: BitTorrent
    • Comparar les característiques dels sistemes P2P estructurats basats en DHTs: Chord: organització de l'anell, inserció d'elements, cerca d'elements amb taules de finger, inserció de nodes
    • Implementar i avaluar un sistema P2P estructurat
    • Comparar les característiques dels sistemes P2P no-estructurats jeràrquics: FastTrack
    • Comparar les característiques dels sistemes P2P no-estructurats decentralitzats amb cerca per inundació: Gnutella
11. Conèixer els paradigmes més importants de computació distribuïda (computació voluntària, Grid i Cloud) i les seves característiques.
    Competències relacionades: CTI3.1, CT6.4, CTI1.3,
    Subcompetences:
    • Conèixer el paradigma Cloud de computació distribuïda, les seves característiques i les seves aplicacions: Utility computing, tipus de Clouds (públic, privat, comunitari, híbrid), diferència respecte al Grid, serveis Cloud (IaaS, PaaS, SaaS), tecnologies base d'implementació, infrastructura Cloud (datacenters), obstacles per la consolidació del Cloud
    • Conèixer el paradigma Grid de computació distribuïda, les seves característiques i les seves aplicacions: Virtual organizations (VO), arquitectura OGSA, diferència respecte a la computació clúster i distribuïda
    • Conèixer el paradigma de computació distribuïda voluntària: BOINC
12. Conèixer els paradigmes de Mobile i Ubiquitous Computing i la seva problemàtica.
    Competències relacionades: CTI3.1, CT6.4, CTI3.2,
    Subcompetences:
    • Conèixer els paradigmes de Mobile i Ubiquitous Computing i la seva problemàtica: volatilitat, associació, interoperabilitat, sensors i context-awareness, adaptació
13. Comprendre articles, enunciats, i en general qualsevol font d'informació de caràcter tècnic escrita en anglès
    Competències relacionades: G3.1,

Continguts

1. Conceptes de sistemes distribuïts
   Definició de sistema distribuït. Possibles aplicacions d'un sistema distribuït. Exemples de sistemes distribuïts. Desafiaments per dissenyar i implementar un sistema distribuït: heterogeneïtat, absència de visió global, seguretat, coordinació, asincronia, obertura, transparència, tolerància a fallades, escalabilitat. Arquitectures de sistema bàsiques en els sistemes distribuïts: centralitzades (client-servidor), descentralitzades (peer-to-peer), híbrides.
2. Comunicació entre processos
   Tipus de comunicació en un sistema distribuït: directa vs. indirecta (desacoblament espacial i temporal), persistent vs. transitòria, síncrona vs. asíncrona, discreta vs. contínua. Paradigmes de comunicació bàsics en els sistemes distribuïts: invocació remota de procediment, pas de missatges, cues de missatges, comunicació de grups, publicació/subscripció, espais de dades compartits, memòria compartida, codi mòbil, orientat a stream. Invocació de procediments remots (RPC): operació bàsica, pas de paràmetres, extensions del model bàsic, tractament de fallades, invocació de mètodes remots (RMI). Comunicació basada en missatges: transitòria (Sockets) vs. persistent (MOM). Comunicació basada en events: sistemes de publicació/subscripció. Comunicació basada en streams: modes de transmissió, qualitat de servei
3. Temps i ordenació
   Temps i ordenació d'events en un sistema distribuït. Rellotges lògics: relació happened-before, rellotges lògics de Lamport (escalars, vectorials). Algorismes per sincronitzar rellotges físics en un sistema distribuït: Cristian (NTP), Berkeley.
4. Coordinació i consens
   Coordinació de processos en un sistema distribuït per garantir exclusió mútua: algorismes basats en permís (centralitzat, Lin, Maekawa, Ricart & Agrawala), algorismes basats en token (token ring). Coordinació de processos en un sistema distribuït per l'elecció de líder: Bully, Ring. Coordinació de processos en un sistema distribuït per la comunicació en grup multicast: multicast fiable bàsic, multicast fiable escalable, multicast ordenat (FIFO, causal, total), atomic multicast.
5. Consistència i replicació
   Replicació i consistència en un sistema distribuït. Models de consistència forta centrats en les dades: estricta, seqüencial, causal, FIFO. Models de consistència relaxada centrats en les dades: ús de variables de sincronització. Models de consistència centrats en el client: eventual, monotonic-read, monotonic-write, read-your-writes, writes-follow-reads. Ubicació de les rèpliques (permanents, iniciades pel servidor, iniciades pel client) i propagació d'actualitzacions (push-pull protocols). Implementacions de models de consistència: protocols basats en primari (remote-write, local-write) i protocols d'escriptura replicada (replicació activa, protocols basats en quòrum)
6. Sistemes de noms
   Serveis de resolució de noms plans: broadcasting, forwarding pointers, solucions basades en home, DHTs. Serveis de resolució de noms estructurats: name spaces, resolució iterativa, resolució recursiva, DNS. Serveis de resolució de noms basats en atributs: serveis de directori (LDAP)
7. Sistemes de fitxers distribuïts
   Arquitectures dels sistemes de fitxers distribuïts: model d'accés remot, model upload/download, idea bàsica de les arquitectures en clúster (stripping+replicació). Semàntica de compartició de fitxers: semàntica UNIX, semàntica de sessió, fitxers immutables, semàntica transaccional. Característiques bàsiques del sistema de fitxers distribuït NFS. Característiques bàsiques del sistema de fitxers distribuït Coda
8. Sistemes distribuïts basats en Web
   Arquitectures dels sistemes distribuïts basats en Web: client/servidor, servlets, clústers de servidors, Web Services. Protocols de comunicació en els sistemes distribuïts basats en Web: HTTP, SOAP, WSDL. Serveis de noms en els sistemes distribuïts basats en Web: URL, DNS, UDDI. Sincronització en els sistemes distribuïts basats en Web. Caching i replicació en els sistemes distribuïts basats en Web: Proxies, Content Distribution Networks (CDN): Akamai, esquemes de redirecció (URL rewriting, DNS redirection)
9. Sistemes Peer-to-Peer (P2P)
   Model de computació Peer-to-Peer (P2P): avantatges i aplicacions. Sistemes P2P no-estructurats centralitzats: BitTorrent. Sistemes P2P no-estructurats decentralitzats amb cerca per inundació: Gnutella. Sistemes P2P no-estructurats jeràrquics: FastTrack. Sistemes P2P estructurats basats en DHTs: Chord: organització de l'anell, inserció d'elements, cerca d'elements amb taules de finger, inserció de nodes; Kademlia: organització de l'arbre i estat del node, cerca i inserció de nodes, cerca i inserció d'elements.
10. Sistemes de computació distribuïda
    Paradigma de computació distribuïda voluntària: BOINC. Paradigma Grid de computació distribuïda, les seves característiques i les seves aplicacions: Virtual organizations (VO), arquitectura OGSA, diferència respecte a la computació clúster i distribuïda. Paradigma Cloud de computació distribuïda, les seves característiques i les seves aplicacions: Utility computing, tipus de Clouds (públic, privat, comunitari, híbrid), diferència respecte al Grid, serveis Cloud (IaaS, PaaS, SaaS), tecnologies base d'implementació, infrastructura Cloud (datacenters), obstacles per la consolidació del Cloud
11. Sistemes mòbils i ubics
    Sistemes mòbils i ubics: volatilitat, associació, interoperabilitat, sensors i context-awareness, adaptació

Activitats

Activitat Acte avaluatiu

Metodologia docent

Mètode d'avaluació

Bibliografia

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/

Capacitats prèvies