Summary: ADAPTIVE AND EFFICIENT ALGORITHMS FOR LATTICE
AGREEMENT AND RENAMING \Lambda
HAGIT ATTIYA y AND ARIE FOUREN y
Abstract. In a sharedmemory system, n independent asynchronous processes, with distinct
names in the range f0; : : : ; N \Gamma 1g, communicate by reading and writing to shared registers. An
algorithm is waitfree if a process completes its execution regardless of the behavior of other processes.
This paper considers waitfree algorithms whose complexity adjusts to the level of contention in the
system: An algorithm is adaptive (to total contention) if its step complexity depends only on the
actual number of active processes, k; this number is unknown in advance and may change in different
executions of the algorithm.
Adaptive algorithms are presented for two important decision problems, lattice agreement and
(6k \Gamma 1)renaming; the step complexity of both algorithms is O(k log k). An interesting component
of the (6k \Gamma 1)renaming algorithm is an O(N) algorithm for (2k \Gamma 1)renaming; this improves on
the best previously known (2k \Gamma 1)renaming algorithm, which has O(Nnk) step complexity.
The efficient renaming algorithm can be modified into an O(N) implementation of atomic snap
shots using dynamic singlewriter multireader registers. The best known implementations of atomic
snapshots have step complexity O(N log N) using static singlewriter multireader registers, and
O(N) using multiwriter multireader registers.
Key words. sharedmemory systems, waitfree computation, atomic read/write registers, re
naming, lattice agreement, atomic snapshots