PARTE PRIMA: Sistemi Distribuiti ed Elezione del Leader

13/1/04:

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.

 

14/1/04:

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, peggiore e medio dell'algoritmo suddetto.

Dispense: 1, 2, 3. 4. 5. 6. 7. 8.
 

15/1/04:

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

Elezione del leader in un anello sincrono non anonimo e non uniforme con partenza sincronizzata: algoritmo richiedente O(n) messaggi.

Approfondimento: Generazione di un'istanza pessima per l'algoritmo asincrono non anonimo richiedente O(n log n) messaggi.

Dispense: 9, 10, 11, 12, 13,
 

20/1/04:

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: 14, 15, 16, 17, 18,