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

Damien Imbs (1) , Sergio Rajsbaum (1) , Michel Raynal (2, 3) , Julien Stainer (2)

1 Instituto de Matematicas [México]
2 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
3 IUF - Institut universitaire de France

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.

Cet article propose une abstraction de mémoire partagée adaptée aux systèmes asynchones à passage de messages où jusqu'à t fautes Byzantines peuvent survenir. Il présente également une implémentation de cette abstraction ainsi que sa preuve.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

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⟩