文章基本信息

标题：Brief Announcement: On Decidability of 2-Process Affine Models
本地全文：下载
作者：Petr Kuznetsov ; Thibault Rieutord
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：179
页码：1-3
DOI：10.4230/LIPIcs.DISC.2020.54
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Affine models of computation, defined as subsets of iterated immediate-snapshot runs, capture a wide variety of shared-memory systems: wait-freedom, t-resilience, k-concurrency, and fair shared-memory adversaries. The question of whether a given task is solvable in a given affine model is, in general, undecidable. In this paper, we focus on affine models defined for a system of two processes. We show that task computability of 2-process affine models is decidable and presents a complete hierarchy of five equivalence classes of 2-process affine models.
关键词：Affine tasks; Decidability