Sistemi distribuiti - Distributed Systems

Programma dell'insegnamento - Corso di laurea in Informatica Magistrale internazionale

 

Docente

Prof. Marino Miculan

Indirizzo e-mail

marino.miculan@uniud.it

Indirizzo Pagina Web Personale

http://www.dimi.uniud.it/miculan/

La pagina del corso è http://sole.dimi.uniud.it/~marino.miculan/wordpress/teaching/sistemi-distribuiti

Crediti

9 CFU

Finalità e obbiettivi formativi

Scopo del corso è fornire allo studente i fondamenti e gli strumenti per la progettazione e implementazione dei sistemi distribuiti. A questo scopo, il corso è diviso in tre parti. Nella prima parte, si studiano gli aspetti sistemistico-architetturali dei sistemi distribuiti, analizzando vari modelli (client-server, multi-tier, peer-to-peer…). Nella seconda parte si studiano i modelli di comunicazione adottabili su questi sistemi distribuiti, e i corrispondenti middleware. In questa parte vengono anche introdotti alcuni linguaggi specifici per la programmazione dei sistemi distribuiti, come Erlang e Jolie. Infine nella terza parte si affrontano le principali problematiche che si presentano comunemente nella programmazione distribuita, come il rilevamento dei fallimenti, del deadlock, il raggiungimento del consenso; per ognuna di queste, si studieranno adeguate soluzioni algoritmiche e tecniche.

Programma

  1. Introduzione ai sistemi distribuiti. Problematiche, motivazioni, esempi.
  2. Modelli di sistemi. Modelli fisici, architetturali, fondamentali. Architetture stratificate, client-server, peer-to-peer. Middleware
  3. Meccanismi per comunicazione diretta: socket, RPC, RMI.
  4. Meccanismi per comunicazione indiretta: comunicazione di gruppo, publish-subscribe, code di messaggi. AMQP.
  5. Linguaggi per la programmazione ad attori: Erlang
  6. Web Services. SOAP. Linguaggi per la programmazione service-oriented: Jolie.
  7. Sistemi di oggetti distribuiti. Oggetti persistenti e transitori. Componenti distribuiti. JavaBeans.
  8. Sistemi peer-to-peer. Replicazione negli overlay non strutturati con random walk: analisi del caso uniforme, proporzionale e    square-root. Overlay di instradamento. Tabelle hash distribuite. Lookup semplice e scalabile. Pastry, Tapestry, Kademlia. Peer e ultrapeer: Gnutella, Skype.
  9. File system distribuiti. Architetture. NFS.
  10. Naming. Semplice, strutturato, con attributi. X.500 e LDAP.
  11. Tempo e stato globale. Orologi fisici, algoritmi di sincronizzazione, NTP. Orologi logici. Stato globale, multicast totalmente ordinato. Comunicazione causale.
  12. Coordinamento. Mutua esclusione distribuita. Algoritmi di elezione. Coordinamento in comunicazioni di gruppo. Problema del consenso. Problema dei Generali Bizantini.
  13. Transazioni distribuite. Lock distribuiti. Sincronia virtuale. Ordinamento dei messaggi. Distributed Commit (2PC, 3PC). Deadlock distribuito: definizione, rilevamento, prevenzione.
  14. Replicazione. Modelli di consistenza dei dati. Servizi fault tolerant. Consistenza causale, per eventi. Gestione delle replica: replicazione passiva vs. attiva. Sistemi ad alta disponibilità. Architettura gossip. Transazioni con dati replicati. Algoritmo di Gifford.

 

Attività di Laboratorio

Opzionale

Prerequisiti

Sistemi operativi; Reti di calcolatori

Bibliografia

  1. G. Coulouris, J. Dollimore, T. Kindberg, G. Blair, “Distributed systems: concepts and design”, 5 ed., International edition, Pearson, 2012.
  2. In alternativa al precedente: A. Tanenbaum, M. Van Steen, “Sistemi distribuiti. Principi e paradigmi”, Pearson, 2007.
  3. J. Armstrong, “Programming Erlang: Software for a Concurrent World”, The Pragmatic Programmers, 2007. ISBN: 978-1-93435-600-5
  4. Appunti dalle lezioni

 

Modalità d'esame

Progetto, da svolgere in gruppi di al massimo 2 persone, su un argomento del corso, più esame orale.

Orario di ricevimento

Su appuntamento

**************************************************************************************************

Aims

The aim of the course is to provide students with the foundations and tools for the design and implementation of distributed systems, both client-server and peer-to-peer. To this end, in the course we will discuss the main issues of distributed systems, such as the detection of failures, deadlocks, the achievement of consensus. For each of these, we will study the appropriate solutions and algorithmic techniques. We will also describe the main network communication primitives (such as sockets, RPC, message exchange), and languages specifically developed for the implementation of distributed systems (such as Erlang, Scala and Globe).

Program

         •          Introduction to distributed systems. Issues, motivations, examples.

         •          System models. Physical models, architectures, fundamental. Layered architectures, client-server, peer-to-peer networks. Middleware.

         •          Mechanisms for direct communication: sockets, RPC, RMI.

         •          Mechanisms for indirect communication: group communication, publish-subscribe, message queues. AMQP.

         •          Languages for actor-oriented programming: Erlang

         •          Web Services. SOAP. Languages for service-oriented programming: Jolie.

         •          Systems of distributed objects. Persistent objects and transient. Distributed components. JavaBeans.

         •          Peer-to-peer networks. Replication in unstructured overlays with random walk: analysis of the uniform, proportional and square-root cases. Overlay routing. Distributed hash tables. Lookup simple and scalable. Pastry, Tapestry, Kademlia. Peer and ultrapeer: Gnutella, Skype.

         •          Distributed file systems. Architectures. NFS.

         •          Naming. Simple, structured, with attributes. X.500 and LDAP.

         •          Time and global state. Physical clocks, synchronization algorithms, NTP. Logical clocks. Global state, totally ordered multicast. Causal communication.

         •          Coordination. Distributed mutual exclusion. Election algorithms. Coordination group communications. Consensus problem. Byzantine Generals Problem.

         •          Distributed transactions. Distributed lock. Virtual synchrony. Ordered messages. Distributed Commit (2PC, 3PC). Distributed deadlock: definition, detection, prevention.

         •          Replication. Models of data consistency. Fault-tolerant services. Consistency: causal, event-based. Replication management: passive vs. active. High-availability systems. Gossip architecture. Transactions with replicated data. Gifford’s Algorithm.

Bibliography

      1.         G. Coulouris, J. Dollimore, T. Kindberg, G. Blair, “Distributed systems: concepts and design”, 5 ed., International edition, Pearson, 2012.

      2.         Alternatively: A. Tanenbaum, M. Van Steen, “Sistemi distribuiti. Principi e paradigmi”, Pearson, 2007.

      3.         J. Armstrong, “Programming Erlang: Software for a Concurrent World”, The Pragmatic Programmers, 2007. ISBN: 978-1-93435-600-5

      4.         Notes from lectures

Exam modality

Practical project (implementation), with written essay, followed by an oral exam.