Problema dei generali bizantini

Se tutti i generali attaccano in modo coordinato, la battaglia è vinta (a sinistra). Se due generali dichiarano falsamente di avere l'intenzione di attaccare, ma invece si ritirano, la battaglia è persa (a destra).

Il problema dei generali bizantini è un problema informatico su come raggiungere consenso in un sistema (in particolare un sistema informatico distribuito) nel quale i diversi componenti percepiscono informazioni contrastanti, senza poter riconoscere a priori i componenti responsabili di tale malfunzionamento. Il problema consiste pertanto nel trovare un accordo, comunicando solo tramite messaggi, tra componenti diversi alla luce della presenza di informazioni discordanti.

Il termine prende il nome da un'allegoria, formulata da Leslie Lamport, per descrivere una situazione in cui, per evitare il fallimento catastrofico di un sistema (organizzare un attacco), gli attori coinvolti (ossia i bizantini) devono concordare una strategia comune in modo autonomo (se attaccare o ritirarsi), ma alcuni di essi risultano inaffidabili in un modo che porta gli altri attori (quelli "leali") a non trovare un immediato accordo sulla strategia.

La tolleranza ai guasti bizantini (BFT, dall'inglese Byzantine Fault Tolerance) è la capacità di resilienza di un sistema informatico, o di un sistema simile, rispetto a tali condizioni di guasto. Un guasto bizantino è un qualsiasi guasto che presenta sintomi diversi a osservatori diversi. Un fallimento bizantino è la perdita di un servizio del sistema a causa di un guasto bizantino in sistemi che richiedono il consenso tra più componenti.

Storia

Il problema di ottenere il consenso bizantino fu concepito e formalizzato da Robert Shostak, che lo battezzò "problema della coerenza interattiva". Questo lavoro fu svolto nel 1978 nel contesto del progetto SIFT, sponsorizzato dalla NASA, presso il Computer Science Lab dello SRI International. Il SIFT (acronimo di Software Implemented Fault Tolerance, tolleranza ai guasti implementata via software) fu frutto dell'ingegno di John Wensley e si basava sull'idea di utilizzare più computer generici in comunicazione tra loro tramite messaggistica a coppie, al fine di raggiungere un consenso anche nel caso in cui alcuni dei computer risultassero difettosi.

Inizialmente non era chiaro quanti computer fossero necessari in totale per garantire che una cospirazione di $n$ computer difettosi risultasse risolvibile. Shostak dimostrò che era necessario un minimo di $3n+1$ computer, e ideò un protocollo di messaggistica a due round per $3n+1$ che avrebbe funzionato per il caso $n=1$. Il suo collega Marshall Pease generalizzò l'algoritmo per qualsiasi $n>0$, dimostrando che $3n+1$ era una condizione sia necessaria che sufficiente alla risoluzione del problema. Questi risultati, insieme a una successiva dimostrazione di Leslie Lamport sulla sufficienza di soli $3n$ computer attraverso l'uso delle firme digitali, furono pubblicati nell'articolo fondamentale Reaching Agreement in the Presence of Faults ("Raggiungere un accordo in presenza di guasti"). Per questo scritto, gli autori furono insigniti del Premio Edsger W. Dijkstra nel 2005.

Per rendere il problema della coerenza interattiva più facile da comprendere, Lamport inventò la pittoresca allegoria che oggi dà il nome al problema. Un gruppo di generali dell'esercito deve formulare un piano per attaccare una città. Nella sua versione originale, la storia vedeva i generali come comandanti dell'esercito albanese. Il nome venne in seguito cambiato, optando infine per "bizantino" su suggerimento di Jack Goldberg, così da scongiurare per il futuro qualsiasi rischio di recare offesa. Questa formulazione del problema, insieme ad alcuni risultati aggiuntivi, fu presentata dagli stessi autori in un loro articolo del 1982, The Byzantine Generals Problem ("Il problema dei generali bizantini").

Definizione informale

L'allegoria bizantina prende in considerazione un certo numero di generali bizantini che stanno attaccando una fortezza. I generali devono decidere in gruppo se attaccare o ritirarsi; anche se inizialmente alcuni potrebbero preferire l'attacco, mentre altri la ritirata, la cosa importante è che tutti i generali concordino su una decisione comune (ossia raggiungano il consenso), poiché un attacco poco convinto da parte di un manipolo di generali si trasformerebbe in una disfatta, e si rivelerebbe peggiore sia di un attacco coordinato che di una ritirata coordinata.

Il problema è complicato dalla presenza di generali traditori, i quali potrebbero non solo esprimere un voto per una strategia non ottimale, ma potrebbero farlo in modo selettivo. Ad esempio, se ci sono nove generali votanti, quattro dei quali sono a favore dell'attacco mentre altri quattro sono per la ritirata, il nono generale potrebbe inviare un voto di ritirata a coloro che sono a favore della ritirata, e un voto di attacco ai restanti. Coloro che hanno ricevuto il voto di ritirata dal nono generale si ritireranno, mentre gli altri attaccheranno (il che potrebbe avere esiti negativi per gli attaccanti). Il problema è ulteriormente complicato dal fatto che i generali sono fisicamente separati e devono inviare i propri voti tramite messaggeri, i quali potrebbero non riuscire a consegnare i messaggi o potrebbero falsificare i voti.

Senza la firma dei messaggi, la tolleranza ai guasti bizantini può essere raggiunta solo se il numero totale di generali è superiore a tre volte il numero dei generali sleali (difettosi). Ai messaggi mancanti può essere assegnato un valore di voto predefinito. Ad esempio, a un messaggio mancante può essere assegnato un valore "nullo". Inoltre, se dal consenso emerge che i voti nulli sono la maggioranza, si può adottare una strategia predefinita (ad es., la ritirata).

Solo se i generali leali fossero equamente distribuiti tra le varie opzioni, ossia non vi fosse un consenso chiaro, la soluzione sarebbe incerta, tuttavia in questo specifico caso qualsiasi scelta comune adottata sarebbe valida. Pertanto se non vi è un consenso chiaro, si opta tutti per una scelta predefinita, raggiungendo comunque il consenso.

Definizione formale

Dato un numero $n$ di processi, si richiede che al termine dell'algoritmo tutti i processi corretti impostino la variabile di decisione sullo stesso valore. Questo valore deve essere quello fornito dal processo comandante nel caso in cui questo sia corretto. I processi non corretti possono non inviare messaggi oppure inviarne con contenuto arbitrario. I messaggi non sono firmati. Pertanto, il comportamento dei traditori non deve inficiare la correttezza dell'algoritmo.

Sia $v_{i}$ l'informazione comunicata dall'$i$-esimo processo, ciascun processo deve poter combinare le informazioni $v_{1},v_{2},\cdots ,v_{n}$ in un piano di azione, in modo che tutti i processi affidabili giungano alla stessa conclusione.

Obiettivi desiderati

Il paper originale di Leslie elenca le seguenti condizioni desiderate per l'algoritmo risolutivo:

1. Tutti i processi affidabili devono decidere lo stesso piano d'azione.
2. Un piccolo numero di traditori non deve poter indurre i processi affidabili in un piano pessimo.

La condizione B è difficile da formalizzare, poiché richiederebbe di definire cosa sia un "piano pessimo". La condizione A viene raggiunta facendo sì che tutti i processi utilizzino lo stesso metodo per combinare le informazioni, e la condizione B viene raggiunta utilizzando un metodo robusto. Queste condizioni definiscono il problema. Tuttavia, sono troppo vaghe per essere programmate. Pertanto la ricerca di un algoritmo si basa invece sulle seguenti condizioni di consistenza.

Condizioni di consistenza

Un processo comandante deve inviare un ordine ai n - 1 processi affidabili tale che:

1. Tutti i processi affidabili obbediscano allo stesso ordine.
2. Se il processo comandante è affidabile, allora ogni processo affidabile obbedisce all'ordine che egli invia.

Si noti che se il comandante è leale, allora 1 deriva da 2. Tuttavia, il comandante non deve necessariamente essere leale.

Il limite matematico

Assumendo di aver già in precedenza dimostrato che nessuna soluzione esiste per il caso $n=3$ con un solo traditore, si può dimostrare che nessuna soluzione con meno di $3m+1$ generali può far fronte a $m$ traditori. La dimostrazione avviene per contraddizione: supponiamo esista una tale soluzione per un gruppo di $3m$ o meno generali e la utilizziamo per costruire una soluzione al caso $n=3$ con un solo traditore, cosa che tuttavia sappiamo essere impossibile. Chiamiamo i generali della soluzione ipotetica "generali albanesi" e quelli della soluzione costruita "generali bizantini". Quindi, partendo da un algoritmo che consente a $3m$ o meno generali albanesi di far fronte a $m$ traditori, costruiamo una soluzione che consente a tre generali bizantini di gestire un singolo traditore.

La soluzione si ottiene facendo sì che ciascuno dei generali bizantini rappresenti circa un terzo dei generali albanesi, ossia ogni generale bizantino rappresenta al massimo m generali albanesi. Il comandante bizantino simula fa anche le veci del comandante albanese più al massimo m - 1 luogotenenti albanesi, e ciascuno dei due luogotenenti bizantini rappresenta al massimo m luogotenenti albanesi. Poiché solo un generale bizantino può essere un traditore, e questi simula al massimo m albanesi, al massimo m dei generali albanesi sono traditori. Di conseguenza, la soluzione ipotetica garantisce che 1 e 2 valgano per i generali albanesi. Per la 1, tutti i luogotenenti albanesi simulati da un leale luogotenente bizantino obbediscono allo stesso ordine, che è l'ordine a cui egli stesso deve obbedire. È facile verificare che le condizioni 1 e 2 della soluzione per i generali albanesi implichino le corrispondenti condizioni per i generali bizantini, dunque abbiamo costruito la soluzione impossibile richiesta.

Esempi

Il caso irrisolvibile (n = 3)

Problema dei generali bizantini nel caso n = 3

Per dimostrare l'impossibilità di raggiungere il consenso con $n=3$ generali di cui $f=1$ traditore, è necessario utilizzare il modello del comandante e dei tenenti, originariamente formalizzato da Leslie Lamport. Il sistema è composto da un comandante $C$ e due tenenti $T_{1}$ e $T_{2}$.

Affinché l'algoritmo sia valido, devono essere soddisfatte due condizioni:

• Tutti i tenenti leali devono concordare sulla stessa azione.
• Se il comandante è leale, ogni tenente leale deve eseguire l'ordine che il comandante gli ha inviato.

Si analizzino i due seguenti scenari, in cui le comunicazioni avvengono in due fasi (il comandante invia l'ordine, successivamente i tenenti si scambiano quanto ricevuto).

Scenario A: Il Comandante è il traditore

Supponiamo che $C$ sia il traditore e voglia sabotare i tenenti leali inviando loro ordini discordanti.

• Fase 1: $C$ invia l'ordine $attack$ a $T_{1}$ e l'ordine $withdraw$ a $T_{2}$.
• Fase 2: I tenenti si scambiano i messaggi. Essendo leale, $T_{1}$ riferisce a $T_{2}$ la verità: "Il comandante mi ha ordinato $attack$". Allo stesso modo, $T_{2}$ riferisce a $T_{1}$: "Il comandante mi ha ordinato $withdraw$".

Alla fine delle comunicazioni, il tenente $T_{1}$ si trova con questa informazione: ha ricevuto $attack$ direttamente da $C$, ma il suo pari $T_{2}$ gli assicura che $C$ ha ordinato $withdraw$.

Scenario B: Il Tenente $T_{2}$ è il traditore

Supponiamo ora che $C$ sia leale e ordini a tutti di attaccare, ma che $T_{2}$ sia un traditore che vuole confondere $T_{1}$.

• Fase 1: $C$ invia l'ordine $attack$ sia a $T_{1}$ che a $T_{2}$.
• Fase 2: I tenenti si scambiano i messaggi. Il traditore $T_{2}$ decide di mentire a $T_{1}$ e gli riferisce falsamente: "Il comandante mi ha ordinato $withdraw$".

Alla fine delle comunicazioni, il tenente $T_{1}$ si trova con questa informazione: ha ricevuto $attack$ direttamente da $C$, ma il suo pari $T_{2}$ gli assicura che $C$ ha ordinato $withdraw$.

Il paradosso dell'indistinguibilità

Dal punto di vista del tenente leale $T_{1}$, lo Scenario A e lo Scenario B sono matematicamente indistinguibili. In entrambi i casi, l'input che $T_{1}$ riceve è identico: l'ordine diretto del comandante è in contraddizione con il messaggio riportato dall'altro tenente.

$T_{1}$ non ha alcun mezzo logico per dedurre chi stia mentendo. Se $T_{1}$ decidesse di fidarsi sempre del comandante (risolvendo lo Scenario B), nello Scenario A finirebbe per attaccare mentre $T_{2}$ si ritirerebbe, violando la prima condizione del consenso.

Questa asimmetria dell'informazione dimostra formalmente che un sistema con $n=3$ e $f=1$ non può tollerare un guasto bizantino, confermando il teorema per cui il consenso è raggiungibile solo se $n\geq 3f+1$.

Un caso risolvibile ($n=4$)

Il problema dei generali bizantini nel caso n = 4

Come dimostrato matematicamente da Pease, Shostak e Lamport, il problema dei generali bizantini è risolvibile se e solo se il numero totale di generali $n$ è strettamente maggiore di tre volte il numero dei traditori $f$, ovvero $n\geq 3f+1$. Nel caso sia presente un solo traditore ($f=1$), la configurazione minima funzionante richiede quindi $n=4$ generali (un comandante e tre tenenti).

La risoluzione si basa su un algoritmo di comunicazione in due fasi, in cui i generali leali incrociano le informazioni ricevute per smascherare eventuali discrepanze. L'algoritmo prevede che, al termine delle comunicazioni, ogni generale applichi una funzione di maggioranza sui dati raccolti per prendere la decisione finale.

Di seguito si analizzano i due scenari di guasto possibili, visibili nei diagrammi:

Scenario A: Un Tenente è il traditore

In questa configurazione, il Comandante è leale e invia a tutti i tenenti il medesimo ordine legittimo $v$ (es. "attaccare"). Il Tenente 3, tuttavia, è un traditore e cerca di sabotare l'azione.

• Prima fase: Il Comandante invia $v$ ai Tenenti 1, 2 e 3.
• Seconda fase: I tenenti si riferiscono a vicenda l'ordine appena ricevuto. Poiché il Tenente 1 è leale, riferirà correttamente l'ordine $v$. Il Tenente 3 (traditore) riferirà invece un falso ordine $x$ (es. "ritirarsi").

Si ponga l'attenzione sulla prospettiva del Tenente 2. Alla fine degli scambi, egli ha raccolto tre ordini:

• L'ordine $v$ ricevuto direttamente dal Comandante;
• L'ordine $v$ riportatogli dal Tenente 1;
• L'ordine $x$ riportatogli dal Tenente 3.

Costruendo il vettore delle decisioni $(v,v,x)$ e calcolandone la maggioranza, il Tenente 2 stabilisce univocamente che l'ordine corretto è $v$. L'intento del traditore viene così neutralizzato e tutti i tenenti leali eseguiranno l'ordine del Comandante.

Scenario B: Il Comandante è il traditore

In questo caso, i tre tenenti sono tutti leali, mentre il Comandante è il traditore. Il suo obiettivo è inviare ordini contrastanti affinché i tenenti non agiscano all'unisono.

• Prima fase: Il Comandante invia deliberatamente tre ordini diversi: $x$ al Tenente 1, $y$ al Tenente 2 e $z$ al Tenente 3.
• Seconda fase: I tre tenenti, essendo tutti leali, si scambiano le informazioni in modo del tutto sincero. Il Tenente 1 comunica di aver ricevuto $x$, il Tenente 2 comunica $y$ e il Tenente 3 comunica $z$.

Alla fine degli scambi si verifica una situazione fondamentale: tutti i tenenti possiedono lo stesso identico vettore di informazioni. Dal punto di vista del Tenente 1, il vettore degli ordini è $(x,y,z)$. Anche il Tenente 2 e il Tenente 3 dispongono esattamente del vettore $(x,y,z)$.

Poiché tutti e tre i tenenti applicano la medesima funzione deterministica allo stesso vettore (ad esempio, stabilendo che in assenza di una maggioranza assoluta si debba ripiegare sull'ordine di default "ritirata"), arriveranno tutti alla medesima conclusione. La prima condizione vitale del consenso (tutti i tenenti leali devono concordare sulla stessa azione) è dunque pienamente rispettata, vanificando la strategia del comandante traditore.

Soluzione

In un sistema sincrono

Il caso sincrono del problema è costituito dalla situazione in cui il sistema si compone di $n$ processi e al termine di ogni round i processi leali ricevono sempre $n$ messaggi.

Nell'articolo originale di Lamport, Shostak e Pease è dimostrato che non esiste soluzione al problema se il numero di processi non corretti è maggiore o uguale a un terzo del numero totale di processi.

Nella Blockchain di Bitcoin

Il funzionamento di Bitcoin dimostra che l'assunto di Lamport cambia se i nodi della rete vengono remunerati quando operano senza errori; in tal caso il problema dei generali bizantini non si presenta fintanto che il numero dei processi non corretti è maggiore o uguale al 50%+1 del numero totale di processi. In altre parole, in una rete in cui i nodi (processi) hanno una convenienza economica ad operare correttamente, l'affidabilità del sistema aumenta perché il funzionamento complessivo è corretto con il 50%+1 dei processi senza errori, mentre nella soluzione senza incentivi economici il sistema per essere affidabile richiede che il 66%+1 dei processi sia senza errori .

Origine del nome del problema

Quando il problema fu ideato, nel 1982, l'autore Leslie Lamport cercò di renderlo semplice da comprendere e ricordare scegliendo una nazionalità reale per i generali protagonisti della storia. Per evitare di causare malumori optò inizialmente per la definizione generali albanesi, supponendo che questo avrebbe avuto la minor probabilità di generare offese, ma successivamente decise il nome di generali bizantini, così da avere la certezza che nessun popolo potesse sentirsi direttamente chiamato in causa.

Bibliografia

• Leslie Lamport, Robert Shostak, Marshall Pease, The Byzantine Generals Problem, in ACM Transactions on Programming Languages and Systems, vol. 4, n. 3, luglio 1982, pp. 382-401. URL consultato il 30 giugno 2008.
• George Coulouris, Jean Dollimore, Tim Kindberg, Coordination and agreement, in Distributed Systems, 3ª ed., Addison-Wesley, 2001 [1988], ISBN 0-201-61918-0.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su problema dei generali bizantini