Minimal Synchrony for Asynchronous Byzantine Consensus

Zohir Bouzid 1 Achour Mostefaoui 2 Michel Raynal 1, 3
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
2 GDD - Gestion de Données Distribuées [Nantes]
LINA - Laboratoire d'Informatique de Nantes Atlantique
Abstract : Solving the consensus problem requires in one way or another that the underlying system satisfies some synchrony assumption. Considering an asynchronous message-passing system of n processes where (a) up to t < n/3 may commit Byzantine failures, and (b) each pair of processes is connected by two uni-directional channels (with possibly different timing properties), this paper investigates the synchrony assumption required to solve consensus, and presents a signature-free consensus algorithm whose synchrony requirement is the existence of a process that is an eventual t+1bisource. Such a process p is a correct process that eventually has (a) timely input channels from t correct processes and (b) timely output channels to t correct processes (these input and output channels can connect p to different subsets of processes). As this synchrony condition was shown to be necessary and sufficient in the stronger asynchronous system model (a) enriched with message authentication, and (b) where the channels are bidirectional and have the same timing properties in both directions, it follows that it is also necessary and sufficient in the weaker system model considered in the paper. In addition to the fact that it closes a long-lasting problem related to Byzantine agreement, a noteworthy feature of the proposed algorithm lies in its design simplicity, which is a first-class property.
Type de document :
Pré-publication, Document de travail
AP. 2015
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01103466
Contributeur : Michel Raynal <>
Soumis le : mercredi 14 janvier 2015 - 17:32:51
Dernière modification le : vendredi 16 novembre 2018 - 01:40:22
Document(s) archivé(s) le : mercredi 15 avril 2015 - 11:40:17

Fichiers

RR-2015-Min-Synchrony.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01103466, version 1

Citation

Zohir Bouzid, Achour Mostefaoui, Michel Raynal. Minimal Synchrony for Asynchronous Byzantine Consensus. AP. 2015. 〈hal-01103466〉

Partager

Métriques

Consultations de la notice

1498

Téléchargements de fichiers

366