Stabilizing Server-Based Storage in Byzantine Asynchronous Message-Passing Systems: Extended abstract

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.

References

1. 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).
2. Attiya H. and Bar-Or A., Sharing memory with semi-Byzantine clients and faulty storage servers. Parallel Processing Letters, 16(4):419--428, 2006.
3. 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.
4. 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.
5. Chockler G. and Malkhi D., Active disk Paxos with infinitely many processes. Distributed Computing, 18(1):73--84, 2005.
6. Dolev S., Self-stabilization, MIT Press, 197 pages, ISBN 0--262-04178--2, 2000.
7. 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.
8. 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.
9. 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.
10. Dolev S.. Welch J., Stabilizing clock synchronization in the presence of Byzantine faults. Journal of the ACM, 51(5):780--799, 2004.
11. 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.
12. Lamport L., Shostack R. and Pease M., The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3)-382--401, 1982.
13. Lamport L., On inter-process communications, Part I: basic formalism. Distributed Computing, 1(2): 77--85, 1986.
14. Lamport L., On interprocess communication, Part II: algorithms. Distributed Computing, 1(2):77--101, 1986.
15. 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.
16. Raynal M., Concurrent programming: algorithms, principles, and foundations. Springer, 516 pages, ISBN 978--3--642--32027--9, 2013.
17. 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)
18. Santoro N. and Widmayer P.,Agreement in synchronous networks with ubiquitous faults. Theoretical Computer Science, 384(2--3): 232--249, 2007.

Index Terms

• Software and its engineering

  • Software organization and properties

    • Extra-functional properties

      • Software fault tolerance

    • Software system structures

      • Distributed systems organizing principles

        • Organizing principles for web applications