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.