Istituto di Scienza e Tecnologie dell'Informazione     
Di G., Guidotti M., Grandoni F., Simoncini L. A gracefully degradable algorithm for byzantine agreement. In: Sixth Symposium on Reliability in Distributed Software and Database Systems. (Williamsburg, Virginia, 17 - 19 March 1987). Proceedings, pp. 188 - 200. IEEE Computer Society Press, 1987.
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.

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