×

Structure of concurrency. (English) Zbl 0814.68061

A new approach to the semantic of concurrency is proposed. It is motivated by the remark that the causal order of events is sometimes insufficient to describe adequately some aspect of concurrent behaviour, this happens for example in the case of systems with priority and for Petri nets with inhibitor arcs. Three levels of description are distinguished. At the bottom level – called observation level – the system is represented by partial orders with the ordering giving precedence of events and incomparability denoting simultaneity. Relations between observations and interval orders are thoroughly examined. The next level discussed is the invariant level. Roughly, invariants are relations that are universally satisfied over the set of observations of a system. Further developments of the theory lead to the notions of histories and paradigms, where paradigms are intended to capture structural properties of histories.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Abraham, U.; Ben-David, S.; Magidor, M., On global-time and inter-process communication, (), 311-323, Leicester 1990, Workshops in Computing
[2] Allen, A.F.; Kentz, H.A., A model of naive temporal reasoning, (), 251-268
[3] Anger, F.D., On Lamport’s interprocess communication model, ACM to-plas, 11, 3, 404-417, (1989)
[4] Best, E.; Devillers, R., Concurrent behaviour: sequences, processes and programming languages, (1985), GMD Bonn, GMD-Studien Nr. 99 · Zbl 0567.68035
[5] Best, E.; Koutny, M., Petri net semantics of priority systems, Theoret. comput. sci., 94, 141-158, (1992) · Zbl 0753.68059
[6] Degano, P.; Montanari, U., Concurrent histories; a basis for observing distributed systems, J. comput. systems sci., 34, 422-467, (1987) · Zbl 0619.68017
[7] Fishburn, P.C., Intransitive indifference with unequal indifference intervals, J. math. psych., 7, 144-149, (1970) · Zbl 0191.31501
[8] Fishburn, P.C., Interval orders and interval graphs, (1985), Wiley New York · Zbl 0216.30401
[9] Fräisse, R., Theory of relations, (1986), North-Holland Amsterdam · Zbl 0593.04001
[10] F. Franek, private communication, 1989.
[11] Fulkerson, D.R.; Gross, O.A., Incidence matrics and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001
[12] Gaifman, H.; Pratt, V., Partial order models of concurrency and the computation of function, Proc. symp. on logic in computer science, 72-85, (1987)
[13] R. Gerber and I. Lee, A resource-based prioritized bisimulation for real-time systems, Inform. and Comput., to appear. · Zbl 0942.68622
[14] Gilmore, P.C.; Hoffman, A.J., A characterization of comparability graphs and interval graphs, Canad. J. math., 16, 539-548, (1964) · Zbl 0121.26003
[15] Hoare, C.A.R., Communicating sequential processes, (1985), Prentice-Hall Englewood Cliffs, NJ · Zbl 0637.68007
[16] Hooman, J.J.M.; Ramesh, S.; de Roever, W.P., A compositional axiomatisation of safety and liveness properties for statecharts, (), 242-261, Leicester 1990, Workshops in Computing
[17] Janicki, R., A formal semantics for concurrent systems with a priority relation, Acta inform., 24, 33-55, (1987) · Zbl 0589.68021
[18] Janicki, R.; Koutny, M., Observing concurrent histories, (), 133-142, York 1989
[19] Janicki, R.; Koutny, M., Invariants and paradigms of concurrency theory, (), 59-74
[20] Janicki, R.; Koutny, M., Invariant semantics of nets with inhibitors arcs, (), 317-331
[21] Janicki, R.; Koutny, M., Structure of concurrency II, () · Zbl 0814.68061
[22] Janicki, R.; Lauer, P.E., On the semantics of priority systems, (), 150-156
[23] Katz, S.; Peled, D., Interleaving set temporal logic, Vancouver, 6th ACM symp. on principles of distributed computing, 178-190, (1987)
[24] Katz, S.; Peled, D., Defining conditional independence using collapses, (), 262-280, Leicester 1990, Workshops in Computing
[25] Kuratowski, K.; Mostowski, A., Set theory, (1976), North-Holland Amsterdam · Zbl 0337.02034
[26] Lamport, L., What it means for a concurrent program to satisfy a specification: why no one has specified priority, (), 78-83, New Orleans Louisiana
[27] Lamport, L., The mutual exclusion problem. part I - A: theory of interprocess communication: part II: statements and solutions, J. ACM, 33, 313-326, (1986) · Zbl 0627.68017
[28] Lamport, L., On interprocess communication. part I: basic formalism; part II: algorithms, Distributed comput., 1, 77-101, (1986) · Zbl 0598.68022
[29] Lauer, P.E.; Shields, M.W.; Cotronis, J.Y., Formal behavioural specification of concurrent systems without globality assumptions, () · Zbl 0481.68012
[30] Lengauer, C.; Hehner, E.C.R., A methodology for programming with concurrency: an informal presentation, Sci. comput. programming, 2, 1-18, (1982) · Zbl 0491.68005
[31] Mazurkiewicz, A., Concurrent program schemes and their interpretations, DAIMI-PB-78, (1977), Aarhus University
[32] Mazurkiewicz, A., Trace theory, (), 297-324
[33] Milner, R., A calculus of communicating systems, () · Zbl 0452.68027
[34] Milner, R., Calculi for synchrony and asynchrony, Theoret. comput. sci., 25, 264-310, (1983) · Zbl 0512.68026
[35] Monk, J.D., Mathematical logic, (1976), Springer Berlin · Zbl 0354.02002
[36] Nielsen, M.; Engberg, U.; Larsen, K.S., Fully abstract models for a process language with refinement, (), 523-548
[37] Peterson, J.L., Petri net theory and the modeling of systems, (1981), Prentice-Hall Englewood Cliffs, NJ
[38] Petri, C.A., Kommunikaten mit automaten, ()
[39] G. Plotkin and V. Pratt, Teams Can See Pomsets, unpublished memo, available electronically as pub/pp2.tex by anonymous FTP from Boole.Stanford.EDU.
[40] Pratt, V., Modelling concurrency with partial orders, Int. J. parallel programming, 15, 33-71, (1986) · Zbl 0622.68034
[41] Reisig, W., Petri nets, (1985), Springer Berlin · Zbl 0521.68057
[42] Rozenberg, G.; Verraedt, R., Subset languages of Petri nets, Theoret. comput. sci., 26, 301-323, (1983) · Zbl 0531.68029
[43] Salwicki, A.; Müldner, T., On algorithmic properties of concurrent programs, (), 169-197
[44] Shields, M.W., Concurrent machines, Comput. J., 28, 449-465, (1985) · Zbl 0573.68026
[45] Szpilrajn-Marczewski, E., Sur l’extension de l’ordre partial, Fundam. math., 16, 386-389, (1930) · JFM 56.0843.02
[46] van Glabbeek, R.; Vaandrager, F., Petri net models for algebraic theories of concurrency, (), 224-242
[47] Vogler, W., Failure semantics based on interval semiwords is a congruence for refinement, (), 285-297
[48] Wiener, N., A contribution to the theory of relative position, Proc. camb. philos. soc., 17, 441-449, (1914) · JFM 45.1150.10
[49] Winskel, G., Event structure semantics for CCS and related language, (), 561-567
[50] Zielonka, W., Notes on finite asynchronous automata, Informatique thèorique et applications, 21, 99-135, (1987) · Zbl 0623.68055
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.