Providing high availability using lazy replication

ABSTRACT

To provide high availability for services such as mail or bulletin boards, data must be replicated. One way to guarantee consistency of replicated data is to force service operations to occur in the same order at all sites, but this approach is expensive. For some applications a weaker causal operation order can preserve consistency while providing better performance. This paper describes a new way of implementing causal operations. Our technique also supports two other kinds of operations: operations that are totally ordered with respect to one another and operations that are totally ordered with respect to all other operations. The method performs well in terms of response time, operation-processing capacity, amount of stored state, and number and size of messages; it does better than replication methods based on reliable multicast techniques.

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	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	Kenneth P. Birman , Thomas A. Joseph, Reliable communication in the presence of failures, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.47-76, Feb. 1987 [doi>10.1145/7351.7478]
	4	André Schiper , Kenneth Birman , Pat Stephenson, Lightweight causal and atomic group multicast, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.272-314, Aug. 1991 [doi>10.1145/128738.128742]
	5	Andrew D. Birrell , Roy Levin , Michael D. Schroeder , Roger M. Needham, Grapevine: an exercise in distributed computing, Communications of the ACM, v.25 n.4, p.260-274, April 1982 [doi>10.1145/358468.358487]
	6	Amr El Abbadi , Sam Toueg, Availability in partitioned replicated databases, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.240-251, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15418]
	7	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]
	8	FAreWELL, A. K. A deadlock detection scheme for Argus. S. B. thesis, Dept. of Electrical Engineering and Computer Science, MIT, Cambridge, Mass., July 1988.
	9	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]
	10	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]
	11	GIFPORD, D.K. Information storage in a decentralized computer system. Tech. Rep. CSL-81- 8, Xerox Corp., Mar 1983.
	12	A. Heddaya , M. Hsu , W. Weihl, Two phase gossip: managing distributed event histories, Information Sciences: an International Journal, v.49 n.1-3, p.35-57, Oct.-Dec. 1989 [doi>10.1016/0020-0255(89)90023-6]
	13	Maurice Herlihy, A quorum-consensus replication method for abstract data types, ACM Transactions on Computer Systems (TOCS), v.4 n.1, p.32-53, Feb. 1986 [doi>10.1145/6306.6308]
	14	HWANG, D. J. Constructing a highly-available location service for a distributed environment. Tech. Rep. MIT/LCS/TR-410, MIT Lab. for Computer Science, Cambridge, Mass., Nov. 1987. Master's thes~s.
	15	Rivka Ladin , Barbara Liskov , Liuba Shrira, A technique for constructing highly available services, Algorithmica, v.3 n.3, p.393-420, 1988
	16	Rivka Ladin , Murray S. Mazer , Alec Wolman, A general tool for replicating distributed services, Proceedings of the first international conference on Parallel and distributed information systems, p.172, December 1991, Miami, Florida, United States
	17	LADIN, R. A method for constructing highly available services and a technique for distributed garbage collection. Ph.D. dissertation, MIT Dept. of Electrical Engineering and Computer Science, Cambridge, Mass., May 1989.
	18	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]
	19	Butler W Lampson, Designing a global name service, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.1-10, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10591]
	20	LAMPSON, B. W., AND STURGIS, H.E. Crash recovery in a distributed data storage system. Xerox Research Center, Palo Alto, Calif., 1979.
	21	Barbara Liskov , Rivka Ladin, Highly available distributed services and fault-tolerant distributed garbage collection, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.29-39, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10593]
	22	LISKOV, B., SCHEIFLER, R., WALKER, E., AND WEIHL, W. Orphan detection (extended abstract). In Proceedings of the 17th Internatwnal Symposium on Fault-Tolerant Computtng (Pittsburgh, Pa., July 1987). IEEE, New York, pp. 2 7
	23	B. Liskov , T. Bloom , D. Gifford , R. Scheifler , W. Weihl, Communications in the mercury system, Proceedings of the Twenty-First Annual Hawaii International Conference on Software Track, p.178-187, January 1988, Kailua-Kona, Hawaii, United States
	24	Barbara Liskov, Distributed programming in Argus, Communications of the ACM, v.31 n.3, p.300-312, March 1988 [doi>10.1145/42392.42399]
	25	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
	26	MILLS, D.L. Network time protocol (version 1) specification and implementation. DARPA- Internet Rep. RFC 1059. July 1988.
	27	MISHRA, S., PETERSON, L. L., AND SCHLICHTING, R. D. Implementing fault-tolerant objects using Psync. In Proceeding of the Eighth Symposium on Reltable Distributed Systems (Oct. 1989).
	28	Brian M. Oki , Barbara H. Liskov, Viewstamped replication: a general primary copy, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.8-17, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62549]
	29	B. M. Oki, VIEWSTAMPED REPLICATION FOR HIGHLY AVAILABLE DISTRIBUTED SYSTEMS, Massachusetts Institute of Technology, Cambridge, MA, 1988
	30	PARKER, D. S., POPEK, G. J., RUDISIN, G., STOUGHTON, A., WALKER, B., WALTON, E., CHOW, J., EDWARDS, D., KISER, S., AND KLINE, C. Detection of mutual inconsistency in distributed systems. IEEE Trans. Softw. Eng. SE-9, 3 (May 1983), 240-247.
	31	Frank B. Schmuck, The Use of Efficient Broadcast Protocols in Asynchronous Distributed Systems, Cornell University, Ithaca, NY, 1988
	32	Peter M. Schwarz , Alfred Z. Spector, Synchronizing shared abstract types, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.223-250, Aug. 1984 [doi>10.1145/989.1188]
	33	SKEEN, D. Non-blocking Commit Protocols. In Proceedings of the 3rd ACM SIGACT- SIGMOD Symposium on Principles of Database Systems (April 1984). ACM, New York.
	34	William E. Weihl, Distributed version management for read-only actions, IEEE Transactions on Software Engineering, v.13 n.1, p.55-64, Jan. 1987 [doi>10.1109/TSE.1987.232835]
	35	William Weihl , Barbara Liskov, Implementation of resilient, atomic data types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.244-269, April 1985 [doi>10.1145/3318.3319]
	36	Gene T.J. Wuu , Arthur J. Bernstein, Efficient solutions to the replicated log and dictionary problems, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.233-242, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806750]