Stabilizing server-based storage in Byzantine asynchronous message-passing systems (extended abstract)

DOI10.1145/2767386.2767441MaRDI QIDQ2796285zbMATH OpenOpenAlexFDO

Authors Silvia Bonomi, Shlomi Dolev, Michel Raynal, Maria Potop-Butucaru

Publication date 23 March 2016

Published in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

asynchronous message-passing systematomic read/write registerByzantine server

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

Abstract: A stabilizing Byzantine single-writer single-reader (SWSR) regular register, which stabilizes after the first invoked write operation, is first presented. Then, new/old ordering inversions are eliminated by the use of a (bounded) sequence number for writes, obtaining a practically stabilizing SWSR atomic register. A practically stabilizing Byzantine single-writer multi-reader (SWMR) atomic register is then obtained by using several copies of SWSR atomic registers. Finally, bounded time-stamps, with a time-stamp per writer, together with SWMR atomic registers, are used to construct a practically stabilizing Byzantine multi-writer multi-reader (MWMR) atomic register. In a system of $n$ servers implementing an atomic register, and in addition to transient failures, the constructions tolerate t<n/8 Byzantine servers if communication is asynchronous, and t<n/3 Byzantine servers if it is synchronous. The noteworthy feature of the proposed algorithms is that (to our knowledge) these are the first that build an atomic read/write storage on top of asynchronous servers prone to transient failures, and where up to t of them can be Byzantine.

Recommendations

• Remote storage with Byzantine servers
• Bounded Wait-Free f-Resilient Atomic Byzantine Data Storage Systems for an Unbounded Number of Clients
• scientific article; zbMATH DE number 2013839
• Bounded Wait-Free Implementation of Optimally Resilient Byzantine Storage Without (Unproven) Cryptographic Assumptions
• Optimal self-stabilizing synchronous mobile Byzantine-tolerant atomic register

Cites work

• scientific article; zbMATH DE number 826255 (Why is no real title available?)
• Memorization and Association on a Realistic Neural Model

Cited in

(16)

• Optimal self-stabilizing synchronous mobile Byzantine-tolerant atomic register
• Optimal self-stabilizing mobile Byzantine-tolerant regular register with bounded timestamps
• Self-stabilizing and private distributed shared atomic memory in seldomly fair message passing networks
• The complexity of robust atomic storage
• scientific article; zbMATH DE number 7295743 (Why is no real title available?)
• Bounded Wait-Free Implementation of Optimally Resilient Byzantine Storage Without (Unproven) Cryptographic Assumptions
• Bounded Wait-Free f-Resilient Atomic Byzantine Data Storage Systems for an Unbounded Number of Clients
• A protocol for implementing Byzantine storage in churn-prone distributed systems
• scientific article; zbMATH DE number 2013839 (Why is no real title available?)
• scientific article; zbMATH DE number 1875370 (Why is no real title available?)
• Optimal mobile Byzantine fault tolerant distributed storage (extended abstract)
• Remote storage with Byzantine servers
• Reliable shared memory abstraction on top of asynchronous Byzantine message-passing systems
• Self-stabilizing Byzantine fault-tolerant repeated reliable broadcast
• Practically-self-stabilizing vector clocks without scheduling fairness
• Wait-free regular storage from Byzantine components

This page was built for publication: Stabilizing server-based storage in Byzantine asynchronous message-passing systems (extended abstract)

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