PARTE PRIMA: Sistemi Distribuiti ed Elezione del Leader

8/1/03:

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.

 

9/1/03:

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.

Approfondimento: Analisi del caso migliore e del caso peggiore dell'algoritmo suddetto.

 

14/1/03:

Elezione del leader in un anello asincrono non anonimo: algoritmo richiedente O(n log n) messaggi. Analisi dettagliata del caso peggiore.

Approfondimento: Impossibilità di generare 4*2^k messaggi per ogni processore durante la fase k dell'algoritmo.

 

15/1/03:

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.