Skip to Main content Skip to Navigation
Conference papers

Reliable Shared Memory Abstraction on Top of Asynchronous 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. Differently from usual atomic registers which record a single value, each of these atomic registers records the whole history of values written to it. 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 algorithms, when the underlying system is an asynchronous message-passing system prone to Byzantine failures.
Complete list of metadata
Contributor : Julien Stainer <>
Submitted on : Friday, December 19, 2014 - 3:26:35 PM
Last modification on : Tuesday, June 15, 2021 - 4:25:50 PM



Damien Imbs, Sergio Rajsbaum, Michel Raynal, Julien Stainer. Reliable Shared Memory Abstraction on Top of Asynchronous Byzantine Message-Passing Systems. Structural Information and Communication Complexity, 2014, Hida Takayama, Japan. pp.37-53, ⟨10.1007/978-3-319-09620-9_5⟩. ⟨hal-01097383⟩



Record views