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 computer difettosi risultasse risolvibile. Shostak dimostrò che era necessario un minimo di computer, e ideò un protocollo di messaggistica a due round per che avrebbe funzionato per il caso . Il suo collega Marshall Pease generalizzò l'algoritmo per qualsiasi , dimostrando che 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 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 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 l'informazione comunicata dall'-esimo processo, ciascun processo deve poter combinare le informazioni 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:

Tutti i processi affidabili devono decidere lo stesso piano d'azione. 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:

Tutti i processi affidabili obbediscano allo stesso ordine. 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 con un solo traditore, si può dimostrare che nessuna soluzione con meno di generali può far fronte a traditori. La dimostrazione avviene per contraddizione: supponiamo esista una tale soluzione per un gruppo di o meno generali e la utilizziamo per costruire una soluzione al caso 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 o meno generali albanesi di far fronte a 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)

Per dimostrare l'impossibilità di raggiungere il consenso con generali di cui traditore, è necessario utilizzare il modello del comandante e dei tenenti, originariamente formalizzato da Leslie Lamport. Il sistema è composto da un comandante e due tenenti e .

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 sia il traditore e voglia sabotare i tenenti leali inviando loro ordini discordanti. Fase 1: invia l'ordine a e l'ordine a . Fase 2: I tenenti si scambiano i messaggi. Essendo leale, riferisce a la verità: "Il comandante mi ha ordinato ". Allo stesso modo, riferisce a : "Il comandante mi ha ordinato ". Alla fine delle comunicazioni, il tenente si trova con questa informazione: ha ricevuto direttamente da , ma il suo pari gli assicura che ha ordinato .

Scenario B: Il Tenente è il traditore

Supponiamo ora che sia leale e ordini a tutti di attaccare, ma che sia un traditore che vuole confondere . Fase 1: invia l'ordine sia a che a . Fase 2: I tenenti si scambiano i messaggi. Il traditore decide di mentire a e gli riferisce falsamente: "Il comandante mi ha ordinato ". Alla fine delle comunicazioni, il tenente si trova con questa informazione: ha ricevuto direttamente da , ma il suo pari gli assicura che ha ordinato .

Il paradosso dell'indistinguibilità

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

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

Questa asimmetria dell'informazione dimostra formalmente che un sistema con e non può tollerare un guasto bizantino, confermando il teorema per cui il consenso è raggiungibile solo se .