Ph.D Thesis | |

Ph.D Student | Fouren Arie |
---|---|

Subject | Adaptive Wait-Free Algorithms for Asynchronous Shared- Memory Systems |

Department | Department 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.