"Sistemi Distribuiti Modulo 2"
Informazioni generali
Pagina ufficiale del corso.
Argomenti trattati
- LEZIONE 1. I sistemi distribuiti: il modello e le misure
di complessita'. L'esempio del
problema del "broadcast". [S] paragrafi 1.1, 1.2, 1.3, 1.4, 1.5.
- LEZIONE 2. Il limite inferiore al problema del "broadcast".
Il "broadcast" sull'ipercubo, sugli alberi, sui grafi completi. La
costruzione di uno "spanning tree" di un grafo: il protocollo "Shout".
[S] paragrafi 2.1, 2.5 introduzione e 2.5.1.
- LEZIONE 3. La costruzione di uno "spanning tree" di un grafo: il protocollo senza "NO", la
DFS (distribuita). Introduzione al problema dell'elezione del "leader".
Operazioni sugli alberi: la tecnica di saturazione.
[S] Sezioni 2.3.1, fine 2.5.1, 2.5.5, 2.5.6,2.6, 2.6.1.
- Lezione 4. Operazioni sugli alberi: la ricerca del minimo,
dell'eccentricita' di un nodo, del centro di un grafo. Il problema del
"ranking" di un grafo. [S] Sezioni 2.6.2,2.6.3, 2.6.4,2.6.5.
- LEZIONE 5. Il problema dell'elezione del "leader" sugli anelli:
l'algoritmo "All the way", "As far as it can" e "Controlled
distances". [S] Sezioni 3.1,3.2,3.1 introduzione, 3.3.1,3.3.2, 3.3.3, 3.3.7
(prima sottosezione).
- LEZIONE 6. Il problema dell'elezione del "leader" sugli anelli:
l'algoritmo "Electoral stages". Elezione sulla "mesh" e sull'ipercubo.
[S] Sezioni 3.3.4, 3.4 introduzione, 3.4.1, 3.5.
- LEZIONE 7. Il "routing": costruzione dell'albero dei
cammini minimi su grafi pesati e non.
Le tecniche di "compact routing":
Interval Routing [S] Sezioni 4.1, 4.2.1,
4.2.2, 4.2.3, 4.2.5, 4.4.1, 4.4.2.
- LEZIONE 8. Le tecniche di "compact routing":
Interval Routing, Boolean Routing, Prefix Routing.
Il senso della direzione.
[S] Sezioni 4.4.2,1.8.
- LEZIONE 9. La sicurezza e gli agenti mobili. Analisi
del problema della cattura di un "intruder" in "mesh", "tori" e
grafi cordali (accenno).
- LEZIONE 10. La sicurezza e gli agenti mobili. Analisi
del problema della cattura di un "intruder" in
grafi cordali e sul grafo Sierpinski.
I sistemi sincroni: tecniche di "waiting", "counting",
"guessing", "pipeline". [S] Sezioni 6.1, 6.2, 6.3.1, 6.3.2.
- LEZIONE 11. Introduzione generale ai sistemi "Peer to Peer". Esercizi
vari.
- LEZIONE 12. I sistemi "Peer to Peer": le tabelle hash distribuite e
il sistema Chord. Esercizi vari.
Materiale didattico
- Testo di riferimento: [S] N. Santoro. Design and Analysis of Distributed
Algorithms, Wiley 2007.
- I lucidi sono scaricabili dalla
pagina Web del docente
sotto Collegamenti - Materiale Didattico.
Ricevimento
Vedi
la
pagina
principale.
Esami