## Efficient Fully Adaptive Snapshots using Incremental Calculation

### Authors

- Hagit Attiya, Technion
- Idan Zach, Technion

### Abstract

The step complexity of fully
adaptive algorithms depends only on the contention during an
operation, when counting both local computation and accesses to shared
registers. This paper significantly improves the local and shared
step complexity of atomic snapshot and immediate snapshot to $O(k^2)$
and $O(k^3)$, respectively, where $k$ is the point contention during
the operation's execution interval. These implementation uses only
read and write operations on the shared memory.
The fully adaptive algorithms employ a generic Gather&f object, which
returns the value of applying a function f on previously stored
information. It has $O(k)$ local and shared step complexity for
calculating $f$ and $O(k^2)$ for storing information.
A simple implementation of a Collect&f object has $O(k^2)$ local and
shared step complexity for storing information and for calculating f.
For common applications, the paper presents an efficient ECollect&f
implementation, where storing information takes a single step and
calculating f has $O(k)$ local and shared step complexity.