Skip to Main content Skip to Navigation
Journal articles

Implementing Snapshot Objects on Top of Crash-Prone Asynchronous Message-Passing Systems

Carole Delporte-Gallet 1, 2 Hugues Fauconnier 1, 2 Sergio Rajsbaum 3, * Michel Raynal 4
* Corresponding author
2 GANG - Networks, Graphs and Algorithms
IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale, Inria de Paris
4 WIDE - the World Is Distributed Exploring the tension between scale and coordination
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : In asynchronous crash-prone read/write shared-memory systems there is the notion of a snapshot object, which simulates the behavior of an array of single-writer/multi-reader (SWMR) shared registers that can be read atomically. Processes in the system can access the object invoking (any number of times) two operations, denoted write() and snapshot(). A process invokes write() to update the value of its register in the array. When it invokes snapshot(), the process obtains the values of all registers, as if it read them simultaneously. It is known that a snapshot object can be implemented on top of SWMR registers, tolerating any number of process failures. Snapshot objects provide a level of abstraction higher than individual SWMR registers, and they simplify the design of applications. Building a snapshot object on an asynchronous crash-prone message-passing system has similar benefits. The object can be implemented by using the known simulations of a SWMR shared memory on top of an asynchronous message-passing system (if less than half the processes can crash), and then build a snapshot object on top of the simulated SWMR memory. This paper presents an algorithm that implements a snapshot object directly on top of the message-passing system, without building an intermediate layer of a SWMR shared memory. To the authors knowledge, the proposed algorithm is the first providing such a direct construction. The algorithm is more efficient than the indirect solution, yet relatively simple.
Document type :
Journal articles
Complete list of metadata
Contributor : Carole Delporte-Gallet Connect in order to contact the contributor
Submitted on : Friday, December 14, 2018 - 4:44:05 PM
Last modification on : Friday, January 21, 2022 - 3:19:54 AM

Links full text



Carole Delporte-Gallet, Hugues Fauconnier, Sergio Rajsbaum, Michel Raynal. Implementing Snapshot Objects on Top of Crash-Prone Asynchronous Message-Passing Systems. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2018, 29 (9), pp.2033-2045. ⟨10.1109/TPDS.2018.2809551⟩. ⟨hal-01955906⟩



Les métriques sont temporairement indisponibles