• absence of physical memory common to each computer -message exchange by the network A schematic structure of distributed system with distributed shared memory (DSM) is illustrated in Fig. 1 ([Cz 2012]).

Fig. 1 Assumptions and denotations:

• the computers work in parallel and are numbered 1,2,...,n

• reading and writing is governed by the memory manager of each computer;

• each message is accompanied by a global timestamp -a pair of computer number and compensated local timestamp;

• there is one critical section assuring mutually exclusive usage of a resource by the computers;

• no hardware or software failure happens during performing the mutual exclusion mechanism;

• computer number i keeps a vector r i = [r i1 ,r i2 ,...,r in ] of variables r ij allocated in its physical memory; it stores a global timestamp in the component r ii when requesting for the critical section;

• computer number i stores in r ij a copy of a global timestamp stored by the computer number j in r jj when it requested for the critical section;

• initially all variables r ij contain ∞ ;

• by min(r i ) the least value of the components in r i is denoted;

Fig. 2 shows a transition graph of the protocol based on global timestamps.

given by the transition graph of the protocol

• state of the whole system:

Attendant circumstances of the DSM usage:

-time consumptive transmission with data marshalling/unmarshalling; -necessity of time compensation (various frequency of computer clocks);

-overlapping (concurrent) memory accesses;

-possible data replication (cache);

They bring on the following consequences and problems to be tackled:

• a message directed to a group of receivers is delivered at different moments; hence memory locations alloted to this message may hold different content at a time;

• reading a memory location may fetch content different from that assigned to this location by its latest (?) (by global time) actualization (writing);

• suspension of the system activity for a period of any memory access would solve the above problems, thus to achieve data consistency but is unacceptable by reason of dramaic decrease of system performance; locking of access operations -too restrictive!

• need of a compromise between data consistency and effectiveness;

• weakening of data consistency -when this does not violate requirements of system's main objectives; example: frequent stocked goods actualization (written) of chain-stores network may be seen (read) different in different countries; data consistency maintenance -unnecessary effort!

• degrees of resignation from consistency to enhance effectiveness -bring on the so-called models of consistency;

• consistency models are usually explained informally -not always univocally; precise understanding them by users of DSM is one of disadvantages of DSM; hence need of their formal description;

• but formal description of consistency models must be based on a formal model of computing thus: (1) on actions and states as primary units of computing (2) on interleaving or non-interleaving ("true concurrency") model of computing;

• common descriptions of consistency models in DSM admit actions read and write from/to memory (fetch and update) as primary units and, informally, non-interleaving computing model;

• but read/write actions are too coarse to formally express memory consistency in the interleaving model along with retaining efficiency provided by true concurrency model;

• partial order of read/write not always is linearizable, i.e. their arrangement in sequence with retaining result of concurrent computation not always possible;

Notation: w(z,α) j , r(z,α) j -operations of writing and reading value α to/from variable (memory cell) z by computer j. Initially x = 0, y = 0. Scenario of not linearizable computing:

ã -global time precedence, -flow of write result r(y,0) 1 ã w(y,2) 2 ã r(x,0) 2 ã w(x,3) 1 ã r(y,0) 1 r(x,0) 2 ã w(x,3) 1 ã r(y,0) 1 ã w(y,2) 2 ã r(x,0) 2 contradictions!

Remarks, consequences:

• actions w(x,3) 1 , r(y,0) 1 , w(y,2) 2 , r(x,0) 2 cannot be interleaved in one sequence so that to retain result of the concurrent computation;

• scheduling protocol for linearization of accesses to DSM not always possible: serial equivalence to each computing scenario impossible;

• difficulty with formal description of consistency issues within the "true concurrency" model; expressions like "seen by processes", etc. are intuitive;

• instead of time-extensive actions read/write, let us take atomic (timeless) events of their beginnings and ends: ‫ݓ‬ ഥ(z,α) j , w(z,α) j , ‫ݎ‬ҧ (z,α) j , r(z,α) j ; finer granularity allows for applying interleaving model.

• assumption: a process completes reading and writing a cell with the same value as commenced; another process may change this value between these events.

