Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults

Authors Ittai Abraham, Danny Dolev, Alon Kagan, Gilad Stern



PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.38.pdf
  • Filesize: 379 kB
  • 3 pages

Document Identifiers

Author Details

Ittai Abraham
  • VMware Research, Herzliya, Israel
Danny Dolev
  • The Hebrew University of Jerusalem, Israel
Alon Kagan
  • The Hebrew University of Jerusalem, Israel
Gilad Stern
  • The Hebrew University of Jerusalem, Israel

Cite AsGet BibTex

Ittai Abraham, Danny Dolev, Alon Kagan, and Gilad Stern. Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 38:1-38:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DISC.2022.38

Abstract

Protocols solving authenticated consensus in synchronous networks with Byzantine faults have been widely researched and known to exists if and only if n > 2f for f Byzantine faults. Similarly, protocols solving authenticated consensus in partially synchronous networks are known to exist if n > 3f+2k for f Byzantine faults and k crash faults. In this work we fill a natural gap in our knowledge by presenting MixSync, an authenticated consensus protocol in synchronous networks resilient to f Byzantine faults and k crash faults if n > 2f+k. As a basic building block, we first define and then construct a publicly verifiable crusader agreement protocol with the same resilience. The protocol uses a simple double-send round to guarantee non-equivocation, a technique later used in the MixSync protocol. We then discuss how to construct a state machine replication protocol using these ideas, and how they can be used in general to make such protocols resilient to crash faults. Finally, we prove lower bounds showing that n > 2f+k is optimally resilient for consensus and state machine replication protocols.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • consensus
  • state machine replication
  • mixed faults
  • synchrony
  • lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Juan Garay, Aggelos Kiayias, and Nikos Leonardos. The bitcoin backbone protocol: Analysis and applications. In Annual international conference on the theory and applications of cryptographic techniques, pages 281-310. Springer, 2015. Google Scholar
  2. Rafael Pass, Lior Seeman, and Abhi Shelat. Analysis of the blockchain protocol in asynchronous networks. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 643-673. Springer, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail