Architetture distribuite per il Cloud (Sistemi Distribuiti)

Prova del teorema:

Dimostriamo il teorema per il modello sincrono, che è un caso particolare del modello asincrono. Tutti i nodi hanno la stessa funzione di transizione. Se i nodi non sono distinguibili, le transizioni dipendono solo dai messaggi ricevuti (che faranno cambiare lo stato). Poiché tutti i nodi partono dallo stato iniziale, tutti seguiranno la stessa transizione e tutti invieranno gli stessi messaggi durante il primo round (cambieranno tutti lo stato). Poiché le transizioni dipendono solo dai messaggi ricevuti, tutti eseguiranno la stessa transizione e invieranno gli stessi messaggi al round due (al round successivo tutti riceveranno gli stessi messaggi, tutti i nodi faranno la stessa transizione di stato, ma se questo è vero, tutti i nodi entrerebbero nello stato eletto).

Se esistesse un algoritmo per l'elezione di un leader, tutti i nodi raggiungerebbero lo stato di eletto. Questo problema è chiamato "problema di eccesso di

rompere la simmetria. In generale, più nodi ci sono nel grafo, più iterazioni saranno necessarie per ottenere un leader unico. Per implementare questo algoritmo probabilistico, è possibile utilizzare tag html per evidenziare i passaggi chiave: 1. Generazione casuale di identificatori:

Generare un numero casuale tra 1 ed N per ogni nodo.

2. Verifica delle condizioni di elezione:

Controllare se l'identificatore generato è il più piccolo o il più grande tra tutti i nodi.

3. Proclamazione:

Proclamare il nodo con l'identificatore più piccolo o più grande come leader.

Ricorda che questo è solo un esempio di come formattare il testo utilizzando tag html. Puoi personalizzare ulteriormente il design e lo stile utilizzando CSS.

Eleggere il leader, questi algoritmi sono buoni, riesco a raggiungere velocemente una soluzione. Supponiamo che eleggiamo la id con peso minimo, e assumiamo che min = 1, ci mettiamo nelle condizioni in cui generiamo, se c'è un unico nodo che genera 1 io lo eleggo, altrimenti rigenero. La probabilità che un nodo generi 1 assumendo che i numeri siano generati in maniera uniforme è 1/n: prob(id=1)=1/n. La probabilità che non generi 1 è 1-(1/n). La probabilità che sia 1 e sia unico è circa (quindi che una fase termini) 0.37%. Il numero medio di fasi è quindi minore di 3. Complessità di messaggio: è il numero di fasi (minore di 3) * complessità di una fase (algoritmo di elezione su rete identificata).

3.1. Algoritmo asincrono uniforme

3.1.1. Algoritmo base

Nel momento in cui abbiamo una rete identificata, in particolare vedremo l'anello, dobbiamo capire come si elegge un leader, bisogna cercare una configurazione

finale della rete in cui un nodo ha una caratteristica diversa dagli altri, dal nostro punto di vista è una ricerca di minimo o di massimo. In un anello banalmente ognuno mette in giro il proprio ID, tutti i processori hanno una concezione di destra e sinistra, si inviano le ID verso sinistra, e ricevo la ID' del vicino da destra, se è ID' > ID (ID del vicino) più grande allora non inoltro il messaggio perché noi cerchiamo il minimo, altrimenti va avanti e passa nello stato non eletto, altrimenti se ID' = ID vuol dire che il nodo è eletto leader, siccome solo l'ID minimo andrà avanti fino a tornare al nodo eletto, quindi riceve la propria ID e si ferma. Nel caso peggiore se le ID sono ordinate in ordine decrescente rispetto al verso di percorrenza, devo fare 2 l'anello due volte. Complessità O(n) ma non ci piace.

3.1.2. Algoritmo ottimale Algoritmo ottimale, la probabilità che sia 1 e sia unico è,

l'idea è che ogni nodo non manda la ID solo a destra, ma anche a sinistra, al round 0 manda questi messaggi a distanza 1, il processore a destra e sinistra fanno il confronto come prima ed eventualmente rispondono al nodo che ha mandato la ID. Se la ID è maggiore della propria allora mandano quella ID avanti a distanza 1. I messaggi che partono dal nodo con la propria ID sono messaggi di PROBE, i messaggi che tornano dall'ultimo arco che sto visitando si chiamano reply, poiché questa distanza raddoppia a ogni fase, perché prima visito nodi a distanza 1, poi a distanza 2, distanza 4 e così via, e ci sarà un contatore di PROB che ci indica che il numero di processori attraversati è il numero giusto. Il processore passa al round successivo se riceve indietro entrambi i PROBE (cioè i reply). Cerco il massimo il nodo manda la ID a destra e sinistra, i nodi confrontano la ID con la propria, se è più grande restituisce un reply.

