Corso di Studi in Ingegneria Informatica

SCHEDA DELL'INSEGNAMENTO (SI)
SSD ING-INF/05

 

LAUREA MAGISTRALE IN INGEGNERIA INFORMATICA

ANNO ACCADEMICO: 2022-2023

 

DOCENTE: STEFANO RUSSO
TELEFONO: 0817683832
EMAIL: Questo indirizzo email è protetto dagli spambots. È necessario abilitare JavaScript per vederlo.

 

INSEGNAMENTO INTEGRATO (EVENTUALE):
MODULO (EVENTUALE):
CANALE (EVENTUALE):
ANNO DI CORSO (I, II, III): II
SEMESTRE (I, II): I
CFU: 6

 

...................................................................................................................................................

 

...................................................................................................................................................

 

Obiettivo dell’insegnamento è di fornire la conoscenza degli algoritmi avanzati che risolvono problemi classici nell’ingegnerizzazione dei sistemi software e dei sistemi embedded distribuiti (sincronizzazione dei clock, consenso; stato globale; comunicazioni di gruppo; mutua esclusione; elezioni; transazioni; tolleranza ai guasti; consistenza dei dati), nonché quelli adoperati nei sistemi peer-to-peer, nei sistemi IoT e nei sistemi basati sulla tecnologia blockchain.

 

Conoscenza e capacità di comprensione
Lo studente deve dimostrare: di comprendere i problemi teorici (non tecnologici) alla base dei sistemi distribuiti in applicazioni affidabili, critiche, tolleranti ai guasti e/o scalabili; di conoscere i limiti teorici in funzione delle assunzioni temporali e sui fallimenti; di conoscere gli algoritmi per la loro risoluzione.

Capacità di applicare conoscenza e comprensione
Lo studente deve dimostrare di saper astrarre le problematiche non tecnologiche della ingegnerizzazione di un sistema distribuito - sia esso di tipo software per applicazioni in rete, o di tipo embedded in applicazioni industriali - di saperle ricondurre a problemi teorici noti, e di saper individuare un adeguato approccio ingegneristico alla pratica risoluzione.

 

Caratterizzazione dei sistemi distribuiti. Definizioni. Modelli architetturali. Modello dei guasti. Requisiti di progetto: prestazioni, qualità del servizio, scalabilità, correttezza, sicurezza, tolleranza ai guasti. Classificazione: sistemi distribuiti sincroni, asincroni, parzialmente sincroni. (0,25 CFU)
Tempo e sincronizzazione nei sistemi distribuiti. Clock, skew, drift, tempo astronomico, Coordinated Universal Time (UTC). Sincronizzazione dei clock; algoritmo di Berkeley; algoritmo di Cristian. Network Time Protocol (NTP). Relazione happened-before. Orologi logici di Lamport. Orologi vettoriali. (0,5 CFU)
Stato globale di un sistema distribuito. Tagli consistenti e non consistenti. Algoritmo di snapshot di Chandy e Lamport. Raggiungibilità dello snapshot. Esempi di applicazione. (0,5 CFU)
Consenso nei sistemi distribuiti. Il problema del consenso, dei generali bizantini, della consistenza interattiva. Algoritmo di Dolev. Algoritmo Paxos. Failure detectors; classificazione. algoritmo Lazy FD. Consenso con failure detectors. (1,25 CFU)
Comunicazioni di gruppo. Multicast affidabili e/o ordinati. Algoritmi per la loro implementazione. (0,5 CFU)
Coordinazione distribuita. Mutua esclusione distribuita; algoritmi: del server centrale, ad anello, di Ricart e Agrawala, di Maekawa. Elezioni distribuite. Algoritmo: ad anello, del prepotente. Valutazione degli algoritmi. (0,5 CFU)
Azioni atomiche distribuite. Transazioni. Proprietà ACID. Problemi di consistenza dei dati, serializzabilità, effetto domino. Controllo di concorrenza: Two-phase lock. Two-version lock. Transazioni composte. Transazioni distribuite, two-phase commit, controllo di concorrenza nelle transazioni distribuite. Deadlock distribuito. L’astrazione memoria stabile. (1 CFU)
Replicazione e tolleranza dei guasti nei sistemi distribuiti. Dependability. La catena fault-error-failure. Replicazione attiva e passiva. Strategie di aggiudicazione. L’approccio state machine replication. (0,25 CFU)
Sistemi peer-to-peer. Motivazioni, requisiti, applicazioni, classificazione. Overlay networks, Overlay routing, Distributed Hash Table (DHT). Esempi: Napster, Gnutella, BitTorrent, Chord, Pastry. (0,25 CFU)
Consistenza dei dati nei sistemi distribuiti. Replicazione e consistenza. Consistenza stretta, linearizzabile, sequenziale, causale, eventuale, processor consistency, slow memory, modelli client centrici. Teorema CAP. (0,5 CFU)
Blockchain. Motivazioni, applicazioni. Algoritmi base. Smart contracts. Bitcoin, Blockchain e Internet of Things. (0,5 CFU)

 

Libri di testo:
• Coulouris, Dollimore, Kindberg, “Distributed Systems: Concepts and Design – 5th ed.”, Addison-Wesley, 2011;
• Kshemkalyani, Singhal, “Distributed Computing: Principles Algorithms and Systems”, Cambridge Univ. Press, 2008.
Trasparenze delle lezioni (disponibili sul sito web docente).
Pubblicazioni scientifiche:
• L. Lamport, “Time, Clocks and the Ordering of Events in a Distributed System”. Communications of the ACM, Vol. 21, N. 7, Luglio 1978.
• L. Lamport, “Paxos Made Simple”, 2001.
• F.B. Schneider, “Implementing Fault-Tolerant Services Using the State Machine Approach: A tutorial”. ACM Computing Survey, Vol. 22, N. 4, Dicembre 1990.
• A. Rowstron and P. Druschel, “Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems”. Proc. 18th IFIP/ACM Int. Conf. on Distributed Systems Platforms (Middleware 2001), Nov. 2001.
• M. Crosby, Nachiappan, P. Pattanayak, S. Verma, V. Kalyanaraman, “BlockChain Technology”, 2015, https://scet.berkeley.edu/wp-content/uploads/BlockchainPaper.pdf

 

La didattica è erogata: a) per l’80% con lezioni frontali; b) per il 10% con seminari sulle tematiche emergenti di blockchain e delle sue applicazioni all’Internet of Things; c) per il 10% con esercitazioni guidate in aula per approfondire praticamente aspetti relativi agli orologi logici e vettoriali e alla realizzazione degli algoritmi trattati.
Gli argomenti delle lezioni frontali e dei seminari sono esposti con l’ausilio di trasparenze dettagliate, messe a disposizione dello studente nel materiale didattico tramite il sito web ufficiale del docente.

 

a) Modalità di esame:

L'esame si articola in prova:
Scritta e orale
Solo scritta
Solo orale
Discussione di elaborato progettuale
Altro

 

In caso di prova scritta i quesiti sono (*):
A risposta multipla
A risposta libera
Esercizi numerici

  

L’esame si articola in una prova solo orale, consistente in tre domande su altrettanti problemi/algoritmi esposti al corso. A scelta dello studente, una delle tre domande può essere sostituita dall’esposizione del contenuto di una delle pubblicazioni scientifiche elencate nel materiale didattico.