Abstract
A simple model of concurrent computations is presented in which disjoint instructions /processes/ of program are executed concurrently by processors /in a sufficiently large number/ under a shared memory environment. The semantics of such a program specifies the tree of configuration sequences which are acceptable as possible computations of the program.
We do not agree with the existing literature /e.g. [2]/ that every sharing one processor among processes can be conceived as a concurrency. We claim that the other meaning of concurrency can be defined as well. The difference between these two meanings turns out to be essential. We do not assume that each configuration is obtained from its predecessor in the computation by exactly one processor performing an atomic step /assignment or test/ in a process. On the contrary, we assume that a processor cannot be delayed during his activities. The length of a step is indefinite, it must be finite only. This reflects various speeds of processors. Hence, for the configuration in which several processors are able to start the execution of their subsequent steps, a maximal number of atomic steps will be started, the choice being nondeterministic.
We discuss semantical phenomena of concurrent computations. It is argued that they can be expressed in the language of an algorithmic logic. The problem of complete axiomatization of the latter remains open. The comparison with another model of concurrency — Petri nets — is given and, we hope, it is interesting. For, our approach offers a structured /algebraic/ restriction of the language of nets and new variants of semantics. From the results obtained in the theory of vector addition systems we learn an important property of concurrent computations — there is no faithful one processor simulation of them.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Burkhard,H.D., Ordered Fairing in Petri Nets. Manuscript, January 1980, Humboldt Universität, see also: On Priorities of Parallelism: Petri Nets under the Maximum Firing Strategy, to appear in Lecture Notes in Comp. Sci., Proc. Poznań 1980, Algorithmic Logic and LOGLAN.
Hansen,P.B., Operating System Principles; Prentice Hall 1973.
Harel,D.,Pratt,V., Nondeterminism in Logics of Programs, Proc. 5-th Ann. ACM Symp. on Principles of Programming Lang. 203–213, Tucson, Arizona, Jan. 1978
Grabowski, Jan, Miscellaneous results on vector addition systems, Proc. FCT 79, Akademie Verlag, Berlin 1979
Mirkowska,G., Algorithmic logic with concurrent programs, manuscript, Nov., 1978.
—, PAL-propositional algorithmic logic, manuscript
—, Algorithmic logic with nondeterministic programs, ICS PAS reports no 343, 1979 Warsaw, see also Fundamenta Informaticae, vol. III Number 1 /1980/ pp. 45–64.
Mazurkiewicz,A., Concurrent program schemes and their interpretations, Proc. Arhus Workshop on Verification of Parallel Processes, 1977
Moalla, M., Pulon, J., Sifakis, J., Synchronized Petri Nets: A model for the Description of Non-Autonomous Systems, in Proc. MFCS '78 Conf. Zakopane, Lecture Notes in Comp.Sci. vol. 64 pp. 374–384, 1978, Berlin.
Müldner,T., On the semantics of parallel programs, ICS PAS reports no 348, 1979 Warsaw
—, On the synchronizing tools, ibidem, no 357
—, Implementation and properties of certain tool..., ibidem no 356,Papers [6,10,11,12] will appear in Fund.Informatic.
Pnueli, A., The temporal semantics of concurrent programs, in Semantics of concurrent computations, Proc. Evian Conf., Lecture Notes on Comp. Sci. vol. 70, 1–20, 1979 Berlin
Valk, R, — On the computational power of extended Petri nets, in Proc. MFCS 78 Conf. Zakopane, Lecture Notes in Comp.Sci. vol. 64, pp. 526–535, 1978, Berlin
Winkowski, J., An algebraic approach to concurrence, in Proc MFCS 79 Conf. Olomouc, Lecture Notes in Comp. Sci. vol. 74 pp. 523–532, 1979, Berlin.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1981 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Salwicki, A., Müldner, T. (1981). On the algorithmic properties of concurrent programs. In: Engeler, E. (eds) Logic of Programs. Logic of Programs 1979. Lecture Notes in Computer Science, vol 125. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-11160-3_6
Download citation
DOI: https://doi.org/10.1007/3-540-11160-3_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-11160-3
Online ISBN: 978-3-540-38631-5
eBook Packages: Springer Book Archive