Consenso in un Sistema Sincrono

Ipotesi:

Sistema sincrono
$N$ processi
Al più $f$ processi esibiscono fallimenti per crash
Disponibilità di una primitiva B-multicast che garantisce che i processi destinatari corretti ricevano il messaggio, finchè il mittente (multicaster) non fallisce
- $multicast(g,m)$ invia il messaggio $m$ a un gruppo $g$ di processi; $m$ porta con sè un identificativo del mittente e un identificativo del gruppo $g$
- $deliver(m)$ consegna al chiamante il messaggio $m$
- I processi non mentono su origine e destinazione dei messaggi

$V_i^k$ vettore dei valori proposti noti al processi $p_i$ all’inizio del ciclo $k$

$f$ numero guasti per crash tollerati dall’algoritmo

$f+1$ numero complessivo di iterazioni

Nel caso peggiore, nelle $f+1$ iterazioni si verifica il numero massimo di crash possibili $f$

L’algoritmo garantisce che al termine i processi corretti sopravvissuti raggiungano il consenso

Nell’iterazione $k$ il processo $p_i$ $(i = 1,..,N)$:

Invia (B-multicast) i valori che non ha inviato nei cicli precedenti
Riceve (B-deliver) i messaggi analoghi ed aggiorna $V_i^k$ con i nuovi valori ricevuti

Dopo $f+1$ cicli, ogni processo sceglie il valore minimo di $V_i^{f+1}$ come valore di decisione

La durata di un ciclo è limitata da un apposito timeout