Long-Lived and Adaptive Atomic Snap-Shot and Immediate Snapshot

Yehuda Afek, Gideon Stupp, and Dan Touitou

To appear at Nineteenth Annual ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC 2000), Portland, Oregon, 16-19 July 2000


Abstract

Long-lived and adaptive implementations of a snapshot and immediate snapshot objects in the read/write shared-memory model are presented. In [ast99a] we have 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 [ast99a] is O(N k^3) and O(N k^4) 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 truly 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(k^4) for the snapshot (which is also a collect) implementation.