An algorithm, for replicated directories

ABSTRACT

This paper describes a replication algorithm for directory objects based upon Gifford's weighted voting for files. The algorithm associates version number with each possible key on every replica and thereby resolves an ambiguity that arises when directory entries are not stored in every replica. The range of keys associated with a version number changes dynamically; but in all instances, a separate version number is associated with each entry stored on every replica. The algorithm exhibits favorable availability and concurrency properties. There is no performance penalty for associating a version number with every possible key except on Delete operations, and simulation results show this overhead is small.

REFERENCES

• 1: James E. Allchin, Martin S. McKendry. Object-Based Synchronization and Recovery. Technical Report GIT-CS-82/15, Georgia Institute of Technology, September, 1982.
• 2: James E. Allchin, Martin S. McKendry. Facilities for Supporting Atomicity in Operating Systems. Technical Report GIT-CS-83/1, Georgia Institute of Technology, January, 1983.
• 3: Peter A. Alsberg , John D. Day, A principle for resilient sharing of distributed resources, Proceedings of the 2nd international conference on Software engineering, p.562-570, October 13-15, 1976, San Francisco, California, United States
• 4: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 5: 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]
• 6: David Kenneth Gifford, Information storage in a decentralized computer system, 1981
• 7: Butler W. Lampson , Robert F. Sproull, An open operating system for a single-user machine, Proceedings of the seventh ACM symposium on Operating systems principles, p.98-105, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806575]
• 8: Bruce G. Lindsay, et al. Notes on Distributed Databases. IBM Research Report RJ2571, IBM Research Laboratory, San Jose, Ca., July, 1979.
• 9: Barbara Liskov , Robert Scheifler, Guardians and actions: linguistic support for robust, distributed programs, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.7-19, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582155]
• 10: G. Popek , B. Walker , J. Chow , D. Edwards , C. Kline , G. Rudisin , G. Thiel, LOCUS a network transparent, high reliability distributed system, Proceedings of the eighth ACM symposium on Operating systems principles, p.169-177, December 14-16, 1981, Pacific Grove, California, United States
• 11: Richard F. Rashid , George G. Robertson, Accent: A communication oriented network operating system kernel, Proceedings of the eighth ACM symposium on Operating systems principles, p.64-75, December 14-16, 1981, Pacific Grove, California, United States
• 12: J. B. Rothnie, N. Goodman, P.A. Bernstein. The Redundant Update Methodology of SDD-1: A System for Distributed Databases (The Fully Redundant Case). Technical Report CCA-77-02, Computer Corporation of America, 1977.
• 13: Peter M. Schwarz, Alfred Z. Spector. Synchronizing Shared Abstract Types. Carnegie-Mellon Report CMU-CS-82-128, Carnegie-Mellon University, Pittsburgh, PA, September, 1982.
• 14: Alfred Z. Spector , Peter M. Schwarz, Transactions: a construct for reliable distributed computing, ACM SIGOPS Operating Systems Review, v.17 n.2, p.18-35, April 1983 [doi>10.1145/1041478.1041481]
• 15: Irving L. Traiger , Jim Gray , Cesare A. Galtieri , Bruce G. Lindsay, Transactions and consistency in distributed database systems, ACM Transactions on Database Systems (TODS), v.7 n.3, p.323-342, Sept. 1982 [doi>10.1145/319732.319734]
• 16: William Weihl , Barbara Liskov, Specification and implementation of resilient, atomic data types, Proceedings of the 1983 ACM SIGPLAN symposium on Programming language issues in software systems, p.53-64, June 27-29, 1983, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Distributed file systems
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Algorithms, Reliability

Keywords:
Availability, Replicated data, Transaction- based systems