Algoritmi Paralleli e Distribuiti
a.a. 2008/09
Lezione del 29/05/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Ricerca del leader in una rete ad anello
Problema: Dato un sistema distribuito, si vuole selezionare un processore
nella rete di interconnessione in modo che assuma il ruolo di unico leader
del sistema. L’esistenza di un leader semplificherà la coordinazione fra i
vari processi e quindi sarà utile per la gestione di vari altri problemi. La
rete di interconnessione che prendiamo in considerazione è la rete ad
anello con i processi caratterizzati da identificativi fra loro differenti.
Idea dell’algoritmo: Ogni processore manda il proprio identificativo lungo
l’anello. Quando il processore p riceve un identificativo, lo confronta con
il proprio. Se i valori sono uguali, p si autodichiara leader e l’intera
computazione termina. Se i valori sono diversi, p fa circolare lungo
l’anello l’identificativo ricevuto se maggiore del proprio, altrimenti non fa
nulla.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
2
Dettagli sulla rete ad anello
Si suppone che i nodi dell’anello siano identificati da valori diversi scelti
in un insieme di positivi qualunque, senza alcun vincolo di ordine.
L’anello si considera unidirezionale.
I singoli processi non conoscono la dimensione della rete; sono però in
grado di distinguere fra vicino sinistro e vicino destro.
Al solo processore eletto leader, ovvero al processo con l’identificativo
maggiore, sarà permesso di generare un output.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
3
Se il sistema è sincrono
Algorithm LES (Leader Election Sincrono)
begin
Pinit=i:
Pi:
stato = ignoto
send i al successore
repeat
receive inf
if inf > i then send inf al successore
if inf = i then
stato = leader
send un segnale di halt
if inf = halt and stato  leader then send halt
until inf = halt
end
O(n2) messaggi in n passi
Si noti che l’intero algoritmo termina quando il segnale di halt torna al leader.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
4
Esempio di funzionamento di LES
1
1
3
3
8
1
3
8
6
6
6
6
3
3
8
8
4
1
1
6
4
4
6
8
inizializzazione
Passo 1
1
1
8
4
8
LEADER
3
8
3
8
3
8
8
6
4
Passo 2
6
4
Passo 3
Algoritmi Paralleli e Distribuiti a.a. 2008/09
6
4
Passo 4
5
Correttezza e complessità
dell’algoritmo LES
Teorema: L’algoritmo LES risolve il problema dell’elezione del leader su
un sistema distribuito sincrono ad anello. Esso richiede complessità
temporale n e complessità dei messaggi O(n2).
Dimostrazione:
La correttezza si basa sui seguenti due fatti:
Fatto 1: Nessun processore, eccetto quello di indice massimo, raggiunge
lo stato di leader.
Fatto 2: Dopo n passi lo stato del processore di indice massimo è quello
di leader.
Dal Fatto 2 si deduce la complessità temporale che implica anche quella
dei messaggi.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
6
Elezione del leader in un sistema ad
anello asincrono
Algorithm LEA (Leader Election Asincrono)
begin
Pinit=i:
P i:
stato = ignoto
send i al successore
repeat
receive inf
if inf > i then send inf al successore
if inf = i then
stato = leader
send un segnale di halt
if inf = halt and stato  leader then send halt
until inf = halt
end
O(n2) messaggi in n passi
L’algoritmo è esattamente lo stesso presentato per il caso sincrono, con l’unica differenza che nella coda dei messaggi
ricevuti potranno essere presenti più valori contemporaneamente
Quindi LEA e LES per rete ad anello coincidono.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
7
Impossibilità del risultato nel caso
di processi anonimi
Negli algoritmi precedenti tutti i processi compiono le stesse identiche operazioni
eccetto il leader eletto che fa partire un segnale di halt. La differenziazione fra un
processo e l’altro è data dalla possibilità di accedere al proprio identificativo. Un
sistema si dice anonimo quando questa possibilità è interdetta.
Teorema: Sia D un sistema distribuito sincrono di tipo anello. Se tutti gli n (n > 1)
processi in D sono anonimi, allora in D non è possibile risolvere il problema
dell’elezione del leader.
Dimostrazione: la dimostrazione procede per assurdo. Ipotizziamo che il
problema del leader ammetta una soluzione su tale sistema: sia A l’algoritmo
risolutivo (A non può essere LES perché non è possibile fare confronti). Poiché
tutti i processori sono identici ed eseguono la stessa sequenza di programma, dato
il sincronismo, tutti i processi ricevono e mandano messaggi allo stesso istante.
Pertanto o tutti i processi arrivano a dichiararsi leader nello stesso istante
(contraddicendo l’unicità del risultato) o nessuno si dichiara leader. In entrambi i
casi non si raggiunge il risultato voluto. Si dice che la ragione di questo risultato
negativo giace nell’impossibilità di rompere la simmetria del sistema.
Un risultato analogo si ha nel caso di anello asincrono.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
8
Da asincrono a sincrono (e viceversa)
Ogni algoritmo che risolve un problema per il caso asincrono può essere
considerato un algoritmo per sistemi sincroni senza modificare né la
complessità temporale, né la complessità dei messaggi. Infatti un
algoritmo progettato per un sistema asincrono, gira su tutte le possibili
variazioni di tempo e quindi, in particolare, sulla variazione coincidente
con il modello sincrono.
Meno banale è trasformare un algoritmo progettato per il modello
sincrono in uno progettato per il modello asincrono. Infatti la
comunicazione fra i nodi sarà più elevata e quindi aumenta sia la
complessità temporale che quella dei messaggi. Normalmente la
simulazione si effettua implementando un apposito algoritmo asincrono
(sincronizzatore) che ha il compito di sincronizzare tra di loro i nodi della
rete attraverso scambi di messaggi.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
9
Il sincronizzatore
L’idea generale di un sincronizzatore è quella di generare una sequenza di
impulsi, numerati 0, 1, 2, … per ogni nodo della rete, in modo da simulare
il tempo costante di spedizione dei messaggi, tipico dei sistemi sincroni.
Durante il tempo del k-esimo impulso, un processore deve mandare i
messaggi che avrebbe mandato al k-esimo passo dell’algoritmo sincrono
che si sta simulando. Tutti gli impulsi debbono soddisfare la seguente
proprietà:
L’impulso (k+1)-esimo sarà generato per il nodo v, solo quando v avrà
ricevuto tutti i messaggi che i suoi vicini gli hanno inviato durante
l’impulso k.
Poiché il sistema è asincrono e non vi sono limiti al tempo di trasmissione
dei messaggi,è necessario introdurre un meccanismo per riconoscere se i
messaggi spediti da un nodo w sono stati ricevuti dal nodo v, ovvero è
necessario introdurre l’acknowledgement da parte del nodo v verso il
nodo w.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
10
Efficienza della simulazione
Quindi v può acquisire la consapevolezza di aver ricevuto tutti i messaggi solo con
l’aiuto di messaggi addizionali. Il problema diventa pertanto quello di non
compromettere l’efficienza dell’algoritmo A che si sta simulando, dato che sia la
complessità dei messaggi che la temporale risultano aumentate
Mtot = MA + M0s + TA Ms
Ttot = T0s + TA Ts
Dove:
Mtot = # totale di messaggi spediti nell’algoritmo simulato
MA = # messaggi spediti dall’algoritmo sincrono A che si sta simulando
M0s = # messaggi di inizializzazione del sincronizzatore
TA Ms = # messaggi extra spediti dal sincronizzatore durante i singoli passi di A
Ttot = tempo totale nell’algoritmo simulato
T0s = tempo di inizializzazione del sincronizatore
TA Ts = tempo dei singoli passi dell’algoritmo A simulato con l’ausilio del
sincronizzatore
Algoritmi Paralleli e Distribuiti a.a. 2008/09
11