On the composition of processes

ABSTRACT

We describe a model of net-connected processes that amounts to a reformulation of a model derived by Brock and Ackerman from the Kahn-McQueen model of processes as relations on streams of data. The reformulation leads directly to a straightforward definition of process composition. Our notion of processes and their composition constitutes a natural generalization of the notion of functions and their composition. We apply this definition of process composition to the development of an algebra of processes, which we propose as supplying a formal semantics for a language whose domain of discourse includes nets of interconnected processes. This in turn leads us to logics of such nets, about which we raise three open and fundamental problems: existence of a finite basis for the operations of the language, finite axiomatizability of the equational theory, and decidability of this theory. A natural generalization of the model deals with the time complexity of computations.

REFERENCES

• 1: Karl R. Abrahamson, Modal Logic of Concurrent Nondeterministic Programs, Proceedings of the International Sympoisum on Semantics of Concurrent Computation, p.21-33, July 02-04, 1979
• 2: W. B. Acherman , J. B. Dennis , William B Ackerman, VAL- ORIENTED ALGORITHMIC LANGUAGE, PRELIMINARY REFERENCE MANUAL, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 3: Brock, J.D. and W.B. Ackerman, An Anomaly in the Specifications of Nondeterminate Packet Systems, Computations Structures Group Note CSG-33, MIT-LCS, Nov. 1977.
• 4: J. Dean Brock , William B. Ackerman, Scenarios: A Model of Non-Determinate Computation, Proceedings of the International Colloquium on Formalization of Programming Concepts, p.252-259, April 19-25, 1981
• 5: Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
• 6: Harel, D., Kozen, D., Parikh, R., Process Logic: Expressiveness, Decidability, Completeness, IBM Research Report, April 1980.
• 7: Hewitt, C. and H.G. Baker, Laws for Communicating Parallel Processes, IFIP 77, 987--992, North-Holland, Amsterdam, 1977.
• 8: 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]
• 9: Kahn, G., The Semantics of a Simple Language for Parallel Programming, IFIP 74, North-Holland, Amsterdam, 1974.
• 10: Kahn, G. and D.B. MacQueen, Coroutines and Networks of Parallel Processes, IFIP 77, 993--998, North-Holland, Amsterdam, 1977.
• 11: Kleene, S.C., Representation of Events in Nerve Nets, in Automata Studies, (eds. Shannon, C.E. and J. McCarthy), 3--40, Princeton University Press, Princeton, NJ, 1956.
• 12: {10a} Lynch, N.A. and M.H. Fischer, On Describing the Behavior and Implementation of Distributed Systems, Theoretical Computer Science,13, 17--43, 1981.
• 13: MacQueen, D.B., Models for Distributed Computing, Technical Report 351, INRIA, Paris, 1979.
• 14: Milner, R., Synthesis of Communicating Behavior, 7th Symp. on Math. Found. of Computer Science, Zakopane, Poland, Sept. 1978.
• 15: R. Milner, A Calculus of Communicating Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 16: Parikh, R., A Decidability Result for a Second Order Process Logic. Proc. 19th IEEE Symp. on Foundations of Computer Science, 177--183, Ann Arbor, Oct. 1978. Also M.I.T. Laboratory for Computer Science Technical Memorandum No. 112, September 1978.
• 17: {14a} Paterson, R. and J. Staples, An algebra of processes with a finite basis, Technical Report No. 29. Dept. of Comp. Sci., U. of QLD, St. Lucia, QLD., Australia, June 1981.
• 18: Petri, C.A., Introduction to General Net Theory, Springer-Verlag Lecture Notes in Computer Science, to appear 1981.
• 19: Pnueli, A., The Temporal Logic of Programs, 18th IEEE Symposium on Foundations of Computer Science, 46--57. Oct. 1977.
• 20: V. R. Pratt, Process logic: preliminary report, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.93-100, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567761]
• 21: V. R. Pratt, Dynamic algebras and the nature of induction, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.22-28, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804649]
• 22: Redko, V.N., On Defining Relations for the Algebra of Regular Events, (Russian), Ukrain. Mat. Z., 16, 120--126, 1964.
• 23: Segerberg, K., A Completeness Theorem in the Modal Logic of Programs, Preliminary report. Notices of the AMS, 24, 6, A-552. Oct. 1977.