Skip to Main content Skip to Navigation
Reports

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
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
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.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/inria-00521646
Contributor : Ist Rennes <>
Submitted on : Tuesday, September 28, 2010 - 12:01:25 PM
Last modification on : Tuesday, June 15, 2021 - 4:15:03 PM
Long-term archiving on: : Wednesday, December 29, 2010 - 2:43:13 AM

File

PI-1954.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

587

Files downloads

320