Skip to Main content Skip to Navigation

Reliable Shared Memory Abstractions on Top of Asynchronous t-Resilient Byzantine Message-passing Systems

Abstract : This paper is on the construction and the use of a shared memory abstraction on top of an asynchronous message-passing system in which up to t processes may commit Byzantine failures. This abstraction consists of arrays of n single-writer/multi-reader atomic registers, where n is the number of processes. A distributed algorithm building such a shared memory abstraction it first presented. This algorithm assumes t < n/3, which is shown to be a necessary and sufficient condition for such a construction. Hence, the algorithm is resilient-optimal. Then the paper presents distributed algorithms built on top of this shared memory abstraction, which cope with up to t Byzantine processes. The simplicity of these algorithms constitutes a strong motivation for such a shared memory abstraction in the presence of Byzantine processes. For a lot of problems, algorithms are more difficult to design and prove correct in a message-passing system than in a shared memory system. Using a protocol stacking methodology, the aim of the proposed abstraction is to allow an easier design (and proof) of distributed algorithm, when one has the underlying system is an asynchronous message-passing system prone to Byzantine failures.
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Julien Stainer Connect in order to contact the contributor
Submitted on : Tuesday, May 20, 2014 - 11:29:25 AM
Last modification on : Thursday, January 20, 2022 - 4:19:58 PM
Long-term archiving on: : Wednesday, August 20, 2014 - 11:20:30 AM


Files produced by the author(s)


  • HAL Id : hal-00993400, version 1


Damien Imbs, Sergio Rajsbaum, Michel Raynal, Julien Stainer. Reliable Shared Memory Abstractions on Top of Asynchronous t-Resilient Byzantine Message-passing Systems. [Research Report] PI-2018, 2014. ⟨hal-00993400⟩



Record views


Files downloads