Atomic read/write memory in signature-free Byzantine asynchronous message-passing systems

DOI10.1007/S00224-016-9699-8MaRDI QIDQ2398211zbMATH OpenOpenAlexFDO

Authors Matoula Petrolia, Michel Raynal, Claude Jard, Achour Mostefaoui

Publication date 15 August 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.08161

zbMATH Keywords

asynchronous message-passing systematomic read/write registerByzantine processlinearizabilityreliable broadcast abstraction

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

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.

Recommendations

• Reliable shared memory abstraction on top of asynchronous Byzantine message-passing systems
• Signature-free asynchronous binary Byzantine consensus with \(t<n/3\), \(O(n^2)\) messages, and \(O(1)\) expected time
• Signature-free asynchronous byzantine consensus with t < n/3 and o(n ² ) messages
• Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with \(t<n/3\), \(O(n^{2})\) messages, and constant time
• Signature-free asynchronous Byzantine systems: from multivalued to binary consensus with \(t<n/3\), \(O(n^2)\) messages, and constant time

Cites work

• Axioms for memory access in asynchronous hardware systems
• Concurrent programming: algorithms, principles, and foundations.
• Distributed Algorithms for Message-Passing Systems
• Efficient and Robust Sharing of Memory in Message-Passing Systems
• scientific article; zbMATH DE number 1179121 (Why is no real title available?)
• On interprocess communication. I: Basic formalism
• Reaching Agreement in the Presence of Faults
• Reliable shared memory abstraction on top of asynchronous Byzantine message-passing systems
• The Byzantine Generals Problem
• The complexity of robust atomic storage

Cited in

(4)

• Practically stabilizing SWMR atomic memory in message-passing systems
• Signature-free communication and agreement in the presence of Byzantine processes
• Reliable shared memory abstraction on top of asynchronous Byzantine message-passing systems
• On implementing SWMR registers from SWSR registers in systems with Byzantine failures

This page was built for publication: Atomic read/write memory in signature-free Byzantine asynchronous message-passing systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2398211)