THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1 DETERMINISM IN PARALLEL SYSTEMS Yaclav Rajlich CRLrTR-4-82 OCTOBER 1982 Room 1079, East Engineering Building Ann Arbor, Michigan 48109 USA Tel: (313) 763-8000 1This research was supported in part by the National Science Foundation under Grant No. MCS-78 00763. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agencies.

Determinism in Parallel Systems Vaclav Rajlich Department of Computer and Communication Sciences University of Michigan Ann Arbor, MI 48109 This research was supported in part by the National Science Foundation under Grant No. MCS-78 00763.

ABSTRACT The report deals with determinism in parallel systems, in which an event can be infinitely postponed. (the so-called "unfair systems" or systems with "starvation to death"). A hierarchy of deterministic, locally deterministic, and strongly locally deterministic systems is defined. It is proved that they form a proper hierarchy. The proof is based in part on a variant of Church-Rosser properties.

1. INTRODUCTION One of the important problems in parallel systems is the problem of determinism. The determinism in persistent systems was investigated in [3, 5]. In this paper, we deal with a generalization to the systems which are not persistent, i.e. systems where an event can be postponed, possibly infinitely. The systems of this kind were also called "unfair systems" or systems with "starvation to death". The techniques used here are an application of the ones published in [1]. The paper defines a hierarchy of deterministic, locally deterministic, and strongly locally deterministic systems and proves that they form a proper hierarchy. Parts of the proof are based on a variant of Church-Rosser properties, as investigated in [2] and other papers. (See [2] for a list of references.) Chapter 2 contains definitions of systems, traces, histories, and related notions, and Chapter 3 contains the main result of the paper. The result can be viewed as a criterion for determining a determinism in systems, and it is fully compatible with H-graphs [4] and similar definitions of systems. 2. SYSTEMS We shall start our formal exposition with the definition of systems: DEFINITION 2. 1. Let L be a set of locations, V a set of values, then s:L+V will be called a state. REMARK. As usual, we shall assume functions to be subsets of Cartesian product s C L x V such that;

- 2 - [i] for every a C L, there exists v C V such that <a,v>Es [ii] if <a,v>cs and <a,w>Es than v=w. Let L C L, then denote s/L = {<a,v>J<a,v>es and a ~ L1}. We say s(a)=v iff <a,v>cs. DEFINITION 2.2. Let L be a set of locations, V a set of values. Then e is a virtual event iff e = <eL, eR> (denoted e =>e ) and there exists L C L, such that eL:L +V, eR:L -*V. Then eL, eR are called left and right side of virtual event e, respectively. Denote Dom e = {a C LlIeL(a)AeR(a)}. DEFINITION 2.3. A system is a quadruple {L, V, so, E} where L is a set of locations, V is a set of values, so:L+V is the original state, and E is a set of virtual events. The state of the system undergoes changes, as defined in the following definitions: DEFINITION 2.4. Let s be a state, e be a virtual event such that eL C s. Then define a new state t = (s-eL)V eR and <s,t> is called actual event. The relationship of s, e, and t will be denoted as s'e=t. If eL C s, we also say e is scheduled in s. DEFINITION 2.5. Let S=<L,V,so,E> be a system. State s is reachable in the system S iff s=s or there exists a reachable state t such that t-e=s.

