Publication

On the Validity of Consensus

Rachid Guerraoui, Jovan Komatovic, Manuel José Ribeiro Vidigueira, Pierre Philippe Civit, Seth Gilbert
2023
Conference Papers

Abstract

The Byzantine consensus problem involves.. processes, out of which t < n could be faulty and behave arbitrarily. Three properties characterize consensus: (1) termination, requiring correct (nonfaulty) processes to eventually reach a decision, (2) agreement, preventing them from deciding different values, and (3) validity, precluding "unreasonable" decisions. But, what is a reasonable decision? Strong validity, a classical property, stipulates that, if all correct processes propose the same value, only that value can be decided. Weak validity, another established property, stipulates that, if all processes are correct and they propose the same value, that value must be decided. The space of possible validity properties is vast. Yet, their impact on consensus algorithms remains unclear.|This paper addresses the question of which validity properties allow Byzantine consensus to be solvable in a general partially synchronous model, and at what cost. First, we determine the necessary and sufficient conditions for a validity property to make the consensus problem solvable; we say that such validity properties are solvable. Notably, we prove that, if n

Official source

Rachid Guerraoui, Jovan Komatovic, Manuel José Ribeiro Vidigueira, Pierre Philippe Civit, Seth Gilbert
2023
Conference Papers

Abstract

Official source

Related concepts (23)

Validity (statistics)

Validity is the main extent to which a concept, conclusion or measurement is well-founded and likely corresponds accurately to the real world. The word "valid" is derived from the Latin validus, meaning strong. The validity of a measurement tool (for example, a test in education) is the degree to which the tool measures what it claims to measure. Validity is based on the strength of a collection of different types of evidence (e.g. face validity, construct validity, etc.) described in greater detail below.

Consensus (computer science)

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts.

Internal validity

Internal validity is the extent to which a piece of evidence supports a claim about cause and effect, within the context of a particular study. It is one of the most important properties of scientific studies and is an important concept in reasoning about evidence more generally. Internal validity is determined by how well a study can rule out alternative explanations for its findings (usually, sources of systematic error or 'bias').

Related publications (29)

Planetary-Scale Byzantine Fault Tolerance

Matteo Monti

The scale and pervasiveness of the Internet make it a pillar of planetary communication, industry and economy, as well as a fundamental medium for public discourse and democratic engagement. In stark contrast with the Internet's decentralized infrastructur ...

EPFL2024

Contextual Stochastic Bilevel Optimization

Daniel Kuhn, Yifan Hu, Andreas Krause, Jie Wang

We introduce contextual stochastic bilevel optimization (CSBO) -- a stochastic bilevel optimization framework with the lower-level problem minimizing an expectation conditioned on some contextual information and the upper-level decision variable. This fram ...

2023

Vertical and Leg Stiffness Modeling During Running: Effect of Speed and Incline

Kamiar Aminian, Frédéric Meyer, Grégoire Millet, Mathieu Pascal Falbriard

A spring mass model is often used to describe human running, allowing to understand the concept of elastic energy storage and restitution. The stiffness of the spring is a key parameter and different methods have been developed to estimate both the vertica ...

GEORG THIEME VERLAG KG2023