Self-Stabilizing Snapshot Objects for Asynchronous Failure-Prone Networked Systems

• This work provides the first self-stabilizing solution for the problem of constructing atomic snapshot objects, which can recover after the last occurrence of a transient fault (as well as node failures). • Our contribution is obtained via code transformation of earlier crash-tolerant algorithms for asynchronous message-passing systems prone to node failures. • This journal version extends our earlier conference papers by presenting the complete proofs for the proposed algorithms, and a completely new upper-bound on the operation completion time. A snapshot object simulates the behavior of an array of single-writer/multi-reader shared registers that can be read atomically. In 2018, Delporte-Gallet et al. proposed two fault-tolerant algorithms for snapshot objects in asynchronous crash-prone message-passing systems. Their first algorithm is non-blocking ; it allows snapshot operations to complete once all write operations have ceased. Their second algorithm allows snapshot operations to always terminate independently of write operations. The fault model of Delporte-Gallet et al. considers node failures (crashes). We aim at the design of even more robust snapshot objects. We do so through the lenses of self-stabilization —a very strong notion of fault-tolerance. In addition to Delporte-Gallet et al. ’s fault model, our self-stabilizing algorithms can recover after the occurrence of transient faults ; these faults represent arbitrary violations of the assumptions according to which the system was designed to operate (as long as the code stays intact). In particular, in this work, we propose self-stabilizing variations of Delporte-Gallet et al. ’s non-blocking algorithm and always-terminating algorithm. Our algorithms have similar communication costs to the ones by Delporte-Gallet et al. yet they eventually recover from the last occurrence of a transient fault. The main differences are that our proposal considers repeated gossiping of O ( ν ) bit messages, ν being the number of bits for encoding the object, and deals with bounded space (which is a prerequisite for self-stabilization). This facilitates recovery of the registers and sequence numbers after the occurrence of the last transient fault by guaranteeing consistency. We use Lamport’s happened-before relation to bound, when possible, the completion time of write and snapshot operations.