Zyzzyva: analisi ed implementazione dell’algoritmo per consenso in sistemi distribuiti

Nell’ambito dei sistemi distribuiti, caratterizzati dall’assenza di memoria condivisa, il modo più diffuso che hanno i processi di comunicare tra loro è con uno scambio di messaggi attraverso una rete asincrona. L’assenza di memoria condivisa implica il fatto che ci potrebbero essere delle inconsistenze nello stato dei vari nodi che compongono il sistema con conseguente invio di dati errati all’applicazione che li richiede; altre possibilità dovute all’architettura distribuita possono essere fallimento di un nodo del sistema o il fallimento della rete di comunicazione. Questi errori portano alla necessità di implementare algoritmi per arrivare al consenso, cioé ottenere un accordo sullo stato del sistema tra macchine inaffidabili connesse in una rete asincrona. Nel contesto del consenso ha molta importanza raggiungere il consenso in un sistema che presenta la possibilità di “Byzantine Failure”: il fallimento bizantino è relativo al problema che alcuni nodi del sistema potrebbero essere compromessi o comportarsi in maniera arbitraria, mandando quindi valori errati come risposta a una richiesta. Sono dunque nati vari algoritmi per assicurare sistemi con una Byzantine Fault Tolerance (BFT), dove per BFT si indica la capacità di funzionare in modo corretto, e dunque raggiungere il consenso tra i nodi del sistema nonostante la presenza di nodi bizantini. Un contesto in cui questi algoritmi sono molto utilizzati è quello dei sistemi State Machine Replication (SMR), che è un metodo generale per implementare un servizio fault-tolerant replicando i server e coordinando le interazioni del client con le repliche server.