Long-lived and adaptive atomic snapshot and immediate snapshot (extended abstract)

Abstract

Long-lived and adaptive to point contention implementations of snapshot and immediate snapshot objects in the read/write shared-memory model are presented. In [2] we presented adaptive algorithms for mutual exclusion, collect and snapshot. However, the collect and snapshot algorithms were adaptive only when the number of local primitive operations that a process performs are ignored, i.e., not counted. The number of primitive local steps (operations that do not access the shared memory) in the collect and snapshot operations presented in [2] is O(Nk3) and O(Nk4) respectively where N is the total number of processes in the system and k is the encountered contention. Here we developed new techniques that enabled us to achieve fully adaptive implementations in which the step complexity (combined local and shared) of any operation is bounded by a function of the number of processes that are concurrent with the operation, in particular, O(k4) for the snapshot implementation.