Set-Linearizable Implementations from Read/Write Operations: Sets, Fetch &Increment, Stacks and Queues with Multiplicity.

This work consideres asynchronous shared memory systems in which any number of processes may crash. It identifies relaxations of fetch & increment, queues, sets and stacks that can be non-blocking or wait-free implemented using only Read/Write operations, without Read-After-Write synchronization patterns. Set-linearizability, a generalization of linearizability designed to specify concurrent behaviors, is used to formally express these relaxations and precisely identify the subset of executions which preserve the original sequential behavior. The specifications allow for an item to be returned more than once by different operations, but only in case of concurrency; we call such a relaxation multiplicity. Hence, these definitions give rise to new notions and new objects where concurrency explicitly appears in the specification of the objects. As far as we know, this work is the first to provide relaxations of objects with consensus number two which can be implemented using only Read/Write registers. [ABSTRACT FROM AUTHOR]