Problema del Consenso

Obiettivo informale: Far convergere processi distribuiti su un valore comune

Formalmente:

• $N$ processi che comunicano tramite messaggi
• Canali di comunicazione affidabili
• Processi possono fallire (crash o bizantini)
• Ogni processo $pᵢ$:
  • Propone un valore $vᵢ$ (da un insieme $D$)
  • Ha una variabile di decisione $dᵢ$ (inizialmente indecisa)
  • Mira a raggiungere uno stato di decisione ($dᵢ$ immutabile)

Requisiti

• Terminazione: Prima o poi ogni processo corretto prende una decisione
• Accordo: Due qualsiasi processi corretti non decidono diversamente
• Integrità: Se tutti i processi corretti propongono lo stesso valore, la decisione finale di ogni processo corretto corrisponde a quel valore

In alcune formulazioni possiamo trovare anche:

• Safety: Tutti i validatori raggiungeranno un certo consenso su un valore proposto dai processi corretti, senza divergenze
• Liveness: Tutti i validatori raggiungeranno un certo consenso entro un tempo utile, ovvero non si ha stallo nel consenso

Problema dei Generali Bizantini

• Difetto bizantino: Condizione di un sistema distribuito in cui i componenti possono guastarsi e c’è imperfetta conoscenza sull’eventuale guasto di un componente

Scenario:

• Un comandante e diversi luogotenenti (generali)
• Il comandante invia un ordine (attacca/ritirati) ai luogotenenti
• I luogotenenti si scambiano i messaggi ricevuti