5 Search Results for "Xiang, Zhuolun"

Document
DOI: 10.4230/LIPIcs.OPODIS.2021.5
Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization

Authors: Ittai Abraham, Ling Ren, and Zhuolun Xiang

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
This paper studies the good-case latency of unauthenticated Byzantine fault-tolerant broadcast, which measures the time it takes for all non-faulty parties to commit given a non-faulty broadcaster. For both asynchrony and synchrony, we show that n ≥ 4f is the tight resilience threshold that separates good-case 2 rounds and 3 rounds. For asynchronous Byzantine reliable broadcast (BRB), we also investigate the bad-case latency for all non-faulty parties to commit when the broadcaster is faulty but some non-faulty party commits. We provide matching upper and lower bounds on the resilience threshold of bad-case latency for BRB protocols with optimal good-case latency of 2 rounds. In particular, we show 2 impossibility results and propose 4 asynchronous BRB protocols.
Cite as

Ittai Abraham, Ling Ren, and Zhuolun Xiang. Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2021.5,
  author =	{Abraham, Ittai and Ren, Ling and Xiang, Zhuolun},
  title =	{{Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.5},
  URN =		{urn:nbn:de:0030-drops-157806},
  doi =		{10.4230/LIPIcs.OPODIS.2021.5},
  annote =	{Keywords: Byzantine broadcast, asynchrony, synchrony, latency, good-case, optimal}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.32
Optimal Communication Complexity of Authenticated Byzantine Agreement

Authors: Atsuki Momose and Ling Ren

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Byzantine Agreement (BA) is one of the most fundamental problems in distributed computing, and its communication complexity is an important efficiency metric. It is well known that quadratic communication is necessary for BA in the worst case due to a lower bound by Dolev and Reischuk. This lower bound has been shown to be tight for the unauthenticated setting with f < n/3 by Berman et al. but a considerable gap remains for the authenticated setting with n/3 ≤ f < n/2. This paper provides two results towards closing this gap. Both protocols have a quadratic communication complexity and have different trade-offs in resilience and assumptions. The first protocol achieves the optimal resilience of f < n/2 but requires a trusted setup for threshold signature. The second protocol achieves near optimal resilience f ≤ (1/2 - ε)n in the standard PKI model.
Cite as

Atsuki Momose and Ling Ren. Optimal Communication Complexity of Authenticated Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{momose_et_al:LIPIcs.DISC.2021.32,
  author =	{Momose, Atsuki and Ren, Ling},
  title =	{{Optimal Communication Complexity of Authenticated Byzantine Agreement}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.32},
  URN =		{urn:nbn:de:0030-drops-148341},
  doi =		{10.4230/LIPIcs.DISC.2021.32},
  annote =	{Keywords: Byzantine Agreement, Communication Complexity, Lower Bound}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.28
Improved Extension Protocols for Byzantine Broadcast and Agreement

Authors: Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Byzantine broadcast (BB) and Byzantine agreement (BA) are two most fundamental problems and essential building blocks in distributed computing, and improving their efficiency is of interest to both theoreticians and practitioners. In this paper, we study extension protocols of BB and BA, i.e., protocols that solve BB/BA with long inputs of l bits using lower costs than l single-bit instances. We present new protocols with improved communication complexity in almost all settings: authenticated BA/BB with t < n/2, authenticated BB with t < (1-ε)n, unauthenticated BA/BB with t < n/3, and asynchronous reliable broadcast and BA with t < n/3. The new protocols are advantageous and significant in several aspects. First, they achieve the best-possible communication complexity of Θ(nl) for wider ranges of input sizes compared to prior results. Second, the authenticated extension protocols achieve optimal communication complexity given the current best available BB/BA protocols for short messages. Third, to the best of our knowledge, our asynchronous and authenticated protocols in the setting are the first extension protocols in that setting.
Cite as

Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang. Improved Extension Protocols for Byzantine Broadcast and Agreement. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nayak_et_al:LIPIcs.DISC.2020.28,
  author =	{Nayak, Kartik and Ren, Ling and Shi, Elaine and Vaidya, Nitin H. and Xiang, Zhuolun},
  title =	{{Improved Extension Protocols for Byzantine Broadcast and Agreement}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.28},
  URN =		{urn:nbn:de:0030-drops-131064},
  doi =		{10.4230/LIPIcs.DISC.2020.28},
  annote =	{Keywords: Byzantine agreement, Byzantine broadcast, extension protocol, communication complexity}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.47
Brief Announcement: Byzantine Agreement, Broadcast and State Machine Replication with Optimal Good-Case Latency

Authors: Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
This paper investigates the problem good-case latency of Byzantine agreement, broadcast and state machine replication in the synchronous authenticated setting. The good-case latency measure captures the time it takes to reach agreement when all non-faulty parties have the same input (or in BB/SMR when the sender/leader is non-faulty) and all messages arrive instantaneously. Previous result implies a lower bound showing that any Byzantine agreement or broadcast protocol tolerating more than n/3 faults must have a good-case latency of at least Δ. Our first result is a matching tight upper bound for a family of protocols we call 1Δ. We propose a protocol 1Δ-BA that solves Byzantine agreement in the synchronous and authenticated setting with optimal good-case latency of Δ and optimal resilience f < n/2. We then extend our protocol and present 1Δ-BB and 1Δ-SMR for Byzantine fault tolerant broadcast and state machine replication, respectively, in the same setting and with the same optimal good-case latency of Δ and f < n/2 fault tolerance.
Cite as

Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. Brief Announcement: Byzantine Agreement, Broadcast and State Machine Replication with Optimal Good-Case Latency. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 47:1-47:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2020.47,
  author =	{Abraham, Ittai and Nayak, Kartik and Ren, Ling and Xiang, Zhuolun},
  title =	{{Brief Announcement: Byzantine Agreement, Broadcast and State Machine Replication with Optimal Good-Case Latency}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{47:1--47:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.47},
  URN =		{urn:nbn:de:0030-drops-131259},
  doi =		{10.4230/LIPIcs.DISC.2020.47},
  annote =	{Keywords: Byzantine broadcast, synchrony, latency, state machine replication}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2016.26
Relaxed Byzantine Vector Consensus

Authors: Zhuolun Xiang and Nitin H. Vaidya

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

Abstract
Byzantine vector consensus requires that non-faulty processes reach agreement on adecision (or output) that is in the convex hull of the inputs at the non-faulty processes. Recent work has shown that, for n processes with up to f Byzantine failures, when the inputs are d-dimensional vectors of reals, n >= max (3f + 1, (d + 1)f + 1) is the tight bound for synchronous systems, and n >= (d + 2)f + 1 is tight for approximate consensus in asynchronous systems. Due to the dependence of the lower bound on vector dimension d, the number of processes necessary becomes large when the vector dimension is large. With the hope of reducing the lower bound on n, we propose relaxed versions of Byzantine vector consensus: k-relaxed Byzantine vector consensus and (delta, p)-relaxed Byzantine vector consensus. k-relaxed consensus only requires consensus for projections of inputs on every subset of k dimensions. (delta, p)-relaxed consensus requires that the output be within distance d of the convex hull of the non-faulty inputs, where distance is defined using the L_{p}-norm. An input-dependent delta allows the distance from the non-faulty convex hull to be dependent on the maximum distance between the non-faulty inputs. We show that for k-relaxed consensus with k > 1, and for (delta, p)-relaxed consensus with constant delta >= 0, the bound on n is identical to the bound stated above for the original vector consensus problem. On the other hand, when k = 1 or d depends on the inputs, we show that the bound on n is smaller when d >= 3. Input-dependent delta may be of interest in practice. In essence, input-dependent delta scales with the spread of the inputs.
Cite as

Zhuolun Xiang and Nitin H. Vaidya. Relaxed Byzantine Vector Consensus. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{xiang_et_al:LIPIcs.OPODIS.2016.26,
  author =	{Xiang, Zhuolun and Vaidya, Nitin H.},
  title =	{{Relaxed Byzantine Vector Consensus}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.26},
  URN =		{urn:nbn:de:0030-drops-70958},
  doi =		{10.4230/LIPIcs.OPODIS.2016.26},
  annote =	{Keywords: Byzantine consensus, vector inputs, relaxed validity conditions}
}
  • Refine by Author
  • 4 Ren, Ling
  • 4 Xiang, Zhuolun
  • 2 Abraham, Ittai
  • 2 Nayak, Kartik
  • 2 Vaidya, Nitin H.
  • Show More...

  • Refine by Classification
  • 3 Security and privacy → Distributed systems security
  • 2 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Communication complexity
  • 1 Theory of computation → Cryptographic protocols

  • Refine by Keyword
  • 3 Byzantine broadcast
  • 2 latency
  • 2 synchrony
  • 1 Byzantine Agreement
  • 1 Byzantine agreement
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2020
  • 1 2017
  • 1 2021
  • 1 2022

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact