Problema del consenso: Tolleranza a Guasti Bizantini

30/10/07 (4 ore):

Tolleranza a guasti bizantini in sistemi distribuiti sincroni a passaggio di messaggi. Il problema dei generali Bizantini. Impossibilità della risoluzione con 3 processori di cui 1 sleale. Caso generale: impossibilità della risoluzione con n processori di cui almeno n/3 sleali. Algoritmo esponenziale di consenso per n processori di cui f<n/3 Bizantini. Albero delle computazioni associato ad ogni processore. Dimostrazione di correttezza dell'algoritmo esponenziale: soddisfacimento delle condizioni di terminazione, validità ed accordo. Complessità dei messaggi dell'algoritmo esponenziale.

Algoritmo polinomiale di consenso per n processori di cui f<n/4 Bizantini. Dimostrazione di correttezza dell'algoritmo, numero di rounds e complessità.
Dispense: 64, 65, 66, 67, 68. 69, 70, 71, 72, 73, 74, 75. 76. 77, 78, 79, 80.

31/10/07:

Approfondimento: Risoluzione del problema dei due generali con canale di comunicazione sicuro. Non correttezza dell'algoritmo esponenziale di consenso per fallimenti Bizantini con n=3 ed f=1. Non correttezza dell'algoritmo polinomiale di consenso per fallimenti Bizantini con n=4 ed f=1.