appunti-steffo/9 - Algoritmi distribuiti/3 - Computazione distribuita/7 - Algoritmi affidabili/algoritmo senza nome Las Vegas di consenso asincrono non-deterministico bizantino.md

algoritmo algoritmo Las Vegas di consenso asincrono non-deterministico bizantino, derivante dal protocollo di Ben-Or Las Vegas.

restrizioni al modello dei sistemi distribuiti aggiuntive

• restrizione di tempo
  • terminazione ignorata

comportamento

[!Summary]+ Summary ma non troppo

Tutte le entità partono che si trovano al round 1, poi avanzano di round man mano che sono completate iterazioni.

I messaggio ricevuti appartenenti a un round precedente al proprio sono scartati; quelli appartenenti a un round successivo al proprio sono archiviati per uso futuro.

Ad ogni round, ogni entità fa il broadcast problem del proprio valore, e attende di ricevere Entities - Fallible messaggio.

Se almeno Entities - 2 \cdot Fallible messaggio che ha ricevuto hanno lo stesso valore, decide per quello.

Se almeno Entities - 4 \cdot Fallible messaggio che ha ricevuto hanno lo stesso valore, sceglie quello e passa al round successivo.

Altrimenti, sceglie un valore casuale e passa al round successivo.

algoritmo corretto

[!Success] Le entità che non sono le prime a decidere condividono (Entities - 2 \cdot Fallible) - 2 \cdot Fallible vicini di un'entità non-guasto con la prima a decidere, quindi al round successivo a una decisione l'algoritmo terminerà sicuramente in favore a quella decisione.

costo computazionale distribuito

Costo	notazione O-grande
9 - Algoritmi distribuiti/1 - Problemi algoritmici/tempo	\sim O\left( 2^{Entities} \right)