Consistency in a partitioned network: a survey

ABSTRACT

Recently, several strategies have been proposed for transaction processing in partitioned distributed database systems with replicated data. These strategies are surveyed in light of the competing goals of maintaining correctness and achieving high availability. Extensions and combinations are then discussed, and guidelines are presented for selecting strategies for particular applications.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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
	2	Peter M. G. Apers , Gio Wiederhold, Transaction classification to survive a network partition, Stanford University, Stanford, CA, 1984
	3	BERNSTEIN, P. A., AND GOODMAN, N. 1980. Timestamp-based algorithms for concurrency control in distributed database systems. In Proceedings of the 6th lnternationl Conference on Very Large Data Bases (Cannes, France, Sept. 9-11). IEEE, New York, pp. 285-300.
	4	Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
	5	Philip A. Bernstein , Nathan Goodman, The failure and recovery problem for replicated databases, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.114-122, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806714]
	6	Philip A. Bernstein , David W. Shipman , James B. Rothnie, Jr., Concurrency control in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.18-51, March 1980 [doi>10.1145/320128.320131]
	7	BLAUSTEIN, B. T. 1981. Enforcing database assertions: Techniques and applications. TR-21-81, Aiken Computation Laboratory, Harvard Univ., Cambridge, Mass.
	8	BLAUSTEIN, B. T., GARCIA, H., RIES, D. R., CHILEN- SKAS, R. M., AND KAUFMAN, C. W. 1983. Maintaining replicated databases even in the presence of network partitions. In Proceedings of the IEEE 16th Electrical and Aerospace Systems Conference (Washington, D.C., Sept.). IEEE, New York, pp. 353-360.
	9	Susan B. Davidson, An optimistic protocol for partitioned distributed database systems, 1982
	10	Susan B. Davidson, Optimism and consistency in partitioned distributed database systems, ACM Transactions on Database Systems (TODS), v.9 n.3, p.456-481, Sept. 1984 [doi>10.1145/1270.1499]
	11	Derek L. Eager , Kenneth C. Sevcik, Achieving robustness in distributed database systems, ACM Transactions on Database Systems (TODS), v.8 n.3, p.354-381, Sept. 1983 [doi>10.1145/319989.319992]
	12	Amr El Abbadi , Dale Skeen , Flaviu Cristian, An efficient, fault-tolerant protocol for replicated data management, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.215-229, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325443]
	13	K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
	14	Michael J. Fischer , Alan Michael, Sacrificing serializability to attain high availability of data in an unreliable network, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588124]
	15	GARCIA, H. 1982. Elections in a distributed computing system. IEEE Trans. Comput. C-31, 1 (Jan.), 48-59.
	16	Hector Garcia-Molina, Using semantic knowledge for transaction processing in a distributed database, ACM Transactions on Database Systems (TODS), v.8 n.2, p.186-213, June 1983 [doi>10.1145/319983.319985]
	17	Hector Garcia-Molina , Gio Wiederhold, Read-only transactions in a distributed database, ACM Transactions on Database Systems (TODS), v.7 n.2, p.209-234, June 1982 [doi>10.1145/319702.319704]
	18	GARCIA, H., ALLEN, T., BLAUSTEIN, B., CHILENSKAS, R. M., AND RIES, D. R. 1983. Data-Patch: Integrating inconsistent copies of a database after a partition. In Proceedings of the 3rd IEEE Symposium on Reliability in Distributed Software and Database Systems (Oct.). IEEE, New York, pp. 38-48.
	19	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]
	20	David Gifford , Alfred Spector, The TWA reservation system, Communications of the ACM, v.27 n.7, p.650-665, July 1984 [doi>10.1145/358105.358192]
	21	Nathan Goodman , Dale Skeen , Arvola Chan , Umeshwar Dayal , Stephen Fox , Daniel Ries, A recovery algorithm for a distributed database system, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588061]
	22	Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
	23	GRAY, J. N., LORIE, R. A., PUTZOLU, G. R., AND TRAIGER, I. L. 1976. Granularity of locks and degrees of consistency in a shared database, in Modeling in Database Management Systems, G. M. Nijisen, Ed. Elsevier North-Holland, New York, pp. 365-394.
	24	Jim Gray , Paul McJones , Mike Blasgen , Bruce Lindsay , Raymond Lorie , Tom Price , Franco Putzolu , Irving Traiger, The Recovery Manager of the System R Database Manager, ACM Computing Surveys (CSUR), v.13 n.2, p.223-242, June 1981 [doi>10.1145/356842.356847]
	25	Micael Hammer , David Shipman, Reliability mechanisms for SDD-1: a system for distributed databases, ACM Transactions on Database Systems (TODS), v.5 n.4, p.431-466, Dec. 1980 [doi>10.1145/320610.320621]
	26	HERLIHY, M. P. 1984. General quorum consensus: A replication method for abstract data types. Tech. Rep. CMU-CS-84-164, Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa. (Dec.).
	27	HERLIHY, M. P. 1985. Using type information to enhance the availability of partitioned data. Unpublished manuscript, Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh, Pa. (Apr.).
	28	Walter H. Kohler, A Survey of Techniques for Synchronization and Recovery in Decentralized Computer Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.149-183, June 1981 [doi>10.1145/356842.356845]
	29	H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
	30	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]
	31	Witold Lipski, Jr., On semantic issues connected with incomplete information databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.262-296, Sept. 1979 [doi>10.1145/320083.320088]
	32	Barbara Liskov , Robert Scheifler, Guardians and Actions: Linguistic Support for Robust, Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.381-404, July 1983 [doi>10.1145/2166.357215]
	33	Nancy A. Lynch, Multilevel atomicity—a new correctness criterion for database concurrency control, ACM Transactions on Database Systems (TODS), v.8 n.4, p.484-502, Dec. 1983 [doi>10.1145/319996.319999]
	34	MINOURA, T., AND WIEDERHOLD, G. 1982. Resilient extended true-copy token scheme for a distributed database system. IEEE Trans. So{tw. Eng. SE-8, 3 (May), 173-189.
	35	C. Mohan, Distributed data base management: Some thoughts and analyses, Proceedings of the ACM 1980 annual conference, p.399-410, January 1980 [doi>10.1145/800176.809995]
	36	Christos H. Papadimitriou, The serializability of concurrent database updates, Journal of the ACM (JACM), v.26 n.4, p.631-653, Oct. 1979 [doi>10.1145/322154.322158]
	37	PARKER, D. S., AND RAMOS, R. A. 1982. A distributed file system architecture supporting high availability. In Proceedings of the 6th Berkeley Workshop on Distributed Data Management and Computer Networks (Pacific Grove, Calif., Feb,). Lawrence Berkeley Laboratory, University of California, Berkeley, Calif., pp. 161-183.
	38	PARKER, D. S., POPEK, G. J., RUDISlN, G,, STOUGH- TON, A., WALKER, B., WALTON, E., CHOW, J., EDWARDS, D., KISER, $., AND KLINE, C. 1983. Detection of mutual inconsistency in distributed systems. IEEE Trans. Softw. Eng. 9, 3 (May).
	39	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
	40	ROTHNIE, J. B., AND GOODMAN, $. 1977. A survey of research and development in distributed database management. In Proceedings o/ the 3rd International Conference on Very Large Data Bases (Tokyo, Japan, Oct. 6-8). IEEE, New York, pp. 48-61.
	41	SARIN, S., BLAUSTEiN, B., AND KAUFMAN, C. 1985. System architecture for partition-tolerant distributed databases. IE EE Trans. Comput. C-34, 12 (Dec.), 1158-1163.
	42	SKEEN, D. 1982a. A quorum-based commit protocol. in Proceedings of the 6th Berkeley Workshop on Distributed Data Management and Computer Networks (Pacific Grove, Calif., Feb.). Lawrence Berkeley Laboratory, Univ. of California, Berkeley, Calif. pp. 69-80.
	43	SKEEN, D. 1982b. Crash recovery in a distributed database system. Doctoral dissertation and ERL Memo M82/45, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley (May).
	44	SKEEN, D. 1982c. On network partitioning. In Proceedings of the IEEE Computer Software and Applications Conference (COMPSAC) (Nov.). IEEE, New York, pp. 454-455.
	45	SKEEN, D., AND STONEBRAKER, M. 1983. A formal model of crash recovery in a distributed system. IEEE Trans. Softw. Eng. SE-9, 3 (May), 219- 228.
	46	Dale Skeen , David D. Wright, Increasing availability in partitioned database systems, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588054]
	47	STONEBRAKER, M. 1979. Concurrency control and consistency of multiple copies in distributed INGRES. IEEE Trans. Softw. Eng. SE-5, 3 (May), 188-194.
	48	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]
	49	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]
	50	WRIGHT, D. D. 1983. Managing distributed databases in partitioned networks. TR83-572, Dept. of Computer Science, Cornell Univ., Ithaca, N.Y. (Sept.).