• Good-case Early-Stopping Laten...

Treffer: Good-case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case (Extended Version)

Title:
Good-case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case (Extended Version)
Authors:
Albouy, Timothé, Frey, Davide, Raynal, Michel, Taïani, François
Contributors:
the World Is Distributed Exploring the tension between scale and coordination (WIDE), Centre Inria de l'Université de Rennes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), ANR-20-CE25-0002,ByBloS,Au-delà des Blockchains : Modules de construction pour les applications à grande échelle zero-confiance multi-utilisateurs(2020), ANR-10-LABX-0007,COMIN Labs,Digital Communication and Information Sciences for the Future Internet(2010)
Publisher Information:
CCSD, 2023.
Publication Year:
2023
Collection:
collection:UNIV-RENNES1
collection:CNRS
collection:INRIA
collection:UNIV-UBS
collection:INSA-RENNES
collection:INRIA-RENNES
collection:IRISA
collection:IRISA_SET
collection:INRIA_TEST
collection:TESTALAIN1
collection:CENTRALESUPELEC
collection:INRIA2
collection:UR1-HAL
collection:UR1-MATH-STIC
collection:UR1-UFR-ISTIC
collection:TEST-UR-CSS
collection:UNIV-RENNES
collection:INRIA-RENGRE
collection:ANR
collection:UR1-MATH-NUM
collection:CYBERSCHOOL
Subject Terms:
Byzantine Fault, Deterministic Algorithm, Genericity, Good-Case Latency, Reliable Broadcast, Synchronous System, Weighted Predicate, [INFO.INFO-DC]Computer Science [cs], Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DS]Computer Science [cs], Data Structures and Algorithms [cs.DS]
Original Identifier:
ARXIV: 2303.05152
HAL: hal-04017887
Document Type:
E-Ressource preprint<br />Preprints<br />Working Papers
Language:
English
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/2303.05152
Access URL:
https://inria.hal.science/hal-04017887
https://inria.hal.science/hal-04017887v2/document
https://inria.hal.science/hal-04017887v2/file/main.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.hal.04017887v2
Database:
HAL

Weitere Informationen

This paper considers the good-case latency of Byzantine Reliable Broadcast (BRB), i.e., the time taken by correct processes to deliver a message when the initial sender is correct. This time plays a crucial role in the performance of practical distributed systems. Although significant strides have been made in recent years on this question, progress has mainly focused on either asynchronous or randomized algorithms. By contrast, the good-case latency of deterministic synchronous BRB under a majority of Byzantine faults has been little studied. In particular, it was not known whether a goodcase latency below the worst-case bound of t + 1 rounds could be obtained. This work answers this open question positively and proposes a deterministic synchronous Byzantine reliable broadcast that achieves a good-case latency of max(2, t + 3 − c) rounds, where t is the upper bound on the number of Byzantine processes and c the number of effectively correct processes.