We present Ω(n) lower bounds on the worst case time to perform a single instance of an
operation in any nonblocking implementation of a large class of concurrent data structures …

The k-set agreement problem is a generalization of the consensus problem. Namely,
assuming that each process proposes a value, every non-faulty process must decide one of …

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 …

In an asynchronous distributed system where any number of processes may crash, a
process may have to run solo, computing its local output without receiving any information …

Most concurrent data structures being designed today are versions of known sequential data
structures. However, in various cases it makes sense to relax the semantics of traditional …

Herlihy and Wing [11] established that the set of possible outcomes of a shared memory
distributed algorithm remains unchanged when atomic objects are replaced by their …

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 …

The notion of a universal construction is central in computing science: the wheel has not to
be reinvented for each new problem. In the context of n-process asynchronous distributed …

A notion of a universal construction suited to distributed computing has been introduced by
Herlihy in his celebrated paper “Wait-free synchronization”(ACM Trans Program Lang Syst …

In this work, we consider the following random process, motivated by the analysis of lock-
free concurrent algorithms under high memory contention. In each round, a new scheduling …