Elezione del Leader

30/9/08: 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. Esempio: algoritmo distribuito asincrono per il calcolo dell’albero Depth First Search  richiedente O(n) messaggi.

2/10/08: Elezione del leader in un sistema distribuito con topologia ad anello. Non esistenza di una soluzione nel caso anonimo. Caso asincrono non anonimo in anelli unidirezionali: algoritmo di Chang&Roberts richiedente O(n2) messaggi. Analisi del caso migliore e peggiore dell'algoritmo. Elezione del leader in un anello asincrono non anonimo bidirezionale: algoritmo di Hirschberg&Sinclair richiedente O(n log n) messaggi.

7/10/08: 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.

9/10/08: Approfondimento: Esecuzione attraverso un esempio dell'algoritmo per l’elezione del leader in un anello sincrono non anonimo ed uniforme con partenza non sincronizzata.

Dispense: Elementi introduttivi, Elezione del leader.

 

13/1/09 (Seminario Prof. Zaks): Impossibilita' di risoluzione del problema dell'elezione del leader in un anello asincrono uniforme con un numero medio di messaggi o(n log n). Estensione del risultato ad anelli sincroni non uniformi per algoritmi basati su confronti.