- 3 - Traces are a tool for description of the "dynamics" of the systems. They are sequences (finite or infinite) of virtual events which consecutively happened in the system. Formally, they are described in the following definitions: DEFINITION 2.6. Let A be an alphabet, then a finite nonempty word is a function w:{l,...,n}+A where n>l. An infinite word is a function w:{1,2,...}+A, and empty word XA=. Word is either is finite, infinite, or empty word. Length of a word Iwl is equal to 0, n, and w for empty, finite, and infinite words, respectively. Prefix of word w of length n (denoted w) is defined n in the following way: for n>Iwl|, nw=w, for n<lwl, w=wl{l,...,n}. Denote operation concatenation in the following way: If both v:{l,...,m}+A and w:{l,...,n}+A are finite words, then v-w is a function v.w:{l,...,m+n}4A so that v'wl{l,...,m}=v and for every i, for which l<i<n, v'w (i+m)=w(i). For empty word X,X.w=w.X=w. If w is infinite, then for every v, w-v=w. If v:{1.,,,.m}+A is finite, and w infinite, then v'w is an infinite word v-w:{1,2,....}A so that v'wI{l',...,m }=v and for every i>l, v'w(i+m)=w(i). Let u,v be words, then u is prefix of v (denoted u<v) iff there exists a word w such that u'w=v. Words v,w are called compatible (denoted v<>w) if either v<w or w<v. Let vOv1,v2... be words such that vO<vl<v2...<v, denote v=lim v.. It should be noted that the infinite words and the corresponding topology were extensively studied in [1]. We will use the following lemma of [1]: If v <v <..., then there exists a unique v such that v=lim v. o- 1 i+ i DEFINITION 2.7. Let <L, V, so, E> be a system, then trace is defined in the following way: Let s be a reachable state, then <s,X> is an empty trace. If <s,u> is

- 4 - a trace and there exists e C E such that e is scheduled in s'u, then <s, u-e> is a trace. Let <s, u >, <s, u >,... be a sequence of traces such that 1 2 u <u _..., then <s, lim u.> is atrace. Trace <s,u> is complete iff s=s and 1-2- 1 0o i+cx either u is infinite or s'u is a terminal state, i.e. for no e s E e is scheduled in s'u. If <s,u> is a trace and s is obvious from the context, then u will sometimes also be called trace. In the next definition, history is defined as a sequence of values held at a location a ~ L: DEFINITION 2.8. History of a ~ L in trace <s,u> (denoted h(a, <s,u>) is defined in the following way: (i) For empty trace, h(a,<s,X>)=s(a). (ii) Suppose that h(a, <s,u>) is defined and event e C E is scheduled in s-u. Then we have the following two cases: (a) a t Dom e (i.e. event e does not affect the value in location a), then h(a, <s,u-e>)=h(a, <s,u>). (b) a e Dom e, then h(a,<s,u'e>)=h(a,<s,u>). eR(a) (i.e. the new value will be added to the history). NOTE: if u <U2<... then h(a,<s,u >)<h(a,<s,u2>)... (iii) Let Ul<u2<..., then h(a,<s, lim u.>)=lim h(a,<s,u.>). We may state the following lemma: LEMMA 2.1. For every n<lh(a,<s,w>)I there exists m>n such that h(a, <s,w>)= h(a, <s, W>). PROOF By induction on m.

- 5 - 3. DETERMINISM This chapter contains several definitions of determinism in systems. Intuitively speaking, a system is deterministic if no matter what the particular choice of sequence of events, the histories of each location are compatible. In [3], a stronger definition of determinism requiring uniqueness of the history for each location was used. In this chapter, we shall also develop several criteria for determining whether a system is deterministic: strong local determinism and local determinism, and prove that strong local determinism, local determinism, and determinism form a proper hierarchy. DEFINITION 3.1. Let <L,V,s,E> be a system, and A C L be a subset of the set of locations L. The system is deterministic on A iff for every a C A and every couple of complete traces <s, u>,<s,v>, h(a, <s u>)<>h(a, <s,v>). 0 0'_ 0 DEFINITION 3.2. Let <L,V,s,E> be a system, and AC L be a subset of the set of locations L. The system is locally deterministic on A iff for every 1 1' a c A and every couple of finite traces u,v there exist traces u, v such that h(a, <s,u-u >)=h(a, <s, v-v >). DEFINITION 3.3. Let <L,V,s,E> be a system. It is strongly locally deterministic 0 on A if f for every a E A, for every reachable state s, and for all virtual events e,f which are scheduled in s, there exist traces x and y, where Iyj<l, h(a,<s,e-x>)=h(a, <s,f-y>), and s-e-x-=s'fy. We may illustrate the definitions by the following lemmas.

