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.
Definizione informale
[modifica | modifica wikitesto]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.
Definizione formale
[modifica | modifica wikitesto]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]
Soluzione
[modifica | modifica wikitesto]
In un sistema sincrono
[modifica | modifica wikitesto]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]
Origine del nome del problema
[modifica | modifica wikitesto]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.[4]
Note
[modifica | modifica wikitesto]- ^ a b Coulouris et al., p. 453.
- ^ Lamport et al.
- ^ Coulouris et al., p. 456.
- ^ The Byzantine Generals Problem, su microsoft.com, Microsoft. URL consultato il 31 agosto 2017.
Bibliografia
[modifica | modifica wikitesto]- 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
[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su problema dei generali bizantini
