Document Open Access Logo

Brief Announcement: Compact Topology of Shared-Memory Adversaries

Authors Petr Kuznetsov, Thibault Rieutord, Yuan He

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.56.pdf
  • Filesize: 435 kB
  • 4 pages

Document Identifiers

Author Details

Petr Kuznetsov
Thibault Rieutord
Yuan He

Cite As Get BibTex

Petr Kuznetsov, Thibault Rieutord, and Yuan He. Brief Announcement: Compact Topology of Shared-Memory Adversaries. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 56:1-56:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.56

Abstract

The paper proposes a simple topological characterization of a large class of adversarial distributed-computing models via affine tasks: sub-complexes of the second iteration of the standard chromatic subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of the 2-round iterated immediate snapshot (IIS) model. Our results generalize and improve all previously derived topological characterizations of distributed-computing models.

Subject Classification

Keywords
  • Adversarial models
  • Affine tasks
  • Topological characterization

Metrics

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

References

  1. Bowen Alpern and Fred B. Schneider. Defining liveness. Information Processing Letters, 21(4):181-185, October 1985. Google Scholar
  2. Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Andreas Tielmann. The disagreement power of an adversary. Distributed Computing, 24(3-4):137-147, 2011. Google Scholar
  3. Eli Gafni. Private communication. 2002. Google Scholar
  4. Eli Gafni, Yuan He, Petr Kuznetsov, and Thibault Rieutord. Read-Write Memory and k-Set Consensus as an Affine Task. In OPODIS 2016, volume 70, pages 6:1-6:17, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.OPODIS.2016.6.
  5. Eli Gafni, Petr Kuznetsov, and Ciprian Manolescu. A generalized asynchronous computability theorem. In PODC, pages 222-231, 2014. URL: http://dx.doi.org/10.1145/2611462.2611477.
  6. Maurice Herlihy, Dmitry N. Kozlov, and Sergio Rajsbaum. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, 2014. Google Scholar
  7. Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. Journal of the ACM, 46(2):858-923, 1999. Google Scholar
  8. Petr Kuznetsov and Thibault Rieutord. Agreement functions for distributed computing models. In NETYS, pages 175-190, 2017. URL: http://dx.doi.org/10.1007/978-3-319-59647-1_14.
  9. Petr Kuznetsov, Thibault Rieutord, and Yuan He. Compact topology of shared-memory adversaries. HAL, https://hal.archives-ouvertes.fr/hal-01572257, 2017. Google Scholar
  10. Vikram Saraph, Maurice Herlihy, and Eli Gafni. Asynchronous computability theorems for t-resilient systems. In DISC, pages 428-441, 2016. 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