2026-07-20T05:42:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8010 2024-03-06T10:41:44Z ddc:004 open_access

Brief Announcement: Compact Topology of Shared-Memory Adversaries Kuznetsov, Petr Rieutord, Thibault He, Yuan Adversarial models Affine tasks Topological characterization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petr Kuznetsov and Thibault Rieutord and Yuan He 2017 Is Part Of LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2017.56 urn:nbn:de:0030-drops-80108 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.56 eng https://creativecommons.org/licenses/by/3.0/legalcode