Skip to Main content Skip to Navigation
Reports

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

https://hal.inria.fr/hal-00993400
Contributor : Julien Stainer <>
Submitted on : Tuesday, May 20, 2014 - 11:29:25 AM
Last modification on : Friday, January 8, 2021 - 3:41:09 AM
Long-term archiving on: : Wednesday, August 20, 2014 - 11:20:30 AM

File

Byzantine-memory-RR-V1.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00993400, version 1

Citation

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⟩

Share

Metrics

Record views

1477

Files downloads

505