Replicated procedure call

ABSTRACT

A new mechanism for constructing highly available distributed programs is described. It combines remote procedure call with replication of program modules for fault tolerance. The set of replicas of a module is called a troupe. In a program constructed from troupes, what appears to the programmer as a single inter-module procedure call results in a replicated procedure call. A distributed program constructed in this way will continue to function as long as at least one member of each troupe survives. The semantics of replicated procedure calls and troupes are defined and algorithms are presented that support these semantics.

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	P. A. Lee , T. Anderson , J. C. Laprie , A. Avizienis , H. Kopetz, Fault Tolerance: Principles and Practice, Springer-Verlag New York, Inc., Secaucus, NJ, 1990
	2	Joel F. Bartlett, A NonStop kernel, Proceedings of the eighth ACM symposium on Operating systems principles, p.22-29, December 14-16, 1981, Pacific Grove, California, United States
	3	Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
	4	David Reeves Boggs. Internet Broadcasting. Ph.D. dissertation, Department of Electrical Engineering, Stanford University, Xerox PARC report number CSL-83-3, October 1983.
	5	Anita Borg , Jim Baumbach , Sam Glazer, A message system supporting fault tolerance, Proceedings of the ninth ACM symposium on Operating systems principles, p.90-99, October 10-13, 1983, Bretton Woods, New Hampshire, United States
	6	Liming Chen and Algirdas Avizienis. N-version programming: A fault-tolerance approach to reliability of software operation. Digest of Papers, FTCS-8: 8th Annual International Conference on Fault-Tolerant Computing, June 1978, pages 3-9.
	7	Eric C Cooper, Circus: A Replicated Procedure Call Facility, University of California at Berkeley, Berkeley, CA, 1984
	8	Eric C. Cooper. Mechanisms for Constructing Reliable Distributed Programs. Ph.D. dissertation, Computer Science Division, University of California, Berkeley, in preparation.
	9	Daniel H. Craft, Resource management in a decentralized system, Proceedings of the ninth ACM symposium on Operating systems principles, p.11-19, October 10-13, 1983, Bretton Woods, New Hampshire, United States
	10	Frank DeRemer , Hans Kron, Programming-in-the large versus programming-in-the-small, Proceedings of the international conference on Reliable software, p.114-121, April 21-23, 1975, Los Angeles, California
	11	Digital Equipment Corporation, Intel Corporation, and Xerox Corporation. The Ethernet: A Local Area Network. September 1980.
	12	R. S. Fabry, Dynamic verification of operating system decisions, Communications of the ACM, v.16 n.11, p.659-668, Nov. 1973 [doi>10.1145/355611.362535]
	13	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]
	14	Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
	15	Per Gunningberg. Voting and redundancy management implemented by protocols in distributed systems. Digest of Papers, FTCS-13: 13th International Symposium on Fault-Tolerant Computing, June 1983, pages 182-185.
	16	Maurice P. Herlihy , Barbara Liskov, A Value Transmission Method for Abstract Data Types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.527-551, Oct. 1982 [doi>10.1145/69622.357182]
	17	William Joy, Eric Cooper, Robert Fabry, Samuel Leffier, Kirk McKusick, and David Mosher. 4.2BSD System Manual. Computer Systems Research Group, Computer Science Division, University of California, Berkeley, July 1983.
	18	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]
	19	Leslie Lamport. The implementation of reliable distributed multiprocess systems. Computer Networks2, 2 (May 1978), pages 95-114.
	20	Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
	21	Butler W. Lampson and Howard E. Sturgis. Crash Recovery in a Distributed Data Storage System, Unpublished paper, Computer Science Laboratory, Xerox PARC, draft of June 1979.
	22	Butler W. Lampson. Replicated Commit. Unpublished paper, Computer Science Laboratory, Xerox PARC, January 1981.
	23	Butler W. Lampson , Eric E. Schmidt, Practical use of a polymorphic applicative language, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.237-255, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567090]
	24	Gérard Le Lann, Synchronization, Distributed Systems - Architecture and Implementation, An Advanced Course, p.266-283, January 1981
	25	R.E. Lyons and W. Vanderkulk. The use of triple-modular redundancy to improve computer reliability. IBM Journal of Research and Development6, 2 (April 1962), pages 200-209.
	26	J. Eliot B. Moss. Nested transactions and reliable distributed computing. Proceedings of the 2nd Symposium on Reliability in Distributed Software and Database Systems, July 1982, pages 33-39.
	27	Bruce Jay Nelson. Remote Procedure Call. Ph.D. dissertation, Computer Science Department, Carnegic-Mellon University, CMU report number CMU-CS-81-119, Xerox PARC report number CSL-81-9, May 1981.
	28	Derek C. Oppen and Yogen K. Dalal. The Clearinghouse: A Decentralized Agent for Locating Named Objects in a Distributed Environment. Xerox Office Products Division report number OPD-T8103, October 1981.
	29	W.H. Pierce. Adaptive vote-takers improve the use of redundancy. In Redundancy Techniques for Computing Systems, ed. Richard H. Wilcox and William C. Mann, Spartan Books, Washington, D.C., 1962, pages 229-250.
	30	Jon Postel. User Datagram Protocol. Information Sciences Institute, University of Southern California, RFC 768, August 1980.
	31	Jon Postel. Internet Protocol. Information Sciences Institute, University of Southern California, RFC 791, September 1981.
	32	Michael L. Powell , David L. Presotto, Publishing: a reliable broadcast communication mechanism, Proceedings of the ninth ACM symposium on Operating systems principles, p.100-109, October 10-13, 1983, Bretton Woods, New Hampshire, United States
	33	Michael L. Powell , Barton P. Miller, Process migration in DEMOS/MP, Proceedings of the ninth ACM symposium on Operating systems principles, p.110-119, October 10-13, 1983, Bretton Woods, New Hampshire, United States
	34	David P. Reed, Implementing atomic actions on decentralized data, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.3-23, Feb. 1983 [doi>10.1145/357353.357355]
	35	Fred B. Schneider. Fail-stop processors. Digest of Papers, Spring COMPCON 83: 26th IEEE Computer Society International Conference, February 1983, pages 66-70.
	36	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]
	37	J. von Neumann. Probabilistic logics and the synthesis of reliable organisms from unreliable components. In Automata Studies, ed. C. E. Shannon and J. McCarthy, Princeton University Press, 1956, pages 43-98.
	38	John H. Wensley. SIFT—Software implemented fault tolerance. Proceedings of the AFIPS 1972 Fall Joint Computer Conference, Volume 41, Part 1, December 1972. pages 243-253.
	39	Xerox Corporation. Courier: The Remote Procedure Call Protocol. Xerox System Integration Standard 038112, December 1981.