The effect of failure and repair distributions on consistency protocols for replicated data objects

ABSTRACT

The accessibility of vital information can be enhanced by replicating the data on several sites, and employing a consistency control protocol to manage the copies. Various protocols have been proposed to ensure that only current copies of the data can be accessed. The effect these protocols have on the accessibility of the replicated data is investigated by simulating the operation of the network and measuring the performance. Several strategies for replica maintenance are considered, and the benefits of each are analyzed. The details of the simulations are discussed. Measurements of the reliability and the availability of the replicated data are compared and contrasted. The sensitivity of the Available Copy and Dynamic-linear Voting protocols to common patterns of site failures and repairs is studied in detail. Exponential, Erlang, uniform, and hyperexponential distributions are considered, and the effect the second moments have on the results is analyzed. The relative performance of competing protocols is shown to be only marginally affected by non-exponential distributions, validating the robustness of the exponential approximations.

REFERENCES

• 1: Arnold O. Allen, Probability, statistics, and queueing theory with computer science applications, Academic Press Professional, Inc., San Diego, CA, 1990
• 2: Philip A. Bernstein , Nathan Goodman, An algorithm for concurrency control and recovery in replicated distributed databases, ACM Transactions on Database Systems (TODS), v.9 n.4, p.596-615, Dec. 1984 [doi>10.1145/1994.2207]
• 3: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 4: Carroll, J.L., "Analysis of the Availability and Reliability of Replicated Data Objects." In Proceedings of the 1989 IVestern Multiconference, San Diego: 1989.
• 5: Carroll, J.L., D.D.E. Long and J.-F. P~ris. "Block-Level Consistency of Replicated Files." In Proceedings of the 7fh InterT~atio~zal Conference on Distributed Computing Systems, Berlin: 1987.
• 6: Dančo Davčev , Walter A. Burkhard, Consistency and recovery control for replicated files, Proceedings of the tenth ACM symposium on Operating systems principles, p.87-96, December 1985, Orcas Island, Washington, United States
• 7: George S. Fishman, Principles of Discrete Event Simulation, John Wiley & Sons, Inc., New York, NY, 1978
• 8: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 9: Glockner, A. "Optimal Consistency Protocols for Replicated Files." In Proceedings of the 8th International Conference on Computers and Communication, Phoenix: IEEE, 1989, to appear.
• 10: Sushil Jajodia, Managing Replicated Files in Partitioned Distributed Database Systems, Proceedings of the Third International Conference on Data Engineering, p.412-418, February 03-05, 1987
• 11: Sushil Jajodia , David Mutchler, Dynamic voting, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.227-238, May 27-29, 1987, San Francisco, California, United States
• 12: Darrell Don Earl Long , Jehan-Francois Paris, The management of replication in a distributed system, 1988
• 13: D.D.E. Long, J.L. Carroll and K. Stewart. "The Reliability of Regeneration-Based Replica Control Protocols." Submitted for publication.
• 14: Long, D.D.E. and J.-F. P ftris. "On improving the Availability of Replicated Files." In Proceedings of the 6th Symposium on Reliability in Distributed Software and Database Systems, Williamsburg: IEEE, 1987, 77-83.
• 15: Long, D.D.E. and J.-F. P'~ris. "A Realistic Evaluation of Optimistic Dynamic Voting." In Proceedings of the 7th Symposium on Reliable Distributed Systems, Columbus: IEEE, October, 1988.
• 16: Darrell D. E. Long , Jehan-François Pâris, Regeneration Protocols for Replicated Objects, Proceedings of the Fifth International Conference on Data Engineering, p.538-545, February 06-10, 1989
• 17: Long, D.D.E., J.-F. P~ris and J.L. Carroll. "Reliability of Replicated Data Objects." In Proceedings of the 8th International Conference on Computers and Communication, Phoenix" IEEE, 1989, to appear.
• 18: Noe, J.D. and A. Andreassian. "Effectiveness of Replication in Distributed Computing Networks." In Proceedings of the 7th International Conference on Distributed Computing Systems, Berlin: IEEE, 1987, 508-513.
• 19: Phris, J.-F. and W.A. Burkhard. "On the Availability of Dynamic Voting Schemes." Tcch,tical Report 86-090, S;ul Diego: Department of CSE, University of California, San Diego, 1986.
• 20: Richard D. Schlichting , Fred B. Schneider, Fail-stop processors: an approach to designing fault-tolerant computing systems, ACM Transactions on Computer Systems (TOCS), v.1 n.3, p.222-238, August 1983 [doi>10.1145/357369.357371]
• 21: Dale Skeen, Determining the last process to fail, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.15-30, Feb. 1985 [doi>10.1145/214451.214453]
• 22: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• 23: Kishar Shridharbhai Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1982

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Distributed

General Terms:
Design, Measurement, Performance, Reliability, Standardization, Theory