Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2 ) Messages, O(1) Time, and no Signature

Abstract : This paper presents a new algorithm that reduces multivalued consensus to binary consensus in an asynchronous message-passing system made up of n processes where up to t may commit Byzantine failures. This algorithm has the following noteworthy properties: it assumes t < n/3 (and is consequently optimal from a resilience point of view), uses O(n 2) messages, has a constant time complexity, and does not use signatures. The design of this reduction algorithm relies on two new all-to-all communication abstractions. The first one allows the non-faulty processes to reduce the number of proposed values to c, where c is a small constant. The second communication abstraction allows each non-faulty process to compute a set of (proposed) values such that, if the set of a non-faulty process contains a single value, then this value belongs to the set of any non-faulty process. Both communication abstractions have an O(n 2) message complexity and a constant time complexity. The reduction of multivalued Byzantine consensus to binary Byzantine consensus is then a simple sequential use of these communication abstractions. To the best of our knowledge, this is the first asynchronous message-passing algorithm that reduces multivalued consensus to binary consensus with O(n 2) messages and constant time complexity (measured with the longest causal chain of messages) in the presence of up to t < n/3 Byzantine processes, and without using cryptography techniques. Moreover, this reduction algorithm tolerates message re-ordering by Byzantine processes. Une réduction du consensus multivalué au consensus binaire en présence d'asynchronisme, de t < n/3 processus byzantins, avec un temps constant, O(n 2) messages, et pas de signatures Résumé : Cet article présente un algorithme réparti qui, dans un système asynchrone de n processus qui communiquent par passage de messages, et qui comprend jusqu'à t processus byzantins, ramène le problème du consensus multivalué au problème du consensus binaire. Cette réduction est optimale par rapport à t (t < n/3), requiert un temps constant et O(n 2) messages, et n'utilise aucun élément cryptographique (i.e., pas de signatures). Elle considère donc un adversaire donc la la puissance de calcul peut être illimitée.
Type de document :
Pré-publication, Document de travail
2015
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01102496
Contributeur : Michel Raynal <>
Soumis le : mardi 13 janvier 2015 - 16:00:04
Dernière modification le : mercredi 16 mai 2018 - 11:23:14
Document(s) archivé(s) le : mardi 14 avril 2015 - 10:26:20

Fichiers

RR-2024-Multivalued.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas de modifications 4.0 International License

Identifiants

  • HAL Id : hal-01102496, version 1

Citation

Achour Mostefaoui, Michel Raynal. Asynchronous Byzantine Systems: From Multivalued to Binary Consensus with t < n/3, O(n 2 ) Messages, O(1) Time, and no Signature. 2015. 〈hal-01102496〉

Partager

Métriques

Consultations de la notice

1259

Téléchargements de fichiers

238