Document Open Access Logo

Which Broadcast Abstraction Captures k-Set Agreement?

Authors Damien Imbs, Achour Mostéfaoui, Matthieu Perrin, Michel Raynal

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.27.pdf
  • Filesize: 0.59 MB
  • 16 pages

Document Identifiers

Author Details

Damien Imbs
Achour Mostéfaoui
Matthieu Perrin
Michel Raynal

Cite As Get BibTex

Damien Imbs, Achour Mostéfaoui, Matthieu Perrin, and Michel Raynal. Which Broadcast Abstraction Captures k-Set Agreement?. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.27

Abstract

It is well-known that consensus (one-set agreement) and total order broadcast are equivalent in asynchronous systems prone to process crash failures. Considering wait-free systems, this article addresses and answers the following question: which is the communication abstraction that "captures" k-set agreement? To this end, it introduces a new broadcast communication abstraction, called k-BO-Broadcast, which restricts the disagreement on the local deliveries of the messages that have been broadcast (1-BO-Broadcast boils down to total order broadcast). Hence, in this context, k=1 is not a special number, but only the first integer in an increasing integer sequence.

This establishes a new "correspondence" between distributed agreement problems and communication abstractions, which enriches our understanding of the relations linking fundamental issues of fault-tolerant distributed computing.

Subject Classification

Keywords
  • Agreement problem
  • Antichain
  • Asynchronous system
  • Communication abstraction
  • Consensus
  • Message-passing system
  • Partially ordered set
  • Process crash

Metrics

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

References

  1. Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. J. ACM, 40(4):873-890, 1993. Google Scholar
  2. James H. Anderson. Multi-writer composite registers. Distributed Computing, 7(4):175-195, 1994. Google Scholar
  3. Hagit Attiya and Jennifer L. Welch. Distributed computing: fundamentals, simulations and advanced topics. Wiley-Interscience, 2004. Google Scholar
  4. Kenneth P. Birman and Thomas A. Joseph. Reliable communication in the presence of failures. ACM Trans. Comput. Syst., 5(1):47-76, 1987. Google Scholar
  5. François Bonnet and Michel Raynal. A simple proof of the necessity of the failure detector sigma to implement an atomic register in asynchronous message-passing systems. Inf. Process. Lett., 110(4):153-157, 2010. 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. Soma Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Inf. Comput., 105(1):132-158, 1993. Google Scholar
  8. Carole Delporte-Gallet, Hugues Fauconnier, and Rachid Guerraoui. Tight failure detection bounds on atomic object implementations. J. ACM, 57(4):22:1-22:32, 2010. Google Scholar
  9. Faith Ellen. How hard is it to take a snapshot? In SOFSEM 2005: Theory and Practice of Computer Science, 31st Conference on Current Trends in Theory and Practice of Computer Science, Liptovský Ján, Slovakia, January 22-28, 2005, Proceedings, pages 28-37, 2005. Google Scholar
  10. Michael J. Fischer and Michael Merritt. Appraising two decades of distributed computing theory research. Distributed Computing, 16(2-3):239-247, 2003. Google Scholar
  11. Damien Imbs, Achour Mostéfaoui, Matthieu Perrin, and Michel Raynal. Set-constrained delivery broadcast: Definition, abstraction power, and computability limits. CoRR, abs/1706.05267, 2017. URL: http://arxiv.org/abs/1706.05267.
  12. Damien Imbs, Achour Mostéfaoui, Matthieu Perrin, and Michel Raynal. Which broadcast abstraction captures dollarkdollar-set agreement? CoRR, abs/1705.04835, 2017. URL: http://arxiv.org/abs/1705.04835.
  13. Damien Imbs and Michel Raynal. Help when needed, but no more: Efficient read/write partial snapshot. J. Parallel Distrib. Comput., 72(1):1-12, 2012. Google Scholar
  14. Michiko Inoue, Toshimitsu Masuzawa, Wei Chen, and Nobuki Tokura. Linear-time snapshot using multi-writer multi-reader registers. In Distributed Algorithms: 8th International Workshop, WDAG '1994 Terschelling, The Netherlands, September 29 - October 1, 1994 Proceedings, pages 130-140. Springer Berlin Heidelberg, 1994. Google Scholar
  15. Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996. Google Scholar
  16. Michel Raynal. Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2010. Google Scholar
  17. Michel Raynal. Distributed Algorithms for Message-Passing Systems. Springer, 2013. Google Scholar
  18. Michel Raynal. Set agreement. In Encyclopedia of Algorithms, pages 1956-1959. 2016. Google Scholar
  19. Michel Raynal, André Schiper, and Sam Toueg. The causal ordering abstraction and a simple way to implement it. Inf. Process. Lett., 39(6):343-350, 1991. 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