Variants of Determinacy in Parallel Program Schemata

Article type: Research Article

Authors: Kelter, Udo

Affiliations: Universität Dortmund, Fachbereich Informatik, Postfach 500500, D-4600 Dortmund 50, West Germany

Abstract: Systems which use parallel processing to speed up response times are normally required to be determinate. Parallel program schemata are formal models of parallel systems which serve to exactly define determinacy. Three variants of determinacy have frequently been used in the literature: Two “semantic” ones, which refer to the final contents of variables and to the sequences of contents, and a “syntactic” one, which is based upon the notion of conflict. Variants of determinacy can be derived with a universal definition of determinacy (as presented in [K73]) which uses a parameter, namely an equivalence relation on computations. Each of the above variants corresponds to a certain equivalence relation. The main aim of this paper is to investigate the role of “read-only”-operations, e.g. pure tests. Results of tests do not matter for both semantic forms of determinacy, whereas they are relevant for the syntactic form. We will snow that different variants of semantic and syntactic determinacy can be obtained by judging read-only operations as relevant or not.

Keywords: determinacy, equivalence of computations, program schemata

DOI: 10.3233/FI-1987-10302

Journal: Fundamenta Informaticae, vol. 10, no. 3, pp. 225-246, 1987