文章基本信息

标题：Relaxed Queues and Stacks from Read/Write Operations
本地全文：下载
作者：Armando Casta{~n}eda ; Sergio Rajsbaum ; Michel Raynal 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：184
页码：13:1-13:19
DOI：10.4230/LIPIcs.OPODIS.2020.13
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Considering asynchronous shared memory systems in which any number of processes may crash, this work identifies and formally defines relaxations of queues and stacks that can be non-blocking or wait-free while being implemented using only read/write operations. Set-linearizability and Interval-linearizability are used to specify the relaxations formally, and precisely identify the subset of executions which preserve the original sequential behavior. The relaxations allow for an item to be returned more than once by different operations, but only in case of concurrency; we call such a property multiplicity. The stack implementation is wait-free, while the queue implementation is non-blocking. Interval-linearizability is used to describe a queue with multiplicity, with the additional relaxation that a dequeue operation can return weak-empty, which means that the queue might be empty. We present a read/write wait-free interval-linearizable algorithm of a concurrent queue. As far as we know, this work is the first that provides formalizations of the notions of multiplicity and weak-emptiness, which can be implemented on top of read/write registers only.
关键词：Asynchrony; Correctness condition; Linearizability; Nonblocking; Process crash; Relaxed data type; Set-linearizability; Wait-freedom; Work-stealing