PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Di Giandomenico F., Guidotti M. L., Grandoni F., Simoncini L. Gracefully degradable algorithm for byzantine agreement. In: Computer systems science and engineering, vol. 3 (1) pp. 32 - 40. Butterworth Scientific, 1988.
 
 
Abstract
(English)
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 OM), is based on the same idea as that inspiring the algorithm OM described in Lamport et al.(2), but it can exhibit early stopping whenever possible. The particular feature of this algorithm is that its performance improves as the actual number of faulty processes decreases and as their behaviour becomes less malicious. It is shown that POM rapidly converges to 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 - 2) message exchanges per process are necessary to reach the agreement. The achieved early stopping does not violate the f + 2 lower bound of Dolev et al.(1983)[5]. A comparison with known algorithms based on similar hypotheses is made.
Subject Byzantine agreement
Distributed algorithms
Unreliable distributed systems


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional