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

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