An algorithm for Byzantine Agreement without authentication in a set of n processes is presented, where n > 3t and t is the maximum allowable number of faulty processes. This algorithm, called POM (Pruned DM), is based on the same idea as that inspiring the algorithm DM described in [LSP], but it can exhibit early stopping whenever it is possible. The particular feature of this algorithm is that its performance improves as the actual number of faulty processes decreases and theiir behaviour becomes less malicious. It is shown that POM rapidly converges to the agreement if the actual number of faulty processes is less than t/2; if the sender process is not faulty, 3 rounds and 2(n-1) message exchanges per process are necessary to reach the agreement. The achieved early stopping does not violate the f+2 lower bound of [DRSb]. A comparison with known algorithms based on similar hypotheses is made.
A gracefully degradable algorithm for byzantine agreement
Grandoni F;
1987
Abstract
An algorithm for Byzantine Agreement without authentication in a set of n processes is presented, where n > 3t and t is the maximum allowable number of faulty processes. This algorithm, called POM (Pruned DM), is based on the same idea as that inspiring the algorithm DM described in [LSP], but it can exhibit early stopping whenever it is possible. The particular feature of this algorithm is that its performance improves as the actual number of faulty processes decreases and theiir behaviour becomes less malicious. It is shown that POM rapidly converges to the agreement if the actual number of faulty processes is less than t/2; if the sender process is not faulty, 3 rounds and 2(n-1) message exchanges per process are necessary to reach the agreement. The achieved early stopping does not violate the f+2 lower bound of [DRSb]. A comparison with known algorithms based on similar hypotheses is made.File | Dimensione | Formato | |
---|---|---|---|
prod_419694-doc_148426.pdf
solo utenti autorizzati
Descrizione: A gracefully degradable algorithm for byzantine agreement
Tipologia:
Versione Editoriale (PDF)
Dimensione
2.14 MB
Formato
Adobe PDF
|
2.14 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.