Modeling concurrency with partial orders. (English) Zbl 0622.68034

Concurrency has been expressed variously in terms of formal languages (typically via the shuffle operator), partial orders, and temporal logic, inter alia. In this paper we extract from these three approaches a single hybrid approach having a rich language that mixes algebra and logic and having a natural class of models of concurrent processes. The heart of the approach is a notion of partial string derived from the view of a string as a linearly ordered multiset by relaxing the linearity constraint, thereby permitting partially ordered multisets or pomsets. Just as sets of strings form languages, so do sets of pomsets form processes. We introduce a number of operations useful for specifying concurrent processes and demonstrate their utility on some basic examples. Although none of the operations is particularly oriented to nets it is nevertheless possible to use them to express processes constructed as a net of subprocesses, and more generally as a system consisting of components. The general benefits of the approach are that it is conceptually straightforward, involves fewer artificial constructs than many competing models of concurrency, yet is applicable to a considerably wider range of types of systems, including systems with buses and ethernets, analog systems, and real-time systems.


68Q65 Abstract data types; algebraic specification
68N25 Theory of operating systems
Full Text: DOI


[1] V. R. Pratt, Some Constructions for Order-Theoretic Models of Concurrency,Proc. Conf. on Logics of Programs, Springer-Verlag LNCS 193, Brooklyn (1985). · Zbl 0565.68014
[2] T. Denvir, W. Harwood, M. Jackson, and M. Ray,The Analysis of Concurrent Systems, Proc. of a Tutorial and Workshop, September 1983, Cambridge University, LNCS 207, Springer-Verlag (1985).
[3] C. Barney, Logic Designers Toss Out the Clock, Electronics58(49):42-45 (December 1985).
[4] J. Gischer, Partial Orders and the Axiomatic Theory of Shuffle, Ph.D. Thesis, Computer Science Dept., Stanford University (December 1984).
[5] I. Greif, Semantics of Communicating Parallel Processes, Ph.D. Thesis, Project MAC Report TR-154, MIT (September 1975).
[6] E. Best, C. Fernandez, and H. Plünnecke, Concurrent Systems and Processes, Final Report on the Foundational Part of the Project BEGRUND, FMD-Studien Nr. 104, GMD, Sankt Augustin, FDR (March 1985).
[7] W. Reisig,Petri Nets: An Introduction Springer-Verlag (1985).
[8] G. Winskel, Events in Computation, Ph.D. Thesis, CST-10-80, Dept. of Computer Science, University of Edinburgh (1980).
[9] G. Winskel, A New Definition of Morphisms on Petri Nets, Proc. CMU/SERC Workshop on Analysis of Concurrency, Springer-Verlag LNCS 196, Pittsburgh (1984).
[10] G. Winskel, Categories of Models for Concurrency, Technical Report No. 58, University of Cambridge, England, (December 1984).
[11] S. S. Pinter and P. Wolper, A Temporal Logic to Reason about Partially Ordered Computations,Proc. 3rd ACM Symp. on Principles of Distributed Computing, pp. 28-37, Vancouver (August 1984).
[12] L. Lamport, On Interprocess Communication, DEC Systems Research Center, Report No. 8 (1985).
[13] J. F. A. K. Van Benthem,The Logic of Time, D. Reidel (1983). · Zbl 0508.03008
[14] G. J. Whitrow,The Natural Philosophy of Time, 2nd ed., Oxford University Press (1980). · Zbl 0506.00019
[15] Mazurkiewicz, Traces, Histories, Graphs: Instances of a Process Monoid,Proc. Conf. on Mathematical Foundations of Comput. Sci., Springer-Verlag LNCS 176 (1984).
[16] V. R. Pratt, On the Composition of Processes,Proc. of the Ninth Annual ACM Symp. on Principles of Programming Languages (January 1982).
[17] J. D. Brock and W. B. Ackerman, Scenarios: A Model of Non-Determinate Computation. In:Formalization of Programming Concepts, J. Diaz and I. Ramos, Eds., Springer-Verlag LNCS 107, New York, pp. 252-259 (1981).
[18] G. Kahn, The Semantics of a Simple Language for Parallel Programming,IFIP 74, North-Holland, Amsterdam (1974). · Zbl 0299.68007
[19] G. Kahn and D. B. MacQueen, Coroutines and Networks of Parallel Processes,IFIP 77 993-998, North-Holland, Amsterdam (1977). · Zbl 0363.68076
[20] V. R. Pratt, The Pomset Model of Parallel Processes: Unifying the Temporal and the Spatial,Proc. CMU/SERC Workshop on Analysis of Concurrency, Springer-Verlag LNCS 197, Pittsburgh (1984). · Zbl 0589.68025
[21] R. Milner, Calculi for Synchrony and Asynchrony,Theor. Comput. Sci. 25:267-310 (1983). · Zbl 0512.68026 · doi:10.1016/0304-3975(83)90114-7
[22] A. Pnueli, The Temporal Logic of Programs,18th IEEE Symp. on Foundations of Comput. Sci., pp. 46-57 (October 1977).
[23] D. Gabbay, A. Pnueli, S. Shelah, and J. Stavi, On the Temporal Analysis of Fairness,Proc. of the 7th Annual ACM Symp. on Principles of Programming Languages, pp. 163-173 (January 1980).
[24] V. R. Pratt, Two-Way Channel with Disconnect, in Denviret al. (3) section 3.1.3 (1983).
[25] L. F. Monteiro and F. C. N. Pereira, Outline of a Sheaf-theoretic Approach to Concurrency,Proc. IEEE Symp. on Logic in Comput. Sci., Boston (July 1986).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.