High level programming for distributed computing

ABSTRACT

Programming for distributed and other loosely coupled systems is a problem of growing interest. This paper describes an approach to distributed computing at the level of general purpose programming languages. Based on primitive notions of module, message, and transaction key, the methodology is shown to be independent of particular languages and machines. It appears to be useful for programming a wide range of tasks. This is part of an ambitious program of development in advanced programming languages, and relations with other aspects of the project are also discussed.

REFERENCES

• 1: Astrahan, M.M., et al. System R.: A relational approach to data base management. IBM Res. Lab., Feb. 1976.
• 2: Ball, E., Feldman, J., Low, J., Rashid, R., and Rovner, P. RIG, Rochester's intelligent gateway: System overview. IEEE Trans. Software Eng. SE-2, 4 (Dec. 1976), 321-328.
• 3: Ball, J., Williams, G., and Low, J. Preliminary ZEI':O language description. TR41, Comptr. Sci. Dept., U. of Rochester, Rochester, N.Y., Dec. 1978.
• 4: G.M. Birtwhistle , O.J. Dahl , B. Myhrhaug , K. Nygaard, Simula Begin, Chartwell-Bratt Ltd, 1979
• 5: Daniel G. Bobrow , Bertram Raphael, New Programming Languages for Artificial Intelligence Research, ACM Computing Surveys (CSUR), v.6 n.3, p.153-174, Sept. 1974 [doi>10.1145/356631.356632]
• 6: Bolt, Beranek and Newman, Inc. Interface message processor: Specifications for the interconnection of a host and an IMP. Rep. 1822, BBN, Cambridge, Mass., 1978 (revised).
• 7: Cohen, D. Specifications for the network voice protocol. ISI/ RR-75-39, Inform. Sci. Inst., U. of S. Calif., Los Angeles, March 1976.
• 8: Alan Demers , James Donahue , Glenn Skinner, Data types as values: polymorphism, type-checking, encapsulation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.23-30, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512764]
• 9: 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]
• 10: Feldman, J.A. A programming methodology for distributed computing (among other things). TR9, Comptr. Sci. Dept., U. of Rochester, Rochester, N.Y., Jan. 1977.
• 11: Feldman, J.A. Synchronizing distant cooperating processes. TR26, Comptr. Sci. Dept., U. of Rochester, Rochester, N.Y., 1977.
• 12: J. A. Feldman , J. R. Low , P. D. Rovner, Programming Distributed Systems, Proceedings of the 1978 annual conference, p.310-316, December 04-06, 1978, Washington, D.C., United States [doi>10.1145/800127.804118]
• 13: Feldman, J.A., Low, J.R., Swinehart, D., and Taylor, R. Recent developments in SAIL, an Algol-based language for artificial intelligence. Proc. AFIPS 1972 FJCC, AFIPS Press, Montvale, N.J., pp. 1193-1202.
• 14: Jerome A. Feldman , Paul D. Rovner, An ALGOL-based associative language, Communications of the ACM, v.12 n.8, p.439-449, Aug. 1969 [doi>10.1145/363196.363204]
• 15: Feldman, J.A., and Sproull, R.F. System support for the Stanford hand-eye system. Proc. Second Int. Joint Conf. on Artif. Intell., London, Sept. 1971.
• 16: Feldman, J.A., and Williams, G.J. Some comments on data types. TR28, Comptr. Sci. Dept., University of Rochester, Rochester, N.Y., 1977.
• 17: Floyd, R.W. Assigning meanings to programs. Proc. Symp. Appl. Math., Vol. 19, 1967, pp. 19-32.
• 18: Geschke, C.M., and Mitchell, J.G. On the problem of uniform references to data structures. IEEE Trans. on Software Eng. SE-3 (June 1975), 207-219.
• 19: Goldberg, A., and Kay, A., Eds. SMALLTALK-72 Instruction Manual. SSL 76-6, Xerox PARC, Palo Alto, Calif., 1976.
• 20: Hewitt, C.E., and Smith, B. Towards a programming apprentice. IEEE Trans. Software Eng. SE-I, 1 (March 1975), 26-45.
• 21: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 22: Hoare, C.A.R., and Wirth, N. An axiomatic definition of the programming language Pascal. Acta lnformatica 2 (1973), 335-355.
• 23: Jones, A.K., and Liskov, B.H. A language extension for controlling access to shared data. IEEE Trans. Software Eng. SE-2, 4 (December 1976).
• 24: B. W. Lampson , J. J. Horning , R. L. London , J. G. Mitchell , G. J. Popek, Report on the programming language Euclid, ACM SIGPLAN Notices, v.12 n.2, p.1-79, February 1977 [doi>10.1145/954666.971189]
• 25: Lampson, B.W., and Sturgis, H. Crash recovery in a distributed data storage system. Unpublished paper, Xerox PARC, submitted to Comm. A CM.
• 26: Roy Levin, Program structures for exceptional condition handling., 1977
• 27: 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]
• 28: Barbara Liskov , Stephen Zilles, Programming with abstract data types, Proceedings of the ACM SIGPLAN symposium on Very high level languages, p.50-59, March 28-29, 1974, Santa Monica, California, United States
• 29: London, R.L., Shaw, M., and Wulf, W.A. An introduction to the construction and verification of Alphard programs. IEEE Trans. Software Eng. SE-2, 4 (Dec. 1976), 253-264.
• 30: Low, J.R. Automatic Coding: Choice of Data Structures. Birkhauser-Verlag, Basel und Stuttgart, 1976.
• 31: James Low , Paul Rovner, Techniques for the automatic selection of data structures, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.58-67, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811540]
• 32: Mitchell, J.A., and Wegbreit, B. Schemes: A high level data structuring concept. CSL-77-1, Xerox PARC, Palo Alto, Calif., Jan. 1977.
• 33: McQuillan, J.M., and Walden, D.C. The ARPA network design decisions. Computer Networks 1, 5 (Aug. 1977), 243-290.
• 34: Susan Owicki , David Gries, Verifying properties of parallel programs: an axiomatic approach, Communications of the ACM, v.19 n.5, p.279-285, May 1976 [doi>10.1145/360051.360224]
• 35: Parnas, D.L., Shore, J.E., and Weiss, D.M. Abstract types defined as classes of variables. S1GPLAN Notices (ACM) 8, 2 (1976), 149- 154 (Vol. I1, 1976 Special Issue).
• 36: Gary L. Peterson , Michael J. Fischer, Economical solutions for the critical section problem in a distributed system (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.91-97, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803398]
• 37: John H. Reif, Data flow analysis of communicating processes, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.257-268, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567777]
• 38: John C. Reynolds, Syntactic control of interference, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.39-46, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512766]
• 39: Rovner, P.D. Message flow control in a local network. Comptr. Sci. Dept., U. of Rochester, Rochester, N.Y., 1978.
• 40: Selfridge, P.G. A flexible data structure for accessory image information. TR45, Comptr. Sci. Dept., U. of Rochester, Rochester, N.Y., Nov. 1978.
• 41: Robert F. Sproull , Elaine L. Thomas, A network graphics protocol, ACM SIGGRAPH Computer Graphics, v.8 n.3, p.27-51, Fall 1974 [doi>10.1145/988026.988030]
• 42: Sturgis, H.E. A postmortem for a time-sharing system. Ph.D. Diss., U. of California, Berkeley, 1974.
• 43: Daniel Carl Swinehart, Copilot: a multiple-process approach to interactive programming systems., 1974
• 44: Thomas, R.H. A solution to the update problem for multiple copy data bases which uses distributed control. Rep. No. 3340, Bolt, Beranek and Newman, Cambridge, Mass., July 1976.
• 45: Ben Wegbreit , Jay M. Spitzen, Proving Properties of Complex Data Structures, Journal of the ACM (JACM), v.23 n.2, p.389-396, April 1976 [doi>10.1145/321941.321957]

INDEX TERMS

Keywords:
assertions, distributed computing, messages, modules