se riceve due reply sa che è il più grande dei 3, e passa al round 1 e passa la stessa ID a distanza 2, il nodo finale eventualmente produce un reply, se tornano entrambi i reply al nodo che ha prodotto i due PROB allora il nodo passa alla fase successiva. L'algoritmo si ferma la prima volta che 2 > n, perché vuol dire che il messaggio torna al nodo che l'ha mandata, è un anello quindi quando il nodo riceve la propria ID allora finisce. Correttezza: La ID massima non viene mai fermata Complessità: Un PROBE in fase i produce al più 2 messaggi, per un processore che passa alla fase successiva, esiste un reply cioè altri 2 messaggi, quindi per ogni lato ho 2 messaggi con i probe e altri 2 messaggi con il reply, un processore alla fase i tra probe e REPLY al più produrrà 4*2 messaggi; Quindi, per essere arrivato alla fase i il processore ha vinto la fase i-1, ma quanti sono questi processori alla fase i? Se un processore ha vinto la fase i-1, allora ha ricevuto 2 reply, quindi ci sono almeno 2 processori alla fase i-1.PROBE raggiunge un nodo e quel nodo confronta la ID nel probe con la propria ID, vince uno dei due, quindi se voglio avere 2 nodi alla fase i vuol dire che questi due nodi non si sono scambiati un PROBE alla fase i-1. Quindi devono stare ad una distanza minima che sarebbe 2 +1, perché nella fase i-1 i processori i-1 mandano il PROBE a distanza 2. Questo significa che il massimo dei nodi che possono arrivare alla fase i sono n/[2 +1] dove n è il numero totale dei processori. Il numero totale di messaggi: fase 0 tutti i nodi partono al più, e ricevono un REPLY, esagerando abbiamo 4n messaggi (2 andata e 2 ritorno), dalla fase 1 fino all'ultima fase, che è log n visto che raddoppio tutte le i volte, il massimo numero di messaggi a ogni fase è 2 PROBE e 2 REPLY, quindi 4*2 messaggi (per ogni i-1 nodo arrivati alla fase i, quindi * n/[2 +1] + n per la fase di proclamazione, eletto il leader manda messaggi a tutti gli altri nodi per avvertirli che è il leader).

leader.Complessità finale è 5n+8n log n quindi Ω(n log n) e non possiamo fare meglio.

3.1.3. Lower Bound

Consideriamo un algoritmo di elezione A per un anello con le seguenti caratteristiche:

1. Asincrono
2. Uniforme
3. Elegge il nodo con ID massimo
4. Garantisce che tutti conoscano la ID del leader

La complessità di messaggio di A è limitata inferiormente da Ω(n log n).

dTeorema: Per ogni insieme S con n = 2 identificatori (distinti) ed ogni anello che usa gli elementi di S come ID, l’algoritmo A ammette uno schedule aperto (un arco non viene utilizzato) in cui vengono spediti almeno M(n) messaggi con:

Il comportamento asintotico sarà n log n, cioè qualunque algoritmo della classe necessità di n log n messaggi.

Per dimostrarlo prendo un algoritmo generico che ammette uno schedule aperto, cerco di capire quanti messaggi vengono scambiati, si può mostrare per induzione:

Supponiamo che x > y. Ad un certo punto p deve 0mandare

un messaggio a p in modo da comunicargli il proprio valore. Se fermiamo la esecuzione dopo aver inviato il primo messaggio lo schedule è quello desiderato. Gli n messaggi finali che il leader deve produrre, ci deve essere, con due processori poi alla fine uno deve avvertire l'altro. Ogni esecuzione quindi ha almeno un messaggio, comincio l'esecuzione e mi fermo subito dopo la spedizione del primo messaggio.

Abbiamo una serie di eventi (schedule), se c'è un arco aperto, quindi dove non vengono scambiati messaggi, e quindi M(2) = 1.

Procediamo per potenze di 2 quindi n cresce raddoppiando, ci riduciamo al caso precedente, supponiamo di avere un anello con n nodi identificato, dividiamo l'anello in due metà, quindi n/2 ed n/2, dove S e S1 sono gli identificatori dei due sotto-anelli, l'abbiamo provato fino ad fino ad n/2 cioè è vera l'ipotesi induttiva, allora per ipotesi induttiva esistono due anelli R e R che sono la

metà dell'anello iniziale (che usano S ed S), io posso dire che in R ed R esiste uno schedule in cui vengono mandati M(n/2) messaggi, quindi abbiamo due schedule α e α, questi schedule sono aperti cioè abbiamo almeno un arco dove non passa alcun messaggio. Questi archi siano e per α ed e per α. Rimuoviamo e ed e ed uniamo i due sotto-anelli, facendolo diventare un anello di dimensione n. Congiungendo p con p e q con q. Siccome l'algoritmo è uniforme l'esecuzione non dipende da n, significa che se io prendo α, essendo un insieme di eventi in R, se lo eseguo nell'anello completo, produrrà lo stesso effetto che ha prodotto nell'anello iniziale, perché l'arco e non viene mai attraversato, ciò implica che su e ed e non passerà alcun messaggio, quindi ho lo stesso stato anche nell'anello R (unione di R ed R) idem per R.

un’esecuzione ammissibile dello stesso algoritmo in R prevede come schedule α ed α , le due1 2esecuzioni sono indipendenti l’una dall’altra, essendo algoritmo uniforme lo stato è medesimo di quelloraggiunto nelle esecuzioni separate.

Quindi in α α vengono inviati 2M(n/2) messaggi, esiste una esecuzione dell’algoritmo dove vengono1 2inviati altri ½(n/2 – 1) messaggi senza utilizzare gli archi aperti, ma non possiamo assumerlo sempre.

Quindi in caso contrario, in cui gli unici messaggi in transito sono su archi aperti, sia α questa3configurazione. L’algoritmo è fermo, perché posso mandare solo messaggi sugli archi aperti.

Continuo fino a fine schedule, ovvero con α α α α ’’ uno schedule ammissibile che raggiunge la1 2 3 4terminazione, (almeno n/2 messaggi sono stati inviati in