PARTE PRIMA: Sistemi Distribuiti
ed Elezione del Leader
-
11/1/05:
-
Elementi introduttivi. Modello di calcolo a trasmissione di messaggi:
topologia del grafo di trasmissione, grado di sincronia, di simmetria e
di uniformità. Definizione del modello computazionale: eventi computazionali.
-
12/1/05:
-
Elezione del leader in un sistema distribuito con topologia ad anello.
Non esistenza di una soluzione nel caso anonimo. Caso asincrono non anonimo:
algoritmo richiedente O(n^2) messaggi. Analisi del caso migliore e peggiore dell'algoritmo.
Elezione del leader in un anello asincrono non anonimo: algoritmo richiedente
O(n log n) messaggi. Analisi dettagliata del caso peggiore.
-
Approfondimento: Generazione di un'istanza pessima per l'algoritmo asincrono non anonimo richiedente O(n log n) messaggi.
Dispense: 1,
2,
3.
4.
5.
6.
7.
8.
9,
10,
11,
-
18/1/05:
-
Elezione del leader in un anello sincrono non anonimo e non uniforme con
partenza sincronizzata: algoritmo richiedente O(n) messaggi.
Elezione del leader in un anello sincrono non anonimo ed uniforme con
partenza non sincronizzata: algoritmo richiedente O(n) messaggi.
-
Approfondimento: Esecuzione attraverso un esempio dell'algoritmo
suddetto.
Dispense: 12,
13,
14,
15,
16,
17,
18,
-