Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Atomic Read/Write Memory in Signature-free Byzantine Asynchronous Message-passing Systems

Abstract : This article presents a signature-free distributed algorithm which builds an atomic read/write shared memory on top of an n-process asynchronous message-passing system in which up to t < n/3 processes may commit Byzantine failures. From a conceptual point of view, this algorithm is designed to be as close as possible to the algorithm proposed by Attiya, Bar-Noy and Dolev (JACM 1995), which builds an atomic register in an n-process asynchronous message-passing system where up to t < n/2 processes may crash. The proposed algorithm is particularly simple. It does not use cryptography to cope with Byzantine processes, and is optimal from a t-resilience point of view (t < n/3). A read operation requires O(n) messages, and a write operation requires O(n 2) messages. Mémoire partagée fiable dans les systèmes asynchones avec processus Byzantins Résumé : Cet article présente une construction de mémoire partagée au dessus d'un système asynchone à passage de messages dans lequel jusqu'à t < n/3 processus peuvent avoir des comportements arbitraires (fautes Byzantines), n étant le nombre total de processsus.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-01238765
Contributor : Michel Raynal <>
Submitted on : Tuesday, December 8, 2015 - 3:41:43 PM
Last modification on : Thursday, January 7, 2021 - 4:26:04 PM
Long-term archiving on: : Wednesday, March 9, 2016 - 11:43:24 AM

File

RR-2028-SeqNb-Byz-memmory.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01238765, version 1

Citation

Achour Mostefaoui, Matoula Petrolia, Michel Raynal, Claude Jard. Atomic Read/Write Memory in Signature-free Byzantine Asynchronous Message-passing Systems. 2015. ⟨hal-01238765⟩

Share

Metrics

Record views

2588

Files downloads

377