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

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

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

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

In un sistema sincrono

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

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

^ ^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

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.