PARTE PRIMA: Sistemi Distribuiti ed Elezione del Leader

11/1/06:

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.

Approfondimento: Algoritmo distribuito per la determinazione del Depth-First Search (DFS) Tree di un grafo. Analisi di correttezza e complessita' dei messaggi.

 

12/1/06:

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,

 

17/1/06:

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.
Dispense: 12, 13, 14, 15, 16, 17, 18,

 

18/1/06:

Approfondimento: Codice per l'algoritmo di elezione del leader in un anello sincrono e uniforme. Esecuzione attraverso un esempio dell'algoritmo.