Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Tuesday, September 28, 2010 - 12:01:25 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:28 AM
Long-term archiving on: : Wednesday, December 29, 2010 - 2:43:13 AM


Files produced by the author(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⟩



Record views


Files downloads