Ph.D Thesis

Ph.D StudentFouren Arie
SubjectAdaptive Wait-Free Algorithms for Asynchronous Shared-
Memory Systems
DepartmentDepartment of Computer Science
Supervisor PROF. Hagit Attiya


An {\em asynchronous shared-memory system} consists
of a set of $n$ processes with distinct names
in the range $\{0,\ldots, N-1\}$, $N\geq n$,
communicating by reading and writing to the shared memory.
Processes do not have access to global or local clocks of any kind,
and there are no bounds on the variation of speed among the processes;
any number of processes may crash.
{\em Wait-free} algorithms guarantee that a
non-faulty process successfully completes its computation in a finite
number of steps, regardless of the behavior of other processes.

The step complexity (i.e., the maximal number
of shared memory operations performed by
a process) of many existing wait-free algorithms
depends on the range of the initial names of the processes, $N$.
In real distributed systems $N$ may be very large,
while often only a small number of
processes participate in the computation.
Therefore, it is desirable to have algorithms whose step complexity
does not depend on the system's scale,
but adapts to the degree of contention in each specific execution.

An algorithm is adaptive to {\em point contention}, if its step complexity
depends only on the maximal number of processes
active {\em simultaneously} at some point during the execution.
The step complexity of algorithms adaptive to
{\em total contention} depends on the {\em total} number of processes
active during the execution.
(Clearly, adaptiveness to point contention implies
adaptiveness to total contention, but not vise versa).

This work presents adaptive algorithms for
well-known problems, such as renaming, lattice agreement,
atomic and immediate snapshots and timestamps.
It also introduces a set of tools and techniques
which allow to construct adaptive algorithms in a modular manner,
to prove their correctness, to analyze their step complexity
and to transform existing non-adaptive algorithms into adaptive ones.
In addition, it improves the step complexity of non-adaptive algorithms
for one-shot and long-lived renaming and atomic snapshots.