A Necessary and Sufficient Synchrony Condition for Solving Byzantine Consensus

Olivier Baldellon 1 Achour Mostefaoui 1 Michel Raynal 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : Solving the consensus problem requires in one way or another that the underlying system satisfies synchrony assumptions. Considering a system of n processes where up to t < n/3 may commit Byzantine failures, this paper investigates the synchrony assumptions that are required to solve consensus. It presents a corresponding necessary and sufficient condition. Such a condition is formulated with the notions of a synchrony property and property ambiguity. A synchrony property is a set of graphs, where each graph corresponds to a set of eventually synchronous links among correct processes. Intuitively, a property is ambiguous if it contains a graph whose connected components are such that it is impossible to distinguish a connected component that contains correct processes only from a connected component that contains faulty processes only. The paper connects then the notion of a synchrony property with the notion of eventual bi-source, and shows that the existence of a virtual 3[t + 1]bi-source is a necessary and sufficient condition to solve consensus in presence of up to t Byzantine processes in systems with message authentication.
Type de document :
[Research Report] PI 1954, 2010, pp.8
Liste complète des métadonnées

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

Contributeur : Ist Rennes <>
Soumis le : mardi 28 septembre 2010 - 12:01:25
Dernière modification le : mercredi 28 février 2018 - 10:22:57
Document(s) archivé(s) le : mercredi 29 décembre 2010 - 02:43:13


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00521646, version 1



Olivier Baldellon, Achour Mostefaoui, Michel Raynal. A Necessary and Sufficient Synchrony Condition for Solving Byzantine Consensus. [Research Report] PI 1954, 2010, pp.8. 〈inria-00521646〉



Consultations de la notice


Téléchargements de fichiers