M.Sc Thesis

M.Sc StudentZach Idan
SubjectFully Adaptive Shared Memory Algorithms
DepartmentDepartment 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(k2) for storing information, where k is the point contention during the operation's execution interval.

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(k2) local and shared step complexity for calculating f and for storing information. For common applications where collect&f is repeatedly invoked, the thesis presents an efficient implementation called ecollect&f, in which storing information takes a single step and calculating f has O(k) local and shared step complexity.

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(k2) and O(k3), respectively.