BASE: using abstraction to improve fault tolerance

ABSTRACT

Software errors are a major cause of outages and they are increasingly exploited in malicious attacks. Byzantine fault tolerance allows replicated systems to mask some software errors but it is expensive to deploy. This paper describes a replication technique, BASE, which uses abstraction to reduce the cost of Byzantine fault tolerance and to improve its ability to mask software errors. BASE reduces cost because it enables reuse of off-the-shelf service implementations. It improves availability because each replica can be repaired periodically using an abstract view of the state stored by correct replicas, and because each replica can run distinct or non-deterministic service implementations, which reduces the probability of common mode failures. We built an NFS service where each replica can run a different off-the-shelf file system implementation, and an object-oriented database where the replicas ran the same, non-deterministic implementation. These examples suggest that our technique can be used in practice --- in both cases, the implementation required only a modest amount of new code, and our performance results indicate that the replicated services perform comparably to the implementations that they reuse.

REFERENCES

• 1: Atul Adya , Robert Gruber , Barbara Liskov , Umesh Maheshwari, Efficient optimistic concurrency control using loosely synchronized clocks, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.23-34, May 22-25, 1995, San Jose, California, United States
• 2: T. C. Bressoud , F. B. Schneider, Hypervisor-based fault tolerance, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.1-11, December 03-06, 1995, Copper Mountain, Colorado, United States
• 3: Brent Callaghan, NFS illustrated, Addison-Wesley Longman Ltd., Essex, UK, 2000
• 4: Michael J. Carey , David J. DeWitt , Jeffrey F. Naughton, The 007 Benchmark, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.12-21, May 25-28, 1993, Washington, D.C., United States
• 5: M. Castro. Practical Byzantine Fault-Tolerance. PhD thesis, Massachusetts Institute of Technology, 2000.
• 6: Miguel Castro , Atul Adya , Barbara Liskov , Andrew C. Meyers, HAC: hybrid adaptive caching for distributed storage systems, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.102-115, October 05-08, 1997, Saint Malo, France
• 7: Miguel Castro , Barbara Liskov, Practical Byzantine fault tolerance, Proceedings of the third symposium on Operating systems design and implementation, p.173-186, February 1999, New Orleans, Louisiana, United States
• 8: M. Castro and B. Liskov. Proactive recovery in a Byzantine-fault-tolerant system. In Proceedings of the Fourth Symposium on Operating Systems Design and Implementation, San Diego, CA, Oct. 2000.
• 9: L. Chen and A. Avizienis. N-Version Programming: A Fanlt-Tolerance Approach to Reliability of Software Operation. In Fault Tolerant Computing, FTCS-8, pages 3-9, 1978.
• 10: Eric C. Cooper, Replicated distributed programs, Proceedings of the tenth ACM symposium on Operating systems principles, p.63-78, December 1985, Orcas Island, Washington, United States
• 11: Kyle Geiger, Inside ODBC, Microsoft Press, Redmond, WA, 1995
• 12: Sanjay Ghemawat , Barbara H. Liskov , M. Frans Kaashoek, The modified object buffer: a storage management technique for object-oriented databases, 1995
• 13: Jim Gray , Daniel P. Siewiorek, High-Availability Computer Systems, Computer, v.24 n.9, p.39-48, September 1991 [doi>10.1109/2.84898]
• 14: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 15: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 16: Nick Kolettis , N. Dudley Fulton, Software Rejuvenation: Analysis, Module and Applications, Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant Computing, p.381, June 27-30, 1995
• 17: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 18: Barbara Liskov , Miguel Castro , Liuba Shrira , Atul Adya, Providing Persistent Objects in Distributed Systems, Proceedings of the 13th European Conference on Object-Oriented Programming, p.230-257, June 14-18, 1999
• 19: Barbara Liskov , Sanjay Ghemawat , Robert Gruber , Paul Johnson , Liuba Shrira, Replication in the harp file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.226-238, October 13-16, 1991, Pacific Grove, California, United States
• 20: Barbara Liskov , John Guttag, Program Development in Java: Abstraction, Specification, and Object-Oriented Design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 21: S. Maffeis. Adding group communication and fault tolerance to CORBA. In Proceedings of the Pad USENIX Conference on Object-Oriented Technologies, pages 135-146, June 1995.
• 22: K. Marzullo and F. Schmuck. Supplying high availability with a standard network file system. In Proceedings of the 8th International Conference on Distributed Computing Systems, pages 447-453. IEEE, June 1988.
• 23: R. Minnich. The Linux BIOS Home Page. http://www.acl.lanl.gov/linuxbios, 2000.
• 24: L. E. Moser , P. M. Melliar-Smith , P. Narasimhan, Consistent object replication in the eternal system, Theory and Practice of Object Systems, v.4 n.2, p.81-92, April 1998 [doi>10.1002/(SICI)1096-9942(1998)4:2<81::AID-TAPO3>3.3.CO;2-M]
• 25: Providing Support for Survivable CORBA Applications with the Immune System, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.507, May 31-June 04, 1999
• 26: Network working group request for comments: 1014. XDR: External data representation standard, June 1987.
• 27: Network working group request for comments: 1094. NFS: Network file system protocol specification, March 1989.
• 28: Object Management Group. The Common Object Request Broker: Architecture and Specification. OMG techical committee document formal/98-12-01, June 1999.
• 29: Object Management Group. Fault Tolerant CORBA. OMG techical committee document orbos/2000-04-04, Mar. 2000.
• 30: J. Ousterhout. Why Aren't Operating Systems Getting Faster as Fast as Hardware? In Proceedings of USENIX Summer Conference, pages 247-256, Anaheim, CA, June 1990.
• 31: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 32: R. Rodrigues. Combining abstraction with Byzantine fault-tolerance. Master's thesis, Massachusetts Institute of Technology, 2001.
• 33: A. Romanovsky. Faulty version recovery in object-oriented N-version programming. IEE Proceedings - Software, 147(3):81-90, June 2000.
• 34: FrZdZric Salles , Manuel Rodrguez , Jean-Charles Fabre , Jean Arlat, MetaKernels and Fault Containment Wrappers, Proceedings of the Twenty-Ninth Annual International Symposium on Fault-Tolerant Computing, p.22, June 15-18, 1999
• 35: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 36: K. Tso and A. Avizienis. Community error recovery in N-version software: A design study with experimentation. In Proceedings of the 17th Annual International Symposium on Fault-Tolerant Computing, pages 127-133, Pittsburgh, PA, July 1987.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Error handling and recovery

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Object-oriented databases

General Terms:
Experimentation, Reliability, Theory