Document Open Access Logo

k-Set Agreement in Communication Networks with Omission Faults

Authors Emmanuel Godard, Eloi Perdereau

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.8.pdf
  • Filesize: 0.56 MB
  • 17 pages

Document Identifiers

Author Details

Emmanuel Godard
Eloi Perdereau

Cite As Get BibTex

Emmanuel Godard and Eloi Perdereau. k-Set Agreement in Communication Networks with Omission Faults. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.OPODIS.2016.8

Abstract

We consider an arbitrary communication network G where at most f messages can be lost at each round, and consider the classical k-set agreement problem in this setting. We characterize exactly for which f the k-set agreement problem can be solved on G.

The case with k = 1, that is the Consensus problem, has first been introduced by Santoro and Widmayer in 1989, the characterization is already known from [Coulouma/Godard/Peters, TCS, 2015]. As a first contribution, we present a detailed and complete characterization for the 2-set problem. The proof of the impossibility result uses topological methods. We introduce a new subdivision approach for these topological methods that is of independent interest.

In the second part, we show how to extend to the general case with k in N. This characterization is the first complete characterization for this kind of synchronous message passing model, a model that is a subclass of the family of oblivious message adversaries.

Subject Classification

Keywords
  • k-set agreement
  • message passing
  • dynamic networks
  • message adversary
  • omission faults

Metrics

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

References

  1. Yehuda Afek and Eli Gafni. Asynchrony from Synchrony, pages 225-239. Number 7730 in Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2013. Google Scholar
  2. Martin Biely, Peter Robinson, and Ulrich Schmid. Easy impossibility proofs for k-set agreement in message passing systems. In OPODIS, volume 7109 of Lecture Notes in Computer Science, pages 299-312. Springer, 2011. Google Scholar
  3. Martin Biely, Peter Robinson, Ulrich Schmid, Manfred Schwarz, and Kyrill Winkler. Gracefully degrading consensus and k-set agreement in directed dynamic networks. In Ahmed Bouajjani and Hugues Fauconnier, editors, Networked Systems - Third International Conference, NETYS 2015, Agadir, Morocco, May 13-15, 2015, Revised Selected Papers, volume 9466 of Lecture Notes in Computer Science, pages 109-124. Springer, 2015. Google Scholar
  4. Martin Biely, Peter Robinson, Ulrich Schmid, Manfred Schwarz, and Kyrill Winkler. Gracefully degrading consensus and k-set agreement in directed dynamic networks, 2016. submitted. Google Scholar
  5. E. Borowsky and E. Gafni. Immediate atomic snapshots and fast renaming. In Proc. of the 12th Annual ACM Symposium on Principles of Distributed Computing, 1993. Google Scholar
  6. Elizabeth Borowsky and Eli Gafni. Generalized flp impossibility result for t-resilient asynchronous computations. In STOC'93: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 91-100, New York, NY, USA, 1993. ACM Press. URL: http://dx.doi.org/10.1145/167088.167119.
  7. Elizabeth Borowsky and Eli Gafni. A simple algorithmically reasoned characterization of wait-free computation (extended abstract). In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, PODC'97, pages 189-198. ACM, 1997. URL: http://dx.doi.org/10.1145/259380.259439.
  8. Bernadette Charron-Bost and André Schiper. The heard-of model: computing in distributed systems with benign faults. Distributed Computing, 22(1):49-71, 2009. URL: http://dx.doi.org/10.1007/s00446-009-0084-6.
  9. S. Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation, 105(1):132–158, Jul 1993. Google Scholar
  10. Étienne Coulouma, Emmanuel Godard, and Joseph G. Peters. A characterization of oblivious message adversaries for which consensus is solvable. Theor. Comput. Sci., 584:80-90, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.01.024.
  11. Eli Gafni and Petr Kuznetsov. The weakest failure detector for solving k-set agreement. In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, PODC'09, pages 83-91, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1582716.1582735.
  12. Rachid Guerraoui, Petr Kouznetsov, and Bastian Pochon. A note on set agreement with omission failures. Electr. Notes Theor. Comput. Sci., 81, 2003. Google Scholar
  13. Maurice Herlihy, Dmitry N. Kozlov, and Sergio Rajsbaum. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, 1 edition edition, 2013. Google Scholar
  14. Maurice Herlihy, Sergio Rajsbaum, and Michel Raynal. Computability in distributed computing: A tutorial. SIGACT News, 43(3):88-110, 2012. Google Scholar
  15. Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. J. ACM, 46(6):858-923, 1999. Google Scholar
  16. Dmitry N. Kozlov. Chromatic subdivision of a simplicial complex. Homology Homotopy Appl., 14(2):197-209, 2012. URL: http://projecteuclid.org/euclid.hha/1355321488.
  17. Michel Raynal. Set Agreement, pages 1956-1959. Springer New York, New York, NY, 2016. URL: http://dx.doi.org/10.1007/978-1-4939-2864-4_367.
  18. Michel Raynal and Julien Stainer. Synchrony weakened by message adversaries vs asynchrony restricted by failure detectors. In Panagiota Fatourou and Gadi Taubenfeld, editors, PODC, pages 166-175. ACM, 2013. Google Scholar
  19. M. Saks and F. Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. on Computing, 29:1449-1483, 2000. Google Scholar
  20. Nicola Santoro and Peter Widmayer. Time is not a healer. In STACS, pages 304-313, 1989. Google Scholar
  21. Nicola Santoro and Peter Widmayer. Agreement in synchronous networks with ubiquitous faults. Theor. Comput. Sci., 384(2-3):232-249, 2007. 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