- 6 - LEMMA 3.1. Let B C A, then S is deterministic (locally deterministic, strongly locally deterministic) on A implies S is deterministic (locally deterministic, strongly locally deterministic) on B. PROOF Obvious. LEMMA 3.2. Let S=<L,V,s,E>. Then the system is strongly locally deterministic 0 on L if for every a c L, for every reachable state s, and for all virtual events e,f which are scheduled in s, there exist traces x and y where IYI<1, h(a,<s, e- x>)=h(a, <s,f-y>). PROOF The only thing we have to prove is that assumptions of Lemma 3.2 imply seex*= s-fey. Note that for every a c L, h(a, <s,e.x>) is finite, because f y is finite and Lemma 2.1. says Ih(a,<s,e'x>)I<Ie xI. Denote t(a) the last value of h(a, <s,e-x>), then t={<a, t(a)>IaEL}=s-f-y=s-e-x, which completes the proof. The main result of the paper is the following theorem. THEOREM 3.1. Let S be a system, A a subset of all locations. Then if S is strongly locally deterministic on A then S is locally deterministic on A and this implies S is deterministic on A. PROOF (i) First we will prove the strong local determinism implies local determinism.

- 7 - (The proof follows techniques of [21, Lemma 2.5.) Suppose S=<L,V,s,E> is a system, A C L, and S is strongly locally deterministic on A. Then we can prove the following statement: Let e be an event, v a finite trace 1 1 1 1 and a e A, then there exists traces x and y where ly<l, s'ex =sv'y, and h(a, <s,e-x >)=h(a, <s,v-y>). (The proof is by induction on Ivl). With this statement, we can prove local determinism. (The proof is by induction on lul). (ii) Now we will prove that the local determinism implies determinism. Suppose S is locally deterministic in A, but not deterministic on A. Then there exist two complete traces u,v and a ~ A such that it is not true that h(a, <s,u>)<> h(a, <s,v>). Then there exists m such that h(a, <s,u>)- h(a <s,v>) (*) m o m o Hence by Lemma 2.1, there exists k,n such that h(a, <s,u>)=h(a, <s ukU >) and h(a, <s,v>)=h(a, <s, v>). However, from the definition of the local m o on 1 1 1 determinism, there exist traces n, v such that h(a, <s, kU-u >)= h(a, <s, v v >) which is a contradiction with (*). o n The next two counter-examples will establish the facts that the hierarchy of Theorem 3.1 is the proper one, i.e. that the implications cannot be replaced by equivalences. EXAMPLE 3.1. This is an example of a system which is deterministic on A but not locally deterministic on A. Let S = <L,V,s,E> where L = {a,b}, A=L, V={O,1}, s = {<a,O>, <b,O>}, E={e1, e2} where e = <a,O> => <al>, e2 = {<a,O>.}I>{<a,l>,<b,l>}

- 8 - Then there are two complete traces <s, e > and <s, e >, where o 1 o 2 h(a, <s,e >)=<0,1 >, h(a, <s,e2>)=<O0,1> h(b, <s,el>)=<O>, h(b, <s,e2>)=<O,l>, hence the system is deterministic but not locally deterministic. EXAMPLE 3.2. This is an example of a system which is locally deterministic but not strongly locally deterministic. Let S = <L,V,s,E>, L = <a,b,c,d>, A=L, V={O,1}, 0 so = {<a,O>, <b,O>, <c,O> ) E = {el, e2 e3 e4 e5' e6} where e1 = <a,O> => <a,l>, e2 = <c,O> => <c,l>, e3 = {<a,l>, <b,O>} => {<a,l>, <b,l>}, e4 = {<b,l>, <c,O>l => {<b,l>, <c,l>}, e5 = {<b,O>, <cl>} => {<b,l>, <c,l>}, e = {<a,O>, <b,l>} => {<a,l>, <b,l>}. 6 Then this system is locally deterministic, but not strongly locally deterministic. In the following example, we shall give the illustration of a strongly locally deterministic system for which h(a, <s,u>)<>h(a, <s,v>)(u, and v 0 0 are complete traces), but h(a, <s,u>)/h(a, <s,v>). In another terminology, o 0 it is an illustration of a system which is unfair [3], or nonpersistent, or contains starvation to death. EXAMPLE 3.3 Let S = <L,V,s,E> where L = {a,b}, V = {O,1}, s = {<a,O>, <b,O>}, E = {e, e2, e3, e4} where el = <a,O> => <a,l>,

e2 = <a,l> => <a,O>, e3 = <b,O> => <b,l>, e4 = <b,l> => <b,O>. Then the system is strongly locally deterministic. Consider the following two complete traces: u = e1 2 le2..' v = e 34e3e4. 3 * Then h(a, <s,u>)=<Ol,O,,...>, while h(a, <s,v>) = <0>. 0

REFERENCES [1] L. Boasson, M. Nivat, Adherence of Languages, J. of Computer and System Science 20 (1980) 295-309. [2] G. Huet, Confluent Reductions: Abstract Properties and Applications to term Rewriting Systems, J. of the Assoc, Comput. M. 22 (1980) 797-821. [3] R.M. Karp, R.E. Miller, Parallel Program Schemata, J. of Computer and System Science 3, (1969) 147-195. [4] T. Pratt, Application of Formal Grammarsand Automata to Programming Language Definition, in Yeh, R.T. (ed.), Applied Computation Theory (Prentice-Hall, 1976). [5] V. Rajlich, Determinism in Relational Systems, in Claus, V., Ehrig, H., and Rosenberg, G., ed., Graph-Grammars and their Application to Computer Science and Biology, Lecture Notes in Computer Science 73, (Springer Verlag 1979) 401-408.