M.Sc Thesis | |

M.Sc Student | Zach Idan |
---|---|

Subject | Fully Adaptive Shared Memory Algorithms |

Department | Department of Computer Science |

Supervisor | PROF. Hagit Attiya |

The
step complexity of *fully adaptive* (FA) algorithms depends only on the
contention during an operation, when counting both *local computation* and
accesses to shared registers. This thesis contributes to the design of
efficient fully adaptive algorithms by specifying and implementing two generic
objects, *gather&f* and *collect&f*. Both objects are based
on a new adaptive safe agreement object that returns a unique, non-empty subset
of values proposed by processes accessing it concurrently.

A
gather&f object returns the value of applying a function *f* on the information
previously stored in the object. In order to reduce the local step complexity,
our implementation of gather&f calculates *f* *incrementally*, as
values are stored in the object. This implementation uses only read and write
operations on the shared memory. It has *O(k)* local and shared step
complexity for calculating *f *and *O(k ^{2})* for storing
information, where

A
collect&f object further guarantees that the value of *f* returned by
a collect&f operation does not reflect fewer store operations than a
(strictly) earlier collect&f operation. A simple implementation has *O(k ^{2})*
local and shared step complexity for calculating

To
demonstrate the applicability of gather&f and ecollect&f, we use them
to significantly reduce the local and shared step complexity of atomic snapshot
and immediate snapshot to *O(k ^{2})* and