Remote evaluation

ABSTRACT

A new technique for computer-to-computer communication is presented that can increase the performance of distributed systems. This technique, called remote evaluation, lets one computer send another computer a request in the form of a program. A computer that receives such a request executes the program in the request and returns the results to the sending computer. Remote evaluation provides a new degree of flexibility in the design of distributed systems. In present distributed systems that use remote procedure calls, server computers are designed to offer a fixed set of services. In a system that uses remote evaluation, server computers are more properly viewed as programmable processors. One consequence of this flexibility is that remote evaluation can reduce the amount of communication that is required to accomplish a given task. In this paper we discuss the semantics of remote evaluation and its effect on distributed system design. We also summarize our experience with a prototype implementation.

REFERENCES

• 1: CORPORATE Adobe Systems Inc., PostScript language reference manual (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 2: Andrew D. Birrell, Secure communication using remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.1-14, Feb. 1985 [doi>10.1145/214451.214452]
• 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: 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]
• 5: F. Warren Burton, Annotations to Control Parallelism and Reduction Order in the Distributed Evaluation of Functional Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.2, p.159-174, April 1984 [doi>10.1145/2993.357241]
• 6: Lisa A. Call , David L. Cohrs , Barton P. Miller, CLAM- an open system for graphical user interfaces, Conference proceedings on Object-oriented programming systems, languages and applications, p.277-286, October 04-08, 1987, Orlando, Florida, United States
• 7: DANIELS, D., SELINGER, P., HAAS, L., LINDSAY, B., MOHAN, C., WALKER, A., AND WILMS, P. An introduction to distributed query compilation in R*. In Distributed Databases: Proceedings of the 2nd International Symposium on Distributed Databases (Berlin, Sept. 1-3, 1982). North-Holland, Amsterdam, 1982, pp. 291-309.
• 8: EASTLAKE, III, D. E. Tertiary memory access and performance in the Datacomputer. In Proceedings of the 3rd International Conference on Very Large Data Bases (Tokyo, Oct. 6-8, 1977). ACM, New York, 1977, pp. 259-267.
• 9: Joseph R. Falcone, A programmable interface language for heterogeneous distributed systems, ACM Transactions on Computer Systems (TOCS), v.5 n.4, p.330-351, Nov. 1987 [doi>10.1145/29868.29870]
• 10: FARRELL, J. The Datacomputer--A network data utility. In First Berkeley Workshop on Distributed Data Management and Computer Networks (Berkeley, Calif., May, 1986). Lawrence Berkeley Lab., Berkeley, Calif., pp. 352-364.
• 11: R. Stockton Gaines, An operating system based on the concept of a supervisory computer, Communications of the ACM, v.15 n.3, p.150-156, March 1972 [doi>10.1145/361268.361274]
• 12: David Kenneth Gifford, Information storage in a decentralized computer system, 1981
• 13: GOSLING, J. Sundew: A distributed and extensible window system. In Proceedings of the 1986 Winter Usenix Technical Conference (Denver, Colo., Jan. 15-17, 1986). Usenix Assoc., El Cerrito, Calif., 1986, pp. 98-103.
• 14: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 15: G. Hallmark, Function request shipping in a database machine environment, Database Machines Sixth International Workshop, IWDM '89, Springer-Verlag New York, Inc., New York, NY, 1989
• 16: M. P. Herlihy, TRANSMITTING ABSTRACT VALUES IN MESSAGES, Massachusetts Institute of Technology, Cambridge, MA, 1980
• 17: 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]
• 18: HIKITA, S., KAWAKAMI, S., SAKAMOTO, A., AND MATSUSHITA, Y. An approach for customizing services of database machines. In Proceedings of the 5th International Workshop on Database Machines (Karuizawa, Japan, Oct. 5-8, 1987). Information Processing Society of Japan, 1987, pp. 305-318.
• 19: IBM CORPORATION. MVS/ESA SPL: Application development--extended addressability. IBM Form GC28-1854-0, IBM Corp., Armonk, N.Y., July 1988.
• 20: Eric Jul , Henry Levy , Norman Hutchinson , Andrew Black, Fine-grained mobility in the Emerald system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.109-133, Feb. 1988 [doi>10.1145/35037.42182]
• 21: KHOSHAFIAN, S., AND VALDURIEZ, P. Parallel execution strategies for declustered databases. In Proceedings of the 5th International Workshop on Database Machines (Karuizawa, Japan, Oct. 5-8, 1987). Information Processing Society of Japan, 1987, pp. 626-639.
• 22: Bruce G. Lindsay , Laura M. Haas , C. Mohan , Paul F. Wilms , Robert A. Yost, Computation and communication in R*: a distributed database manager, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.24-38, February 1984 [doi>10.1145/2080.357390]
• 23: 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]
• 24: Barbara Liskov , Alan Snyder , Russell Atkinson , Craig Schaffert, Abstraction mechanisms in CLU, Communications of the ACM, v.20 n.8, p.564-576, Aug. 1977 [doi>10.1145/359763.359789]
• 25: B Liskov , E Moss , A Snyder , R Atkinson , J C. Schaffert , T Bloom , R Scheifler, CLU reference manual, Springer-Verlag New York, Inc., New York, NY, 1984
• 26: MARILL, T., AND STERN, D. The Datacomputer--A network data utility. In AFIPS Conference Proceedings, Vol. 44, 1975 NCC (Anaheim, Calif., May 19-23, 1975). AFIPS, Reston, Va., 1975, pp. 389-395.
• 27: Bruce Jay Nelson, Remote procedure call, 1981
• 28: D. Notkin , W. G. Griswold, Extension and software development, Proceedings of the 10th international conference on Software engineering, p.274-283, April 11-15, 1988, Singapore
• 29: NOTK1N, D., HUTCHINSON, N., SANISLO, J., AND SCHWARTZ, M. Report on the ACM SIGOPS workshop on accommodating heterogeneity. Oper. Syst. Rev. 20, 2 (Singapore, Apr. 11-15, 1988). ACM, New York, 1988, 9-24.
• 30: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 31: SCHAUFLER, R. X11/NeWS design overview. In Proceedings of the Summer 1988 Usenix Conference (June 1988), pp. 23-35.
• 32: James William Stamos, Remote evaluation, Massachusetts Institute of Technology, Cambridge, MA, 1986
• 33: Steven R. Vegdahl, Moving structures between Smalltalk images, Conference proceedings on Object-oriented programming systems, languages and applications, p.466-471, September 29-October 02, 1986, Portland, Oregon, United States
• 34: WEINREB, D., AND MOON, D. Lisp Machine Manual. MIT Artificial Intelligence Laboratory, Cambridge, Mass., 1981.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Design, Languages, Performance