Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 5.Problemi di consenso nei sistemi distribuiti


Sommario

  • Formulazione del problema del consenso (C)
  • Il problema dei generali bizantini (BG)
  • Il problema della consistenza interattiva (IC)
  • Relazioni tra C, BG, IC
  • Soluzioni ai problemi C e BG nei sistemi sincroni
  • Teorema dell’impossibilità nei sistemi asincroni

Il problema del consenso: formulazione

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:

  • N processi comunicanti tramite scambio messaggi;
  • i canali di comunicazione sono affidabili;
  • i processi sono soggetti a fallimenti di tipo crash oppure bizantini;
  • il processo pi (i=1 .. N) possiede una propria variabile di decisione di, e propone un proprio valore vi appartenente a un insieme D;
  • ciascun processo parte da uno stato di indecisione, e mira a raggiungere uno stato di decisione, in cui il valore di di è immutabile.

Il problema del consenso: esempio

Un esempio con tre processi:

  • i processi p1 e p3 propongono di procedere ad un’azione comune;
  • il  processo p3 propone di abortire l’azione comune, ma poi subisce un crash.

Nella figura a lato: un algoritmo di consenso distribuito fa sì che i due processi corretti decidano di procedere.


Il problema del consenso: requisiti

I requisiti che devono essere soddisfatti da un algoritmo di consenso distribuito in ogni sua esecuzione sono:

  • Terminazione (termination): prima o poi ogni processo corretto prende una decisione;
  • Accordo (agreement): due qualsiasi processi corretti non decidono diversamente;
  • Integrità (integrity): se tutti i processi corretti propongono lo stesso valore, la decisione finale di ogni processo corretto corrisponde a quel valore.

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.

Il problema dei generali bizantini: formulazione

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 dei generali bizantini: formulazione

Il problema differisce da quello del consenso in quanto:

  • non tutti i processi che devono raggiungere l’accordo propongono un valore, ma uno specifico processo (il generale) fornisce loro un valore sul quale devono convenire;
  • tipicamente si assume che i generali siano soggetti a fallimenti arbitrari (bizantini), sebbene il problema possa essere posto anche solo con riferimento a fallimenti per crash.

Il problema dei generali bizantini: requisiti

I requisiti del problema dei generali bizantini sono:

  • Terminazione (termination): prima o poi ogni processo corretto prende una decisione;
  • Accordo (agreement): due qualsiasi processi corretti non decidono diversamente;
  • Integrità (integrity): se il comandante è corretto, tutti i processi corretti decidono per il valore proposto dal comandante.

Nel problema dei generali bizantini l’integrità implica l’accordo se il comandante è corretto.

Il problema della consistenza interattiva

È 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:

  • Terminazione (termination): prima o poi ogni processo corretto prende una decisione;
  • Accordo (agreement): il vettore di decisione è lo stesso per tutti i processi corretti;
  • Integrità (integrity): se pi è corretto, tutti i processi corretti decidono per il valore vi proposto da pi come elemento i-esimo del vettore.

Relazioni tra i problemi C, BG, IC

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)

Relazioni tra i problemi C, BG, IC

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.

Consenso in un sistema sincrono

Un algoritmo di consenso basato su multicast.
Ipotesi:

  • sistema sincrono,
  • N processi,
  • al più f processi esibiscono fallimenti per crash,
  • disponibilità di una primitiva basic multicast (B-multicast), che garantisce che i processi destinatari corretti ricevano il messaggio, finché il mittente (multicaster) non fallisce:

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.

Consenso in un sistema sincrono

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):

  • invia (B-multicast) i valori che non ha inviato nei cicli precedenti;
  • riceve (B-deliver) i messaggi analoghi ed aggiorna Vik con i nuovi valori ricevuti.

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).

Consenso in un sistema sincrono

Nell’iterazione r, il processo pi (i=1..N):

  • invia (B-multicast) i valori che non ha inviato nei cicli precedenti;
  • riceve (B-deliver) i messaggi analoghi ed aggiorna Valuesir con i nuovi valori ricevuti.

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).

Consenso in un sistema sincrono

Algoritmo di Dolev et al.

Algoritmo di Dolev et al.


Consenso in un 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.

Consenso in un sistema sincrono

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.

Analisi del problema con tre generali

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.

I processi in rosso sono bizantini.

I processi in rosso sono bizantini.


Analisi del problema con tre generali

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.

I processi in rosso sono bizantini;Com è il Comandante, p2, p3, p4 i luogotenenti.

I processi in rosso sono bizantini;Com è il Comandante, p2, p3, p4 i luogotenenti.


Analisi del problema con quattro generali

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)=Ø

I processi in rosso sono bizantini; Com è il Comandante, p2, p3, p4 i luogotenenti.

I processi in rosso sono bizantini; Com è il Comandante, p2, p3, p4 i luogotenenti.


Consenso nei sistemi asincroni

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.

I materiali di supporto della lezione

G. Coulouris et al.: Distributed Systems: Concepts and Design (Cap. XII §5), IV ed., 2005.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion