Bizantini

Lezione del 2019-05-30 gio

Nota

NdR. Scopo di questa lezione non è presentare il dettaglio dell’algoritmo, ma introdurre la problematica e chiarire che adottando questo algoritmo si ha un pesante aumento di messaggi che viaggiano nel sistema.

Nei sistemi distribuiti vi sono le seguenti problematiche da affrontare:

  • alcuni dei computer possono guastarsi;

  • alcune componenti guaste possono inviare informazioni diverse rispetto altre componenti;

  • quando vi sono dei guasti è necessario decidere (concordare) quale valore è affidabile;

  • in caso di reti peer-to-peer:

    • i nodi funzionanti devono concordare insieme che cosa fare;

    • i nodi guasti generano messaggi corrotti e fuorvianti;

    • motivi non dolosi: bug del software, guasti hardware, guasti di alimentazione;

    • motivi dolosi: sistemi compromessi.

Ad esempio nel calcolo dei bitcoin si devono affrontare i problemi predetti, e in questo contesto si usa una versione modificata dei Bizantini. Modificata perché, come nel caso di Paxos, la versione canonica sa quanti nodi formano il sistema distribuito; nel calcolo dei bitcoin questa caratteristica non è valida.

L’algoritmo dei Bizantini ha lo stesso scopo di Paxos: raggiungere il consenso tra N processi. Differiscono riguardo le assunzioni: nel caso di Paxos si ipotizza che un sistema, se fallisce, non parla più, invece nel caso dei Bizantini in caso di fallimento il sistema può non essere silente (quale ne sia il tipo di motivo: doloso o meno).

Si noti che l’algoritmo dei bizantini non ha lo scopo di individuare i nodi non funzionanti, ma solo di capire qual’è il valore giusto da utilizzare.

Formalizzazione

Lamport ha formalizzato il problema ricorrendo all’analogia di un esercito bizantino che assedia una città nemica, considerando gli ufficiali dell’esercito bizantino l’equivalente dei nodi o dei componenti dei nodi da analizzare.

Riprendendo l’analogia, abbiamo:

  • ogni unità dell’esercito è diretta da un suo generale;

  • vi sono n generali, alcuni dei quali sono dei traditori;

  • tutte le unità sono accampate all’esterno del castello assediato, osservando il nemico;

  • le unità comunicano tra loro tramite messaggeri;

  • i requisiti stabiliscono:

    • G1: tutti i generali leali decidono lo stesso piano d’azione;

    • G2: un piccolo numero di generali traditori non possono fare in modo che i generali leali adottino un piano d’azione sbagliato.

Qual’è la logica generale di questo scenario?.

Nel campo di battaglia tutti i generali hanno la stessa visione del contesto ed arrivano alla stessa conclusione (attaccare o non attaccare). Dopo di che, un generale leale comunica la sua conclusione a tutti gli altri generali. Un generale non leale comunicherà conclusioni diverse a generali diversi (con lo scopo di sparpagliare le forze).

Come sistema distribuito, ogni processo usando la stessa funzione di scelta arriverebbe alla stessa conclusione e la invierebbe agli altri processi. Ma processi danneggiati o compromessi comunicherebbero valori diversi da quelli della funzione di scelta valida.

Assunzioni della soluzione orale:

  • i messaggi non sono firmati, sono senza cifra;

  • è possibile capire eventuali disturbi di comunicazione, e quindi rigettare i messaggi con contenuto alterato;

  • non vi è assenza di messaggio;

Una soluzione naive del problema potrebbe essere:

  • l’i-esimo generale invia la propria scelta v(i) a tutti gli altri generali;

  • tutti i generali combinano le loro informazioni v(1), v(2), … v(n) nello stesso modo;

  • si sceglie la maggioranza: majority(v(1), v(2), … v(n) ), ignorando la presenza mioritaria di traditori.

Purtroppo la soluzione naive non funziona perché:

  • i traditori possono inviare informazioni diverse ai diversi generali;

  • in tal modo i generali leali possono arrivare a decisioni contrastanti tra loro perché i set di dati di partenza possono essere diversi;

se ne deduce che in questo scenario esisterebbe il requisito che due diversi generali leali devono usare lo stesso set di valori v(i) per decidere lo stesso piano d’azione. Requisito che non è soddisfacibile.

Per analizzare un algoritmo funzionante, effettuiamo una riduzione del problema generale:

  • limitiamoci a considerare il caso di un singolo generale che invia ordini agli altri, quindi:

    • (BGP) un comandante generale deve inviare un ordine ai suoi luogotenenti 1;

  • con validità della interactive consistency condition:

    • (IC1) tutti i luogotenenti leali obbediscono allo stesso ordine;

    • (IC2) se il comandate generale è leale, allora ogni luogotenente leale obbedisce ai suoi ordini;

Si nota che se il comandante generale è leale, allora IC2 => IC1 2; in generale questa assunzione non è soddisfatta.

Il problema originale si riduce a questo con l’assunzione che ogni generale invia il suo ordine v(i) usando la soluzione del BGP, con gli altri generali che agiscono come luogotenenti.

Caso impossibile: i tre generali con un traditore

Nel caso minimale di un comandante e due luogotenenti, con un traditore, si dimostra che il problema non è risolvibile.

Supponendo di avere due possibili messaggi: attaccare e ritirarsi, si hanno due possibili situazioni, illustrate nel seguente diagramma, in cui la figura colorata è un traditore.

_images/38_3_bizantini.svg

A sinistra il traditore è il luogotenente 2, mentre a destra il traditore è il comandante in capo. Come si vede, confrontando i due diagrammi, il luogotenente 1 non ha alcuna possibilità di capire la situazione: a sinistra ha un comandante leale; ma i due messaggi che arrivano, sarebbero potuti arrivare anche con la situazione a destra. Non avendo possibilità di discriminare le due situazioni, luogotenente 1 non ha alcuna possibilità di decidere cosa fare.

Algoritmo

Quindi per risolvere il caso minimo, con un traditore, occorrono 4 generali. Più in generale, con m traditori, sono necessari 3m + 1 generali per risolvere il problema.

Si noti la differenza rispetto Paxos. In quel caso i guasti erano dei fermi macchina: una macchina guasta non inviava messaggi. In queste condizioni, dati m nodi guasti, erano sufficienti 2n + 1 nodi. In questo contesto, invece, il fatto che il nodo guasto continui ad mettere messaggi, abbassa la soglia di tolleranza al guasto: ora servono 3m + 1 nodi per gestire m nodi guasti.

L’algoritmo prevede più passaggi per risolvere il problema, in particolare sono necessari m + 1 passaggi. Un passaggio serve per comunicare le decisioni di ogni nodo a tutti gli altri nodi. I passaggi successivi servono per ricomunicare agli altri nodi la ricezione del valore da parte loro. Dopo di che i valori ricevuti dai nodi nei diversi passaggi vengono combinati opportunamente 3.

Considerando il fatto che ogni nodo deve comunicare a tutti gli altri non solo il proprio valore, ma anche chi ha detto cosa, si capisce che la quantià di messaggi che viaggiano nel sistema aumenta rapidamente all’aumentare dei nodi. Per questo motivo l’algoritmo dei bizantini è poco adatto a gestire impianti di sensori: l’elevato numero di messaggi tende ad esaurire rapidamente le batterie di alimentazione.

Se si fa ricorso alla tecnica della firma dei messaggi da parte del mittente, il numero di messaggi si riduce drasticamente. Per capirlo si riprenda il caso impossibile dei 3 generali con un traditore tra loro. E si analizzai il caso (b) a destra. Se un comandante in capo invia messaggi contraddittori firmati ai suoi sottoposti, e i sottoposti si scambiano i messaggi ricevuti, sono in grado di capire che il comandante ha inviato messaggi diversi. Quindi se i messaggi sono firmati dal mittente, un traditore non può inviare messaggi diversificati, ma solo limitarsi a evitare di comunicare i messaggi ricevuti.

Peccato che la firma introduce a sua volta necessità di elaborazione sul sensore.

Una descrizione dell’algoritmo dei bizantini è contenuta in [PEASL1980], articolo sintetico, maggiormente orientato al formalismo matematico. Una descrizone meno formale, ma comunque complessa, è consultabile in [LAMSP1982].


1

Questo è il byzantine general problem (BGP).

2

Se il comandante generale è leale IC2 implica IC1. Si ricorda qui di seguito la tabella di verità dell’operazione di implicazione:

IC2

IC1

IC2 => IC1

T

T

T

T

F

F

F

T

T

F

F

T

3

L’algoritmo di ricombinazione è uguale per tutti i nodi.