In this paper we prove: For any constant d there is a large enough n such that there is no long-lived adaptive implementation of collect or renaming in the read write model with n processes that uses d or less MWMR registers.

Long-lived and adaptive to point contention implementations of snapshot and immediate snapshot objects in the read/write shared-memory model are presented. In [2] we presented adaptive algorithms for mutual exclusion, collect and snapshot. However, the collect and snapshot algorithms were adaptive only when the number of local primitive operations that a process performs are ignored, i.e., not counted. The number of primitive local steps (operations that do not access the shared memory) in the collect and snapshot operations presented in [2] is O(Nk3) and O(Nk4) respectively where N is the total number of processes in the system and k is the encountered contention. Here we developed new techniques that enabled us to achieve fully adaptive implementations in which the step complexity (combined local and shared) of any operation is bounded by a function of the number of processes that are concurrent with the operation, in particular, O(k4) for the snapshot implementation.

A distributed algorithm is adaptive if the worst case step complexity of its operations is bounded by a function of the number of processes that are concurrently active during the operation (rather than a function of N, the total number of processes, which is usually much larger). We present long-lived and adaptive algorithms for collect in the read/write shared-memory model. Replacing the reads and writes in long-lived shared memory algorithms with our adaptive collect results in many cases in a corresponding long-lived algorithm which is adaptive. Examples of such applications, which are discussed are atomic-snapshots, and l-exclusion. Following the long-lived and adaptive collect we present a more pragmatic version of collect, called active set. This algorithm is slightly weaker than the collect but has several advantages. We employ this algorithm to transform algorithms, such as the Bakery algorithm, into their corresponding adaptive long-lived version, which is more efficient than the version that was obtained with the collect. Previously, long-lived and adaptive algorithms in this model were presented only for the renaming problem.

We consider the problem of implementing atomic operations on multiple shared memory objects, in systems which directly support only single-object atomic operations.Our motivation is to design algorithms that exhibit both low contention between concurrent operations and a high level of concurrency, by disentangling long chains of conflicting operations.That is, operations that access widely disjoint parts of a data structure, or are widely separated in time, should not interfere with each other.The algorithm reported here extends and is based on the work of Attiya and Dagan [A D96], where a nonblocking solution is presented for two-object atomic operations.For any number, k, we present a wait-free solution for atomically accessing up to k objects.Notions of local contention and local step complexity are defined, and it is shown that the solution has low local contention and local step complexity.Relations between multi-objects and the familiar resource allocation problem are explored-the algorithm presented also provides a solution to the resource allocation problem. Int roduct ionConsider a data structure stored in shared memory and accessed concurrently by n processes.The shared data structure is abstracted w an array of memory locations.To perform its operation, a process needs to get exclusive access to the set of locations necessary to carry out qComputer

Counting networks are a class of concurrent structures that allow the design of highly scalable concurrent data structures in a way that eliminates sequential bottlenecks and contention.Linearizable counting networks assure that the order of the values returned by the network reflects the real-time order in which they were requested.We argue that in many concurrent systems the worst case scenarios that violate linearizability require a form of timing anomaly that is uncommon in practice.The linear time cost of designing networks that achieve linearizability under all circumstances may thus prove an unnecessary burden on applications that are willing to trade-off occasional non-linearizability for speed and parallelism.This paper presents a very simple measure that is iocal to the individual links and nodes of the network, and that quantifies the extent to which a network can suffer from timing anomalies and still remain linearizable.Perhaps counter-intuitively, this measure is independent of network depth.We use our measure to mathematically support our experiment al results: that in a variety of normal situations tested on a simulated shared memory multiprocessor, the Monic counting networks of Aspnes, Herlihy, and Shavit are "for all practical purposes" Iinearizable.

As we learn from the literature, flexibility in choosing syn-chroni~ation operations greatly simplifies the task of de-

Shared pools and stacks are two coordination structures with a history of applications ranging from simple producer/consumer buffers to job-schedulers and procedure stacks.This paper introduces elimination trees, a novel form of diffracting trees that offer pool and stack implementations with superior response (on average constant) under high loads, while guaranteeing logarithmic time "deterministic" termination under sparse request patterns.

An implementationof an asynchronous shared-data structure is wait-free if no adversarial scheduler can stop an individual operation on the data structure from making progress (that is the implementation can tolerate a fail-stop fault of any number of processes).An implementation is non-blocking if an adversarial scheduler cannot stop the system from making progress.of the Assoc!abon of Computing Machinery.o cop otherwse, or to repubhsh, requires y '/' a fee ancf/or soecl IC oermisslon.STOC' 95, L& Veg&, Nevada, USA @ 1995 ACM 0-89791 -718-9/95/0005..$3.50 places the O(n) term of wait-free implementations with an O(k) term (or O(k~log f)).