Generali bizantini, comunicazione e consenso

Il problema dei due generali

In un articolo del 1975, gli informatici Akkoyunlu, Akandham e Huber dell’Università di New York, affrontano diversi temi riguardanti la comunicazione fra computer e concludono la pubblicazione con un esempio nel quale dimostrano che non è possibile implementare un protocollo tale da garantire a tutti gli interlocutori che un messaggio sia stato correttamente trasmesso e ricevuto da tutti.
L’esempio originale trattava di gangster che dovevano coordinare i propri uomini dislocati in varie parti della città per compiere un grosso colpo criminoso.
Oggi il problema viene illustrato solitamente sotto forma del Problema dei due generali.

Due eserciti alleati devono attaccare una città fortificata. Le armate sono accampate su due colline e la città si trova nella vallata che le separa.
I generali al comando delle due armate non hanno altro modo per comunicare se non spedire dei messaggeri verso l’altro esercito (non sono previste soluzioni fantasiose come i cellulari o i segnali di fumo!) e questi messaggeri devono necessariamente attraversare la vallata per raggiungere la loro destinazione.
La vallata è ovviamente sorvegliata dai nemici per cui vi è il rischio che i messaggeri vengano catturati prima di arrivare dall’altra parte.
Per la buona riuscita dell’attacco è indispensabile che i due eserciti attacchino contemporaneamente, altrimenti verrebbero sopraffatti, e affinché l’attacco possa essere sincronizzato è indispensabile che i due generali possano accordarsi sull’ora in cui sferrarlo utilizzando i suddetti messaggeri.

E’ facile rendersi conto che la conquista della città nemica, dal punto di vista dei generali, conterrà sempre una certa percentuale di incertezza, perché anche impegnando un numero enorme di messaggeri, dal primo recante il messaggio originale, ai successivi con una eventuale conferma di ricezione, essi non potranno mai avere la certezza che l’ultimo messaggero della serie sia giunto incolume a destinazione.

Il problema, che nel caso dei due generali risulta non risolubile, è stato generalizzato da Lamport, Shostak e Pease in una pubblicazione del 1985, in cui, grazie ad un’idea di Lamport, si parla per la prima volta di Problema dei Generali Bizantini.

Lo scenario qui descritto è simile, ma più generale in quanto il numero di eserciti accampati attorno alla città da conquistare è arbitrario e la variabile che può compromettere l’attacco è la possibile presenza di traditori fra gli alti ranghi delle armate.
I traditori produrranno dei messaggi alterati in modo da impedire ai generali leali di raggiungere il consenso sul momento più adatto per sferrare l’attacco.
L’articolo dimostra che, in presenza di m traditori, affinché possano raggiungere il consenso, i generali leali debbano essere almeno 3m+1.

Nell’immagine sotto vediamo il caso di impossibilità di raggiungere il consenso come illustrato dagli autori.

Se supponiamo che il messaggio possa essere o “Ritirata” o “Attacco” e i soggetti in gioco siano solo 3, un comandante e due luogotenenti, si vede come il luogotenente 1 non possa distinguere il caso in cui il traditore sia il comandante o il luogotenente 2 perché egli vede in entrambi i casi due messaggi ugualmente discordanti.

Dopo aver mostrato il caso di impossibilità, gli autori mostrano che è possibile ideare un algoritmo ricorsivo che permette di raggiungere il consenso nel caso in cui i generali leali siano almeno 3m+1, ma nel generalizzare il risultato mettono in gioco un esercito albanese oltre a quello bizantino! La dimostrazione ne risulta alquanto intricata da seguire e va oltre gli scopi di questo articolo.

Dopo l’articolo di Lamport, Shostak e Pease, in informatica è diventata di uso comune l’espressione BFT=Byzantine Fault Tolerance per descrivere la resistenza di un algoritmo al problema dei generali bizantini.

Nel paragrafo che segue vediamo una soluzione al problema particolarmente efficace utilizzata nell’implementazione della blockchain di Bitcoin.