Problema dei generali bizantini

Il problema dei generali bizantini è un problema informatico su come raggiungere consenso in situazioni in cui è possibile la presenza di errori. Il problema consiste nel trovare un accordo, comunicando solo tramite messaggi, tra componenti diversi nel caso in cui siano presenti informazioni discordanti.

Informalmente il problema è esemplificato dalla situazione in cui tre o più generali bizantini debbano decidere se attaccare o ritirarsi dato un ordine da un comandante superiore. Uno o più dei generali potrebbero essere dei traditori con l'intenzione di confondere gli altri, quindi potrebbe verificarsi il caso in cui il comandante dia ordini discordanti ai generali oppure il caso in cui uno dei generali comunichi ai propri colleghi un ordine differente da quello impartito dal comandante.^[1]

La soluzione al problema permette ai generali leali di evitare queste trappole.

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.^[1]

Questa sezione sull'argomento informatica è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento.

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.^[2][3]

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% dei processi sia senza errori ^{[4] [5]}.

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.^[6]

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

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