Maurice Herlihy
Abstract
Replication can enhance the availability of data in distributed systems. This paper introduces a new method for managing replicated data. Unlike many methods that support replication only for uninterpreted files, this method systematically exploits type-specific properties of objects such as sets, queues, or directories to provide more effective replication. Each operation requires the cooperation of a certain number of sites for its successful completion. A quorum for an operation is any such set of sites. Necessary and sufficient constraints on quorum intersections are derived from an analysis of the data type's algebraic structure. A reconfiguration method is proposed that permits quorums to be changed dynamically. By taking advantage of type-specific properties in a general and systematic way, this method can realize a wider range of availability properties and more flexible reconfiguration than comparable replication methods.
- 1 ALSBERG, P. A., AND DAY, J.D. A principle for resilient sharing of distributed resources. In Proceedings of the 2nd Annual Conference on Software Engineering. (San Francisco, Calif., Oct. 13-15) 1976.]] Google Scholar
- 2 BERNSTEIN, P. A., AND GOODMAN, N. A survey of techniques for synchronization and recovery in decentralized computer systems. ACM Comput. Surv. 13, 2 (June, 1981), 185-222.]] Google Scholar
- 3 BERNSTEIN, P. A., AND GOODMAN, N. The failure and recovery problem for replicated databases. In Proceedings of the 2nd Annual Symposium on Principles of Distributed Computing. August, 1983.]] Google Scholar
- 4 BIRMAN, K.P. Replication and fault-tolerance in the ISIS system. In Proceedings of the l Oth Symposium on Operating Systems Principles. Dec., 1985. Also Tech. Rep. 85-668, Computer Science Department, Cornell University, 1985.]] Google Scholar
- 5 BIRREL, A. D., LEVIN, R., NEEDHAM, R., AND SCHROEDER, M. Grapevine: An exercise in distributed computing. Commun. ACM 25, 14 (April, 1982), 260-274.]] Google Scholar
- 6 BLOCH, J. J., DANIELS, D. S., AND SPECTOR, A.Z. Weighted voting for directories: A comprehensive study. Tech. Rep. CMU-CS-84-114, Carnegie-Mellon University, April, 1984.]]Google Scholar
- 7 CHAN, A., FOX, S., LIN, W. T., NORI, A., AND RIES, D. The implementation of an integrated concurrency control and recovery scheme. In Proceedings of the 1982 SIGMOD Conference. ACM SIGMOD (Orlando, Fla., June 2-4), 184-191.]] Google Scholar
- 8 COOPER, E.C. Circus: A replicated procedure call facility. In Proceedings 4th Symposium on Reliability in Distributed Software and Database Systems (Silver Spring, Md., Oct. 1984), IEEE, NY, 1985, pp. 11-24.]]Google Scholar
- 9 DUBOURDIEU, D.J. implementation of Distributed Transactions. In Proceedings 1982 Berkeley Workshop on Distributed Data Management and Computer Networks, (Asilomar, Calif., Feb. 16-19), National Technical Information Services, 1982, pp. 81-94.]]Google Scholar
- 10 EAGER, D. L., AND SEVCIK, K.C. Achieving robustness in distributed database systems. ACM Trans. Database Syst. 8, 3 (Sept., 1983), 354-381.]] Google Scholar
- 11 ESWARAN, K. P., GRAY, J. N., LORIE, R. A., AND TRAIGER, I.L. The notion of consistency and predicate locks in a database system. Commun. ACM 19, 11 (Nov., 1976), 624-633.]] Google Scholar
- 12 FISCHER, M., AND MICHAEL, A. Sacrificing serializability to attain high availability of data in an unreliable network. In Proceedings, A CM SIGACT-SIGMOD Symposium on Principles of Database Systems. March, 1982.]] Google Scholar
- 13 GARCIA-MOLINA, H., AND BARBARA, D. How to assign votes in a distributed system. To appear in J. A CM.]] Google Scholar
- 14 GIFFORD, D.K. Weighted Voting for Replicated Data. In Proceedings of the Seventh Symposium on Operating Systems Principles. ACM SIGOPS, December, 1979.]] Google Scholar
- 15 GIFFORD, D.K. Information Storage in a Decentralized Computer System. Tech. Rep. CSL-81- 8, Xerox Corporation, March, 1982.]]Google Scholar
- 16 GOODMAN, N., SKEEN, D., CHAN, A., DAYAL, U., FOX, S., AND RIES, D. A recovery algorithm for a distributed database system. In Proceedings, 2nd A CM SIGACT-SIGMOD Symposium on Principles of Database Systems. March, 1983.]] Google Scholar
- 17 HAMMER, M. M., AND SHIPMAN, D. W. Reliability Mechanisms in SDD-1, a System for Distributed Databases. ACM Trans. Database Syst. 5, 4 (Dec., 1980) 431-336.]] Google Scholar
- 18 HERLIHY, M.P. Replication Methods for Abstract Data Types. Tech. Rep. MIT/LCS/TR-319, Massachusetts Institute of Technology Laboratory for Computer Science, Cambridge, Mass., May, 1984. Ph.D. Thesis.]] Google Scholar
- 19 HERLIHY, M.P. Using type information to enhance the availability of partitioned data. Tech. Rep. CMU-CS-85-119, Carnegie-Mellon University, April, 1985.]]Google Scholar
- 20 JOHNSON, P. R., AND THOMAS, R.H. The maintenance of duplicate databases. Tech. Rep. RFC 677 NIC 31507, Network Working Group, january, 1975.]] Google Scholar
- 21 JOSEPH, T., AND BIRMAN, K.P. Low-cost management of replicated data in distributed systems. To appear, ACM TOCS.]] Google Scholar
- 22 LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Commun. A CM 21, 7 (July, 1978), 558-565.]] Google Scholar
- 23 LISKOV, B., AND SNYDER, A. Exception handling in CLU. IEEE Trans. Softw. Eng. 5, 6 (Nov., 1979), 546-558.]]Google Scholar
- 24 LISKOV, B., AND SCHEIFLER, R. Guardians and actions: Linguistic support for robust, distributed programs. ACM Trans. Program. Lang. Syst. 5, 3 (July, 1983), 381-404.]] Google Scholar
- 25 MINOURA, T., AND WIEDERHOLD, G. Resilient extended true-copy token scheme for a distributed database system. IEEE Trans. Softw. Eng. 8, 3 (May, 1982), 173-188.]]Google Scholar
- 26 Moss, J. E.B. Nested transactions: An approach to reliable distributed computing. Tech. Rep. MIT/LCS/TR-260, Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge, Mass. April, 1981.]] Google Scholar
- 27 OPPEN, D., AND DALAL, Y.K. The clearinghouse: A decentralized agent for locating named objects in a distributed environment. Tech. Rep. OPD-T8103, Xerox Corporation, October, 1981.]]Google Scholar
- 28 PAPADIMITRIOU, C.H. The serializability of concurrent database updates. J. ACM 26, 4 (Oct., 1979), 631-653.]] Google Scholar
- 29 REED, D. Implementing atomic actions on decentralized data. ACM Trans. Comp. Syst. 1, 1 (Feb., 1983), 3-23.]] Google Scholar
- 30 SPECTOR, A. Z., BUTCHER, J., DANIELS, D. S., DUCHAMP, D. J., EPPINGER, J. L., FINEMAN, C. E., HEDDAYA, A., AND SCHWARZ, P.M. Support for distributed transactions in the TABS prototype. TOSE 11, 6 (June, 1985), 520-530.]]Google Scholar
- 31 THOMAS, R.H. A solution to the concurrency control problem for multiple copy databases. In Proceedings o{ the 16th IEEE Computer Society international Conference (COMPCON) (New York, NY) Spring, 1978.]]Google Scholar
- 32 VERHOFSTAD, J. S.M. Recovery Techniques for Database Systems. ACM Comput. Surv. 10, 2 (June, 1978), 167-196.]] Google Scholar
- 33 WEIHL, W. Specification and implementation of atomic data types. Tech. Rep. TR-314, Massachusetts Institute of Technology Laboratory for Computer Science, Cambridge, Mass. March, 1984.]] Google Scholar
Index Terms
- A quorum-consensus replication method for abstract data types
Recommendations
Quorum based data replication in grid environment
RSKT'08: Proceedings of the 3rd international conference on Rough sets and knowledge technologyReplication is a useful technique for distributed database systems and can be implemented in a grid computation environment to provide a high availability, fault tolerant, and enhance the performance of the system. This paper discusses a new protocol ...
Performance evaluation of the quorum consensus replication method
IPDS '95: Proceedings of the International Computer Performance and Dependability Symposium on Computer Performance and Dependability SymposiumAbstract: The goal of data replication in distributed database systems is to increase data availability in the presence of failures. Using the quorum consensus method, up to [(n+1)/2] site failures can be tolerated, in an n-site system without loss of ...
Circular Quorum Systems for Write Dominant Data Replication Protocols under Serial Isolation Using Quorum Consensus Approach
AbstractIn distributed systems, we replicate data for the purpose of increasing availability and performance. If any application requires serial isolation and have the dominance of write operations can effectively use quorum consensus approach. In such a ...
Reviews
Alan R. Feuer
The author addresses the problem of accessing data in a distributed database. He discusses the advantage of replicating data at multiple sites—increased reliability in the face of failures—and the problem of keeping the data consistent when there are multiple repositories for the same records. Any database system that allows reading and writing concurrently must address the problem of presenting consistent records to its readers. If a transaction involves changing several records, it would be unfortunate if a reader reading those records saw some new and some old data. Potentially more unfortunate would be allowing those records to be changed by two different writers at the same time, which could leave the records inconsistent among themselves. Both consistency problems are solved by making a transaction an atomic operation on the database. A distributed database system with replicated records that allows writing to the same record at multiple sites confounds these problems. The key question addressed by the author is “How many sites must be polled to assure that a read returns the current version of a record__?__” The answer is a function of how many sites are written to for an update. In the author's scheme, the number of sites written (called the write quorum) is adjusted based on the semantics of the operation. For example, if a write operation is frequent relative to a read, then the write quorum may be kept small at the cost of requiring a larger read quorum. After describing his method, the author gives a short proof of its correctness and some examples of its application. He ends with a discussion of some implementation issues.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments