License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.56
URN: urn:nbn:de:0030-drops-80108
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8010/
Go to the corresponding LIPIcs Volume Portal

Kuznetsov, Petr ; Rieutord, Thibault ; He, Yuan

Brief Announcement: Compact Topology of Shared-Memory Adversaries

pdf-format:
LIPIcs-DISC-2017-56.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{kuznetsov_et_al:LIPIcs:2017:8010,
  author =	{Petr Kuznetsov and Thibault Rieutord and Yuan He},
  title =	{{Brief Announcement: Compact Topology of Shared-Memory Adversaries}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{56:1--56:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8010},
  URN =		{urn:nbn:de:0030-drops-80108},
  doi =		{10.4230/LIPIcs.DISC.2017.56},
  annote =	{Keywords: Adversarial models, Affine tasks, Topological characterization}
}

Keywords: Adversarial models, Affine tasks, Topological characterization
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI