Limitations of synchronous communication with static process structure in languages for distributed computing

ABSTRACT

Modules in a distributed program are active, communicating entities. A language for distributed programs must choose a set of communication primitives and a structure for processes. This paper examines one possible choice: synchronous communication primitives (such as rendez-vous or remote procedure call) in combination with modules that encompass a fixed number of processes (such as Ada tasks or UNIX processes). An analysis of the concurrency requirements of distributed programs suggests that this combination imposes complex and indirect solutions to common problems and thus is poorly suited for applications such as distributed programs in which concurrency is important. To provide adequate expressive power, a language for distributed programs should abandon either synchronous communication primitives or the static process structure.

REFERENCES

• 1: Gregory R. Andrews, Synchronizing Resources, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.405-430, Oct. 1981 [doi>10.1145/357146.357149]
• 2: 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]
• 3: 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]
• 4: Toby Bloom, Evaluating synchronization mechanisms, Proceedings of the seventh ACM symposium on Operating systems principles, p.24-32, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806566]
• 5: Per Brinch Hansen, Distributed processes: a concurrent programming concept, Communications of the ACM, v.21 n.11, p.934-941, Nov. 1978 [doi>10.1145/359642.359651]
• 6: Cook, R. P. "Starmod- a language for distributed programming". <i>IEEE Transactions on Software Engineering 6,</i> 6 (November 1980), 563--571.
• 7: Henry Ledgard, Reference Manual for the ADA Programming Language, Springer-Verlag New York, Inc., Secaucus, NJ, 1983
• 8: Jerome A. Feldman, High level programming for distributed computing, Communications of the ACM, v.22 n.6, p.353-368, June 1979 [doi>10.1145/359114.359127]
• 9: Gehani, N. "Concurrency in Ada and Multicomputers". <i>Computer Languages 7,</i> 2 (1982).
• 10: N. Gehani, Ada: an advanced introduction, Prentice-Hall, Inc., Upper Saddle River, NJ, 1983
• 11: Bruce K. Haddon, Nested monitor calls, ACM SIGOPS Operating Systems Review, v.11 n.4, p.18-23, October 1977 [doi>10.1145/850648.850650]
• 12: C. A. R. Hoare, Monitors: an operating system structuring concept, Communications of the ACM, v.17 n.10, p.549-557, Oct. 1974 [doi>10.1145/355620.361161]
• 13: 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]
• 14: Jean D. Ichbiah , Bernd Krieg-Brueckner , Brian A. Wichmann , John G. P. Barnes , Olivier Roubine , Jean-Claude Heliard, Rationale for the design of the Ada programming language, ACM SIGPLAN Notices, v.14 n.6b, p.1-261, June 1979 [doi>10.1145/956653.956654]
• 15: John C. Knight , John I. A. Urquhart, On the implementation and use of Ada on fault-tolerant distributed systems, ACM SIGAda Ada Letters, v.IV n.3, p.53-64, November-December 1984 [doi>10.1145/998410.998414]
• 16: Hugh C. Lauer , Roger M. Needham, On the duality of operating system structures, ACM SIGOPS Operating Systems Review, v.13 n.2, p.3-19, April 1979 [doi>10.1145/850657.850658]
• 17: B. Liskov and M. Herlihy. Issues in Process and Communication Structure for Distributed Programs. Proceedings of the Third IEEE Symposium on Reliability in Distributed Software and Database Systems, October, 1983.
• 18: 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]
• 19: Andrew Lister, The problem of nested monitor calls, ACM SIGOPS Operating Systems Review, v.11 n.3, p.5-7, July 1977 [doi>10.1145/850644.850645]
• 20: Mitchell, J., G., Maybury, W., and Sweet, R. Mesa language manual, version 5.0. CSL-79-3, Xerox Palo Alto Research Center, April, 1979.
• 21: Bruce Jay Nelson, Remote procedure call, 1981
• 22: Rashid, R. An inter-process communication facility for Unix. CMU-CS-81-124, Carnegie-Mellon University, 1980.
• 23: Schuman, S. A., Clarke, E. M., Nikolaou, C. N. Programming Distributed Applications in Ada: a First Approach. Proceedings of the 1981 Conference on Parallel Processing, Aug., 1981.
• 24: Segall, Z. and Rudolph, L. PIE - a programming and instrumentation environment for parallel processing. CMU-CS-85-128, Carnegie-Mellon University, 1985.
• 25: Wegner, P. and Smolka, S. "Processes, tasks, and monitors: a comparative study of concurrent programming primitives". <i>IEEE Transactions on Software Engineering 9,</i> 4 (July 1983), 39--59.
• 26: Welsh, J., and Lister, A. "A comparative Study of Task Communication in Ada". <i>Software - Practice and Experience 11</i> (1981), 257--290.
• 27: Yemini, S. On the suitability of Ada multitasking for expressing parallel algorithms. Proceedings of AdaTEC Conference on Ada, Oct., 1982.