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 :
Rapport
[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

https://hal.inria.fr/inria-00521646
Contributeur : Ist Rennes <>
Soumis le : mardi 28 septembre 2010 - 12:01:25
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : mercredi 29 décembre 2010 - 02:43:13

Fichier

PI-1954.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00521646, version 1

Citation

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〉

Partager

Métriques

Consultations de la notice

381

Téléchargements de fichiers

229