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

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 metadatas

https://hal.inria.fr/hal-01955906
Contributor : Carole Delporte-Gallet <>
Submitted on : Friday, December 14, 2018 - 4:44:05 PM
Last modification on : Friday, September 13, 2019 - 9:51:33 AM

Links full text

Identifiers

Citation

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⟩

Share

Metrics

Record views

236