Informalmente, il problema del consenso distribuito consiste nel far sì che alcuni processi convengano su un valore, dopo che almeno uno di essi ha effettuato una proposta riguardo tale valore.
Meno informalmente:
Un esempio con tre processi:
Nella figura a lato: un algoritmo di consenso distribuito fa sì che i due processi corretti decidano di procedere.
I requisiti che devono essere soddisfatti da un algoritmo di consenso distribuito in ogni sua esecuzione sono:
Si possono avere varianti al requisito di integrità: per es., un requisito di integrità più debole richiede che il valore di decisione sia proposto da qualche processo corretto, ma non necessariamente da tutti i processi corretti.
Nella formulazione informale di Lamport et al. (1982), tre o più generali devono convenire se sferrare un attacco o ritirarsi. Uno di essi è il comandante; gli altri sono i suoi luogotenenti.
Il comandante invia l’ordine di attaccare o ritirarsi; i luogotenenti devono convenire se attaccare o ritirarsi.
Uno o più generali possono essere maliziosi.
Se il comandante è malizioso, invia ordini diversi ai luogotenenti.
Se un luogotenente è malizioso, dice ad alcuni suoi pari che il comandante ha ordinato di attaccare, ad altri che ha ordinato di ritirarsi.
Il problema differisce da quello del consenso in quanto:
I requisiti del problema dei generali bizantini sono:
Nel problema dei generali bizantini l’integrità implica l’accordo se il comandante è corretto.
È una variante del problema del consenso.
Ogni processo propone un solo valore, e l’obiettivo è che tutti i processi concordino su un vettore di valori, uno per ciascuno di essi.
I requisiti del problema della interactive consistency sono:
Ci(vi,v2,…,vn) – Decisione di pi in un esecuzione di un problema di Consenso.
BGi(j,v) – Decisione di pi in un esecuzione di un problema dei Gen. Bizantini, ove pj è il comandante
IC(v1,v2,….,vn)[j] – j-esimo valore del vettore di decisione di pi in una esecuzione del problema della Interactive Consistency
BG → IC
n esecuzioni di BG. ∀ i ∈ {1,…,n} pi è il generale. Si ha: ICi(v1,v2,…,vn)[j] = BG(j,vj) (i , j = 1,2,….n)
IC → C
Applicando una funzione di valutazione sul vettore di soluzioni prodotto da IC si ha: Ci(v1,v2,…,vn) = majority (ICi(v1,v2,…,vn)[j] ) (j = 1,2,….n)
C → BG
1) Il comandante pj manda v a sé stesso e agli altri n-1 processi.
2) Tutti i processi eseguono C con i valori v1,…,vn ricevuti
3) BGi(j,v) = Ci(v1,v2,…,vn) (i = 1,2,….n)
Le proprietà di Agreement, Integrity e Termination continuano a valere dopo di tali trasformazioni.
Un algoritmo di consenso basato su multicast.
Ipotesi:
multicast(g, m) invia il messaggio m a un gruppo g di processi;
m porta con sé un identificativo del mittente, e
un identificativo del gruppo g;
deliver(m) consegna al chiamante il messaggio m;
i processi non mentono su origine e destinazione dei messaggi.
Vik: vettore dei valori proposti noti al processo pi all’inizio del ciclo k;
f numero di guasti per crash tollerati dall’algoritmo
f+1 numero complessivo di iterazioni
Nel caso peggiore, nelle f+1 iterazioni si verifica il numero massimo di crash possibili f; l’algoritmo garantisce che al termine i processi corretti sopravvissuti raggiungano il consenso.
Nell’iterazione k, il processo pi (i=1..N):
Dopo f+1 cicli, ogni processo sceglie il valore minimo di Vik+1 come valore di decisione.
La durata di un ciclo è limitata da un apposito timeout (sistema sincrono).
Nell’iterazione r, il processo pi (i=1..N):
Dopo f+1 cicli, ogni processo sceglie il valore minimo di Valuesif+1 come valore di decisione.
La durata di un ciclo è limitata da un apposito timeout (sistema sincrono).
Terminazione. Ovvia (il sistema è sincrono).
Accordo e integrità: Sono raggiunti se si dimostra che tutti i processi sopravvissuti pervengono allo stesso vettore al termine dell’algoritmo, in quanto poi tutti applicano la stessa funzione (calcolo del minimo).
Dim.: assumiamo che due processi non abbiano lo stesso vettore finale, p. es. che pi abbia un valore v che pj non possiede (i ≠ j).
L’unica spiegazione possibile è che v sia stato inviato da un altro processo pk a pi, e poi pk sia andato in crash prima di inviarlo a pj.
Ma se pkpossedeva il valore v senza che pj lo possedesse anch’esso già a conclusione del ciclo precedente, vuol dire che ci deve essere stato nel ciclo precedente un altro processo ancora che ha inviato v a pk ed è andato in crash prima di inviarlo a pj.
Iterando il ragionamento, ci deve essere stato almeno un crash per ciclo.
Ma ci sono al più f guasti, e f+1 cicli, e l’ipotesi d’assurdo è contraddetta.
Il risultato è generalizzabile:
Ogni algoritmo di consenso distribuito che voglia tollerare f fallimenti richiede almeno f+1 cicli (Dolev e Strong, 1983).
Ne segue che tale limite inferiore si applica anche agli altri problemi di agreement distribuito, come quello dei generali bizantini.
Si assume che il sistema sia sincrono, e che i canali siano privati (se i processi potessero ispezionare i messaggi degli altri processi, potrebbero riconoscere il processo bizantino).
Notazione: i:j:v = i dice che j dice v.
Se esistesse una soluzione, per il requisito di integrità p2 dovrebbe scegliere il valore v fornito dal comandante se questo è corretto.
Ma nei due casi, p2 è nella stessa situazione.
Analogamente, per simmetria si ha che se p3 è corretto, deve scegliere il valore del comandante.
Ma ciò viola la condizione di agreement, perché se il comandante è faulty invia valori diversi ai due luogotenenti.
In generale, non esiste soluzione se N ≤ 3f.
Esiste soluzione se N ≥ 3f + 1.
Analisi con N = 4, f = 1 → 2 passi:
In Figura:
p2: maggioranza(v,u,v)=v
p4: maggioranza(v,v,w)=v
p1, p2, p3: maggioranza(u,v,w)=Ø
Fischer et alii hanno dimostrato (1985) che nessun algoritmo può garantire il raggiungimento del consenso in un sistema asincrono, anche nel caso di un unico fallimento per crash di un processo.
Di conseguenza, non esistono soluzioni garantite in un sistema asincrono per il problema dei generali bizantini e per quello della consistenza interattiva.
NB: ciò non significa che non si possa raggiungere il consenso in un sistema distribuito, ma che non c’è algoritmo che possa garantire il raggiungimento.
1. Caratterizzazione dei sistemi distribuiti
2. Modelli di sistemi distribuiti
3. Tempo e sincronizzazione nei Sistemi Distribuiti
4. Stato globale nei Sistemi Distribuiti
5. Problemi di consenso nei sistemi distribuiti
7. Algoritmi di mutua esclusione nei sistemi distribuiti
8. Algoritmi di elezione nei sistemi distribuiti
10. Il Network File System di SUN Microsystems
11. AFS (Andrew File System) e GFS (Google File System)
12. Transazioni e controllo di concorrenza
13. Transazioni
15. Affidabilità (dependability) dei sistemi software distribuiti
16. Affidabilità dei sistemi software distribuiti
17. Software Faults
18. Classificazione e analisi dei difetti software
G. Coulouris et al.: Distributed Systems: Concepts and Design (Cap. XII §5), IV ed., 2005.