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]
Esempi[modifica | modifica wikitesto]
Diversi esempi di fallimenti bizantini che si sono verificati sono riportati in due articoli di riviste equivalenti.[5][6] Questi e altri esempi sono descritti nelle pagine web di DASHlink della NASA.[7]
La rete Bitcoin lavora in parallelo per creare una blockchain Proof-of-Work (PoW), consentendo al sistema di superare i fallimenti bizantini e di ottenere una visione globale coerente dello stato del sistema. Alcune blockchain Proof-of-stake (PoS), invece, utilizzano anche algoritmi BFT.[8]
Alcuni sistemi aeronautici, come il Boeing 777 Aircraft Information Management System (tramite la rete ARINC 659 SAFEbus), il Boeing 777 Flight Control System e i sistemi di controllo di volo del Boeing 787, utilizzano la tolleranza di errore bizantina; trattandosi di sistemi in tempo reale, le loro soluzioni con tolleranza di errore bizantina dovrebbero avere una latenza molto bassa. Ad esempio, il SAFEbus può raggiungere la tolleranza di errore bizantina con un ritardo aggiuntivo dell'ordine di un microsecondo.[9][10] Lo SpaceX Dragon incorpora la tolleranza di errore bizantina nel suo progetto.[11]
I meccanismi di tolleranza ai guasti bizantini utilizzano componenti che ripetono un messaggio in arrivo (o semplicemente la sua firma) ad altri destinatari di quel messaggio in arrivo. Tutti questi meccanismi partono dal presupposto che la ripetizione di un messaggio blocchi la propagazione dei sintomi bizantini. Per i sistemi ad alta affidabilità o criticità per la sicurezza, è necessario dimostrare che queste ipotesi soddisfano un livello accettabile di copertura dei guasti. Nel fornire prove attraverso i test, una delle difficoltà consiste nel generare una gamma sufficientemente ampia di segnali con sintomi bizantini.[12][13][14]
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.
- ^ 23rd DASC: The 23rd Digital Avionics Systems Conference: Proceedings: Salt Lake City, UT, October 24-28, 2004, su books.google.com. URL consultato il 23 dicembre 2023.
- ^ Byzantine Fault Tolerance, from Theory to Reality, su link.springer.com. URL consultato il 23 dicembre 2023.
- ^ Real System Failures, su c3.ndc.nasa.gov. URL consultato il 23 dicembre 2023.
- ^ Proof of Work vs. Proof of Stake, su www.fairdesk.com. URL consultato il 23 dicembre 2023.
- ^ Bus Architectures For Safety-Critical Embedded Systems (PDF), su www.csl.sri.com. URL consultato il 23 dicembre 2023.
- ^ Safety critical avionics for the 777 primary flight controls system, su ieeexplore.ieee.org. URL consultato il 23 dicembre 2023.
- ^ ELC: SpaceX lessons learned, su lwn.net. URL consultato il 23 dicembre 2023.
- ^ The Byzantine hardware fault model, su ieeexplore.ieee.org. URL consultato il 23 dicembre 2023.
- ^ Experiences with Fault-Injection in a Byzantine Fault-Tolerant Protocol, su link.springer.com. URL consultato il 23 dicembre 2023.
- ^ US7475318B2 Method for testing the sensitive input range of Byzantine filters, su worldwide.espacenet.com. URL consultato il 23 dicembre 2023.
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
