Document Open Access Logo

Brief Announcement: Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit

Authors Hagit Attiya , Jennifer L. Welch

PDF
Thumbnail PDF

File

LIPIcs.DISC.2023.36.pdf
  • Filesize: 0.67 MB
  • 7 pages

Document Identifiers

Author Details

Hagit Attiya
  • Department of Computer Science, Technion, Haifa, Israel
Jennifer L. Welch
  • Department of Computer Science and Engineering, Texas A&M University, College Station, TX, USA

Funding

  • Attiya, Hagit: partially supported by the Israel Science Foundation (grants 380/18 and 22/1425).

Cite As Get BibTex

Hagit Attiya and Jennifer L. Welch. Brief Announcement: Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 36:1-36:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.DISC.2023.36

Abstract

Algorithms to solve fault-tolerant consensus in asynchronous systems often rely on primitives such as crusader agreement, adopt-commit, and graded broadcast, which provide weaker agreement properties than consensus. Although these primitives have a similar flavor, they have been defined and implemented separately in ad hoc ways. We propose a new problem called connected consensus that has as special cases crusader agreement, adopt-commit, and graded broadcast, and generalizes them to handle multi-valued (non-binary) inputs. The generalization is accomplished by relating the problem to approximate agreement on graphs.
We present three algorithms for multi-valued connected consensus in asynchronous message-passing systems, one tolerating crash failures and two tolerating malicious (unauthenticated Byzantine) failures. We extend the definition of binding, a desirable property recently identified as supporting binary consensus algorithms that are correct against adaptive adversaries, to the multi-valued input case and show that all our algorithms satisfy the property. Our crash-resilient algorithm has failure-resilience and time complexity that we show are optimal. When restricted to the case of binary inputs, the algorithm has improved time complexity over prior algorithms. Our two algorithms for malicious failures trade off failure resilience and time complexity. The first algorithm has time complexity that we prove is optimal but worse failure-resilience, while the second has failure-resilience that we prove is optimal but worse time complexity. When restricted to the case of binary inputs, the time complexity (as well as resilience) of the second algorithm matches that of prior algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • graded broadcast
  • gradecast
  • binding
  • approximate agreement

Metrics

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

Related Versions

References

  1. Ittai Abraham, Naama Ben-David, and Sravya Yandamuri. Efficient and adaptively secure asynchronous binary agreement via binding crusader agreement. In 41st ACM Symposium on Principles of Distributed Computing, pages 381-391, 2022. Google Scholar
  2. Yehuda Afek, James Aspnes, Edo Cohen, and Danny Vainstein. Brief announcement: Object oriented consensus. In 36th ACM Symposium on Principles of Distributed Computing, pages 367-369, 2017. Full version in https://www.cs.yale.edu/homes/aspnes/papers/vac-abstract.html. Google Scholar
  3. Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. McGraw-Hill Publishing Company, 1st edition, 1998. Google Scholar
  4. Zohir Bouzid, Achour Mostefaoui, and Michel Raynal. Minimal synchrony for Byzantine consensus. In 34th ACM Symposium on Principles of Distributed Computing, pages 461-470, 2015. Google Scholar
  5. Armando Castañeda, Sergio Rajsbaum, and Matthieu Roy. Convergence and covering on graphs for wait-free robots. Journal of the Brazilian Computer Society, 24:1-15, 2018. Google Scholar
  6. Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. J. ACM, 43(2):225-267, 1996. Google Scholar
  7. Giovanni Deligios, Martin Hirt, and Chen-Da Liu-Zhang. Round-efficient Byzantine agreement and multi-party computation with asynchronous fallback. In 19th International Conference on Theory of Cryptography, TCC, pages 623-653, 2021. Google Scholar
  8. Carole Delporte-Gallet, Hugues Fauconnier, and Michel Raynal. On the weakest information on failures to solve mutual exclusion and consensus in asynchronous crash-prone read/write systems. Journal of Parallel and Distributed Computing, 153:110-118, 2021. Google Scholar
  9. Danny Dolev. The Byzantine generals strike again. Journal of Algorithms, 3(1):14-30, 1982. Google Scholar
  10. Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. J. ACM, 33(3):499-516, 1986. Google Scholar
  11. Alan David Fekete. Asymptotically optimal algorithms for approximate agreement. Distributed Computing, 4:9-29, 1990. Google Scholar
  12. Paul Feldman and Silvio Micali. Optimal algorithms for Byzantine agreement. In 12th Annual ACM Symposium on Theory of Computing, pages 148-161, 1988. Google Scholar
  13. Pesech Feldman and Silvio Micali. An optimal probabilistic protocol for synchronous Byzantine agreement. SIAM J. Comput., 26(4):873-933, 1997. Google Scholar
  14. Eli Gafni. Round-by-round fault detectors: unifying synchrony and asynchrony. In 17th ACM Symposium on Principles of Distributed Computing, pages 143-152, 1998. Google Scholar
  15. Manfred Koebe. On a new class of intersection graphs. In Annals of Discrete Mathematics, volume 51, pages 141-143. Elsevier, 1992. Google Scholar
  16. Stephen R Mahaney and Fred B Schneider. Inexact agreement: Accuracy, precision, and graceful degradation. In 4th ACM Symposium on Principles of Distributed Computing, pages 237-249, 1985. Google Scholar
  17. Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. Signature-free asynchronous binary Byzantine consensus with t < n/3, O(n²) messages, and O(1) expected time. J. ACM, 62(4):31:1-31:21, 2015. Google Scholar
  18. Achour Mostéfaoui and Michel Raynal. Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with t < n/3, O(n²) messages, and constant time. Acta Informatica, 54(5):501-520, 2017. Google Scholar
  19. Thomas Nowak and Joel Rybicki. Byzantine approximate agreement on graphs. In 33rd International Symposium on Distributed Computing, pages 29:1-29:17, 2019. Google Scholar
  20. Sam Toueg. Randomized Byzantine agreements. In 3rd ACM Symposium on Principles of Distributed Computing, pages 163-178, 1984. Google Scholar
  21. Jiong Yang, Gil Neiger, and Eli Gafni. Structured derivations of consensus algorithms for failure detectors. In 17th ACM Symposium on Principles of Distributed Computing, pages 297-306, 1998. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact