Problema dei generali bizantini

Da Wikipedia, l'enciclopedia libera.

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

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, dati f processi non corretti, il numero totale di processi è N\leq 3f.[3][4]

Note[modifica | modifica wikitesto]

  1. ^ Coulouris et al., p. 453
  2. ^ Coulouris et al., p. 453
  3. ^ Lamport et al.
  4. ^ Coulouris et al., p. 456

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 [1988], 2001, ISBN 0-201-61918-0.