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.
- Alon N., Attiya H., Dolev S., Dubois S., Potop-Butucaru M., and Tixeuil S., Pragmatic self-stabilization of atomic memory in message-passing systems. Proc. 13th Int'l Symposium on Stabilization, Safety, and Security of Distr. Systems (SSS'11), Springer LNCS 6976, pp. 19--31, 2011. Journal version in Journal of Computer and System Sciences 81(4): 692--701 (2015). Google ScholarDigital Library
- Attiya H. and Bar-Or A., Sharing memory with semi-Byzantine clients and faulty storage servers. Parallel Processing Letters, 16(4):419--428, 2006.Google ScholarCross Ref
- Bonomi S., Dolev S., Potop-Butucaru M., and Raynal M., Stabilizing server-based storage in Byzantine asynchronous message-passing systems. CoRR abs/1503.00140, 2015.Google Scholar
- Bonomi S., Potop-Butucaru M., and Tixeuil S., Stabilizing Byzantine fault-tolerant storage. To appear in Proc. 29th IEEE Int'l Parallel & Distributed Processing Symposium, IEEE Press, 2015.Google Scholar
- Chockler G. and Malkhi D., Active disk Paxos with infinitely many processes. Distributed Computing, 18(1):73--84, 2005. Google ScholarDigital Library
- Dolev S., Self-stabilization, MIT Press, 197 pages, ISBN 0--262-04178--2, 2000. Google ScholarDigital Library
- Dolev S., Dubois S., Potop-Butucaru M., and Tixeuil S., Stabilizing data-link over non-FIFO channels with optimal fault-resilience. Information Processing Letters, 111(18): 912--920, 2011. Google ScholarDigital Library
- Dolev S., Hanemann A., Schiller E., and Sharma S., Stabilizing end-to-end communication in (bounded capacity, omitting, duplicating and non-FIFO) dynamic networks. Proc. 14th Int'l Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'12), Springer LNCS 7596, pp. 133--147, 2012. Google ScholarDigital Library
- Dolev S., Liba O., and Schiller E., Stabilizing Byzantine resilient topology discovery and message delivery. Proc. of the First International Conference Networked Systems (NETYS'13), pp. 42--57, 2013.Google ScholarCross Ref
- Dolev S.. Welch J., Stabilizing clock synchronization in the presence of Byzantine faults. Journal of the ACM, 51(5):780--799, 2004. Google ScholarDigital Library
- Imbs D., Rajsbaum R., Raynal M., and Stainer, J.,Reliable shared memory abstractions on top of asynchronous t-resilient Byzantine message-passing systems. Proc. 21st International Colloquium Structural Information and Communication Complexity (SIROCCO 2014), Springer LNCS 8576, pp. 37--53,2014.Google Scholar
- Lamport L., Shostack R. and Pease M., The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3)-382--401, 1982. Google ScholarDigital Library
- Lamport L., On inter-process communications, Part I: basic formalism. Distributed Computing, 1(2): 77--85, 1986.Google ScholarCross Ref
- Lamport L., On interprocess communication, Part II: algorithms. Distributed Computing, 1(2):77--101, 1986.Google ScholarCross Ref
- Martin J.-Ph. and Alvisi L., A framework for dynamic Byzantine storage. Proc. Int'l Conference on Dependable Systems and Networks (DSN'04), IEEE Press, pp. 325--334, 2004. Google ScholarDigital Library
- Raynal M., Concurrent programming: algorithms, principles, and foundations. Springer, 516 pages, ISBN 978--3--642--32027--9, 2013. Google ScholarDigital Library
- Santoro N. and Widmayer P., Time is not a healer. Proc. 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS'89), Springer LNCS 349, pp. 304--313 (1989) Google ScholarDigital Library
- Santoro N. and Widmayer P.,Agreement in synchronous networks with ubiquitous faults. Theoretical Computer Science, 384(2--3): 232--249, 2007. Google ScholarDigital Library
Index Terms
Stabilizing Server-Based Storage in Byzantine Asynchronous Message-Passing Systems: Extended abstract
Recommendations
Time-efficient read/write register in crash-prone asynchronous message-passing systems
The atomic register is one of the most basic and useful object of computing science, and its simple read---write semantics is appealing when programming distributed systems. Hence, its implementation on top of crash-prone asynchronous message-passing ...
Atomic Read/Write Memory in Signature-Free Byzantine Asynchronous Message-Passing Systems
This article presents a signature-free distributed algorithm which builds an atomic read/write shared memory on top of a fully connected peer-to-peer n-process asynchronous message-passing system in which up to t
Read/write shared memory abstraction on top of asynchronous Byzantine message-passing systems
This paper is on the construction and 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 ...
Comments