arXiv Open Access 2020

On Decidability of 2-process Affine Models

Petr Kuznetsov Thibault Rieutord

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DC

Penulis (2)

Petr Kuznetsov

Thibault Rieutord

Format Sitasi

APA MLA BibTeX

Kuznetsov, P., Rieutord, T. (2020). On Decidability of 2-process Affine Models. https://arxiv.org/abs/2008.02099

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2020
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