论文标题
关于2个过程仿射模型的可定性性
On Decidability of 2-process Affine Models
论文作者
论文摘要
计算的仿射模型被定义为迭代的即时触发器的子集，捕获了各种各样的共享内存系统，例如候补，t-弹药，k- c- c持续性和公平的共享 - 内存对手。通常，在给定仿射模型中是否可以解决特定任务的问题是不可决定的。在本文中，我们专注于针对两个过程系统定义的仿射模型。我们表明，2个过程的仿射模型的任务计算性是可决定的，并且介绍了2个过程仿射模型的五个等价类别的完整层次结构。
An affine model of computation is defined as a subset of iterated immediate-snapshot runs, capturing a wide variety of shared-memory systems, such as 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 the task computability of 2-process affine models is decidable and presents a complete hierarchy of the five equivalence classes of 2-process affine models.