Informally: a value read from any cell (variable) is either the initial value or the one written to it prior to the reading, and between these operations no writing to this cell occured. Note: "prior" is undefined since there is no global system clock. Let: Q = q 1 q 2 …q n ࢠ IL and

-either q i is the first such event in the interleaving Q -or there exists q k = w(x,a) g ࢠ W where k < i and there is no

DSM is strictly consistent iff every interleaving generated by the DSM protocols is strictly consistent.

Example of not strictly consistent interleaving: w(x,0) 2 w(x,1) 3 r(x,0) 1 r(x,1) 2

S = {P 1 , P 2 ,…, P N } -system of sequential programs running in computers numbered 1,2,…,N with DSM;

V j -set of variables of program P j allocated in the local memory of computer number j; D j -set of values the variables may assume;

Informally: (1) partial order of read/write operations always linearizable; (2) order of events in each interleaving is identical with order of their occurrences during execution in every individual program;

(3) all locations of the same variable in DSM contain identical value "seen" by every computer after its actualization (memory coherence).

Let Q j be a subsequence of an interleaving Q = q 1 q 2 …q n ࢠ IL resulted from removal of events different from events issued by program P j .

Q is sequentially consistent if for every j = 1,2,…,N, events in Q j occur in the order determined by programmer of the program P j .

DSM is sequentially consistent iff every interleaving generated by the DSM protocols is sequentially consistent and DSM is coherent.

Informally: causal consistency requires that every two causally dependent write actions, be "seen" (readout) in every process in the same order. That is, events q i , q j ∈ ∈ ∈ ∈ W , where q i , is a cause of effect q j , are "seen" by events q k , q l ∈ ∈ ∈ ∈R in the same process, then q k must precede q l .

Let RW = R ∪ ∪ ∪ ∪ W and ⊆ ⊆ ⊆ ⊆ RW × RW denote a causality relation defined by means of the following primary relations:

(1) iff p = q or p occurs before q in the same process;

(2) iff event q∈R terminates reading a certain value α of a variable x assigned to x by writing operation terminating with event p∈W ;

(3) iff event p∈R terminates reading a certain value α of a variable x needed for computing a value β = f(α) assigned afterwards to a variable y by writing operation terminating with event q∈W ;

(4) events p and q in (2) and (3) may occur in the same or different processes; they are called cause and effect respectively.

Causality relation is the least relation in the set RW satisfying:

(i) if or or then p q (ii) If p q and q r then p r

Events p, q are in the relation of cause and effect if p q.

Events p, q are independent (concurrent) if neither p q nor q p, write then q || p Interleaving Q = q 1 q 2 …q n ࢠ IL is causally consistent wrt. relation if for any two elements q i , q j ∈ ∈ ∈ ∈ W with q i q j the following holds:

If there are elements q k , q l ∈ ∈ ∈ ∈ R both belonging to the same process and such that and then But if for some q i , q j ∈ ∈ ∈ ∈ W with q i q j reverse succession holds then Q is causally inconsistent.

DSM is causally consistent iff every interleaving generated by the DSM protocols is causally consistent. q p process q p reading q p writing q p process q p reading q p writing k reading i q p l reading j q p l process k q p k process l q p Causal consistency and inconsistency may be represented by diagrams in Fig. 3 Informally: weaker than causal consistency model: if some values are written by the same process in a certain order and read ("seen") by another process, then the reading must take place in the same order as writing Formal definition is similar to causal consistency: causal dependence q i q j should be replaced with only.

Thus PRAM consistency and inconsistency may be represented by diagrams in Fig. 4.

While aforesaid models of data consistency ensure access to DSM by respective protocols supporting a chosen model without user's intervention, efficiency of the system may sometimes justify such intervention -for the prize of transparency, one of the desirable features of distributed systems. The weak consistency model provides users with the so-called synchronization variables, counterparts of semaphores in centralized systems. Access to them takes place as in the case of sequential consistency model -in any process they occur in the order specified by the program evoking this process. The users are provided with means to create critical sections applying e.g. protocol illustrated in Fig. 2. During execution of such critical section no other process may access data protected by this critical section until their actualization is finished. No data access is permitted until all previous accesses to synchronization variables are completed.