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.
Type de document :
Communication dans un congrès
Structural Information and Communication Complexity, 2014, Hida Takayama, Japan. Springer, Structural Information and Communication Complexity Lecture Notes in Computer Science Volume 8576, 2014, pp 37-53, Volume 8576, pp.37-53, 2014, Lecture Notes in Computer Science. 〈http://link.springer.com/chapter/10.1007%2F978-3-319-09620-9_5〉. 〈10.1007/978-3-319-09620-9_5〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01097383
Contributeur : Julien Stainer <>
Soumis le : vendredi 19 décembre 2014 - 15:26:35
Dernière modification le : mardi 16 janvier 2018 - 15:54:13

Identifiants

Citation

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. Springer, Structural Information and Communication Complexity Lecture Notes in Computer Science Volume 8576, 2014, pp 37-53, Volume 8576, pp.37-53, 2014, Lecture Notes in Computer Science. 〈http://link.springer.com/chapter/10.1007%2F978-3-319-09620-9_5〉. 〈10.1007/978-3-319-09620-9_5〉. 〈hal-01097383〉

Partager

Métriques

Consultations de la notice

738