03.05.23 1

Specificarea sistemelor de programe

Tudor Bălănescu

An 3, sem. 1 specializarea Informatică

03.05.23 2

Introducere• Specificare: descrierea detaliilor structurale şi de comportament ale unui

produs.– Sistemele mari de programe sunt descompuse în subsisteme.– Pentru ca subsistemele să poată fi dezvoltate independent, este necesară

definirea interfeţelor de comunicare între subsisteme. • Exemplu: specificarea printr-un set de clase de obiecte, stabilite de comun acord cu

toţi dezvoltatorii de subsisteme– Specificare neformalizată (mai mare grad de ambiguitate, incompletitudine si

inconsistenţă)– Specificare formalizată: (neambiguă şi mai completă)

• Completează (însoţeşte) specificarea neformalizată• Facilitează analiza proprietăţilor de consistenţă şi de neambiguitate ale specificării

neformalizate– Tipuri de specificări formale:

• Algebrică• Logică• Fundamentată pe teoria mulţimilor• Vienna Development Method• Notaţia (limbajul) Z• etc.

03.05.23 3

Specification techniques (Ian Sommerville, [SE7thed] )

• Algebraic specification– The system is specified in terms of its operations and their relationships.

• Model-based specification– The system is specified in terms of a state model that is constructed

using mathematical constructs such as sets and sequences. Operations are defined by modifications to the system’s state.

Formal specification languagesSequential Concurrent

Algebraic Larch (Guttag et al., 1993) },

OBJ (Futatsugi et al., 1985)} Lotos (Bolognesi and Brinksma,

1987)}, Model-based Z (Spivey, 1992)}

VDM (Jones, 1980)}

B (Wordsworth, 1996)}

CSP (Hoare, 1985)}

Petri Nets (Peterson, 1981)}

03.05.23 4

Specificare algebrică

• Adecvată definirii interfeţelor dintre subsisteme: clasele şi tipurile abstracte de date sunt descrise prin relaţii între operaţii algebrice.

(Guttag, 1977)– Limbaje de specificare algebrică:

• OBJ • Larch• Common Algebraic Specification Language (CASL)

Algorithms + Data Structures = ProgramsN. Wirth, Prentice Halls, 1976

Abstract Data Types (ADT)

Operaţii

abstractizare

Operaţii algebrice + Sorturi= Algebre (multisortate)Algebrele, abstractizări ale programelor

03.05.23 5

Abstract Data Types (ADTs)

• Sub-system interfaces are often defined as a set of abstract data types or objects Each sub-system implements these interfaces and all subsystem access is through the interfaces.

• Abstract data types or ADTs are datatypes described in terms of the operations they support—their interface—rather than how they are implemented.

• ADTs are written in OOP languages by abstract classes or interfaces.• Formally, an ADT is a theory (signature + axioms)• Like any theory, an ADT may have more than one implementation (model)• Users of an ADT are aware of the interface, but not of the implementation.

– When done correctly, a totally different implementation could be used without any need to modify existing code using the ADT

03.05.23 6

Example: an Algebraic spec for a Data Structure Type

Signature :• AbstractType: List[G]• Sort: DS, • Imports: Boolean• Functions (operations):

– new:<> → DS (or new:DS ) constructor – add: DS x G→DS constructor– remove: DS →DS modifier– item: DS →G interogator– empty: DS→ Boolean interogator

• What kind of list (stack, queue etc.)?We need a semantics.(a set of axioms or equations)• By describing the relationships between operations one can infer the semantics of each operation.

We include nothing about implementation for avoiding

overspecification

03.05.23 7

Axiom construction heuristic for ADTs (1/?)

John Guttag developed a simple algorithm to use:1. Divide the operations into 3 sets: constructors,

modifiers and interogators (behaviors).2. For each modifier operation M create an

equation for each constructor C:M(C(V1, ..., Vn)) = ?where V1, ..., Vn are free variables.

3. For each behavior operation B create an equation for each constructor C:B(C(V1, ..., Vn)) = ?where V1, ..., Vn are free variables.

4. Fill in the right-hand sides of the equations.

03.05.23 8

Axiom construction heuristic for ADTs (2/?)

• Identify constructors (generators):operations of the specified type that are sufficient to construct any specific instance of the type – for List[G]

• new• add(indeed: any new element added to DS is of the form new, add(new,g) etc.)

• Identify modifiers: does not produce any new values, but modifies the given ones– for List[G

• remove.

• Identify interogators:an operation that produces an element of a sort other than the specified type– for List[G

• item• empty

1

03.05.23 9

Axiom construction heuristic for ADTs (3/?)• enumerate left-hand-sides (LHS) for axioms by all combinations of

– modifier (constructor…) and– Interogator (constructor…)

• examine each left-hand-side so produced and construct a right-hand-side (RHS) that describes an equivalent, but differently stated, structure.

• each axiom is an equation: LHS = RHS

The RHS of an equation should be “smaller”

than the LHS.smaller:it should only contains constructors: what we want is a set of equations that can be used to rewrite any sequence of operations involving modifiers or behaviors into a sequence that only contains constructors and constants of other types. (M. Ardis)

03.05.23 10

Algebraic specification of Stack (Semantics)[1/2]The type List[G] becomes a LIFO data structure with the following semantics:

Stack: (set of axioms)----------------------------remove(new()) = new() remove(add(S,i)) = S----------------------------item(new()) = undefineditem(add(S,i)) = i

empty(new()) = true empty(add(S,i)) = false ----------------------------

Remark. ADTStack=List[G](signature)+Stack(axioms), is a theory for LIFO data structures.

Usually denoted by push, pop, top

remove produces values from DS but it does not generate any new values, it only produces values we had without it.This is the reason why we decide to classify it as a modifier, not a constructor

Any operation that does not produce a value of the type being defined is called abehavior (inspector) operation.

03.05.23 11

Algebraic specification of Stack 2/2]understanding recursive specifications

• Notation for termsnew()=[]Any list:S=[s]add([s],i)=[I,s]

• Example of terms:add(add(add([],3),2),1)=(notation)[1,2,3]item([1,2,3])=item(add(add(add([],3),2),1))=1

• remove([1,2,3])= remove(add(add(add([],3),2),1))=add(add([],3),2)=[2,3]remove2([1,2,3])= [3]remove3([1,2,3])= []remove3+k([1,2,3])=[]item◦remove3([1,2,3])=undefined

• [1,2,3] is a vector representation of a stack with the top to the left.

The systematic rewriting of the axioms illustrates that it really

behavies as a stack

03.05.23 12

Algebraic specification of Queue (Semantics)[1/2]

The type List[G] becomes a FIFO data structure with the following semantics:

Queue(set of axioms):------------------------------remove(new()) = new()remove(add(Q, I)) = if empty(Q) then Q else add(remove(Q), I)-------------------------------item(new()) = undefineditem(add(Q, I)) = if empty(Q) then I else item(Q)

empty(new) = trueempty(add(Q, I)) = false------------------------------

Usually denoted by add, remove, front

A special distinguished, constant operation such as undefined may be defined. The value undefined is untyped so can be the result of any specification operation.

03.05.23 13

Algebraic specification of Queue 2/2]understanding recursive specifications

• Notation for termsnew()=[]Any list:S=[s]add([s],i)=[I,s]

• Example of terms:add(add(add([],3),2),1)=(notation)[1,2,3]item([1,2,3])=item(add(add(add([],3),2),1))=item( add(add([],3),2))= =item(add ([],3))=3

• remove([3])=remove(add([],3))=[]remove([2,3])= remove(add([3],2))=add(remove([3]),2)=add([],2)=[2]remove([1,2,3])=remove(add([2,3]),1))=

=add(remove([2,3],1))=add([2],1)=[1,2]remove2([1,2,3])= [1]remove3([1,2,3])= []remove3+k([1,2,3])=[] item2([1,2,3])=2item3([1,2,3])=1item4([1,2,3])=undefined

• [1,2,3] is a vector representation of a queue with the oldiest to right

The systematic rewriting of the axioms illustrates that it really

behaves as a queue

03.05.23 14

Sufficiently Complete Sets of Equations

• How can we know if we have writte– few equations (incompleteness )

or– too many (overspecification)

to describe some new abstract data type? • John Guttag algorithm gives hints to use,

but there are still lots of things that can go wrong:– we might divide the constructor and modifier operations incorrectly.– we might fill in a right-hand side of an equation incorrectly:

the RHS of an equation should be “smaller” than the LHS.

For some of the right-hand sides it is clear that they are smaller than the left-hand sides.

• new is smaller than remove(new). • but what about remove(add(Q, I)) >?> add(remove(Q), I)

Note how the remove operation is applied to shorter and shorter operands until it is eliminated

03.05.23 15

Algebraic specification of Array (Ian Sommerville)

03.05.23 16

Exercises• Exercise 1.

– Express by a Java interface (or a Java/ C++ abstract class) the ADT List[G]

– Construct two implementations for ADT Stack: array based and linked list, respectively.

– Construct two implementations for ADT Queue: array based and linked list, respectively.

• Exercise 2. Using the equation rewriting approach as used in LIST ( Elem: [Undefined →Elem] ) verify that the operation Add ([10, 7, 4], 8) on the list causes the list [8, 10, 7, 4] to be built. (Hint: Show the head of the list is 8 and the tail is [10, 7, 4]).

03.05.23 17

Algebraic specs and axiomatic verification

• We will specify the behavior of a user-defined type as a many-sorted algebra

• Many-sorted algebra is – collection of elements of various types (types are called "sorts") – operations that manipulate these elements

• Specification has three main parts: – syntax (what are the sorts, ops, arguments) – semantics (what do the ops do?) – restrictions (are there exceptions or limits?)

• Semantics component provide axioms that can be used in axiomatic proofs

of programs that use the specified type

03.05.23 18

(another) Algebraic specification of Queue (Ian Sommerville)

Compare with the previous

definition.Try to

understand why

are both defining queues

03.05.23 19

Many- sorted algebras

03.05.23 20

Signatura• Signatură

Σ= (S,Ω): mulţime finită de sorturi (S)+ operaţii asociate(Ω)unde Ω={Σw1,s1,... Σwn,sn}, familie de mulţimi de operaţii

– Operaţie: simbol de funcţie, domeniu (aritate, wi), co-domeniu (rezultat, sort si); argumentele şi rezultatul sunt sorturi din S)

– Operaţiile din Σwi,si au toate aceeaşi aritate wi şi acelaşi co-domeniu si

– Exemplu. Signatura Numbers.S=(X,Y)Ω= { ΣX,X={s } :X→X},

ΣXX,X ={a,m } :X x X→X}, ΣXX,Y ={l,g } :X x X→Y}, Σ<>,X ={z } :<>→X},

Σ <>,Y ={T,F } :<>→Y}, }

z,T, F: funcţii constante, domeniu vid (constructori primitivi)s: constructor de tip Xl,g: observatori (funcţii de interogare)a,m: modificatori(de tip X)

03.05.23 21

Signatures, friendlier versions

Signature: NumbersSorts: Num, BoolOperations: zero:<>→Num

T,F:<>→Boolsucc: Num →Numadd, mpy: Num x Num→Num >,< : Num x Num →Bool

Signature: NumbersSorts: X ,YOperations: z:<>→X

T,F:<> →Ys: X →Xa,m: X x X→X l,g: X x X →Y

More intuitive

03.05.23 22

Algebre multi sortate• Algebră: signatură + semantică

Semantică:– Fiecărui sort din S i se asociază o mulţime de obiecte reale, numită mulţime suport

(carrier set)– Fiecărui simbol de funcţie i se asociază o funcţie pe mulţimile suport, de aritate şi

domeniu ce corespund mulţimii Σwi,si din care face parte simbolul– Observaţie: pot exista mai multe semantici (interpretări) pentru aceeaşi signatură,

adică mai multe algebre de aceeaşi signatură– Exemplu:

• Algebra (multisortată a) numerelor naturale |Num|=( |Num|X , |Num|Y, ΩNum)– |Num|X=N={0,1,…}, |Num|Y=B={true, false}– ΩNum contine functiile:

» zNum=0 (zero); sNum(n)=n+1 (functia succesor); TNum=true; FNum=false aNum(m.n)=m+n (suma); mNum(p,n)=p*n (produs)lNum (m.n)=(m<n), gNum (m.n)=(m>n)

• Algebra (multisortată a) claselor de resturi modulo 4 |Num4|– |Num4|X=N={0,1,2,3}, |Num4|Y=B={true, false}– zNum4=0 (zero); sNum4(n)=(n+1) mod 4 (functia succesor modulo 4); TNum4=true; FNum4=false

aNum4(m.n)=(m+n) mod 4 (suma modulo 4); mNum4(p,n)=(p*n) mod 4 (produs modulo 4)– lNum4 (m.n)=(m<n), gNum4 (m.n)=(m>n)

• Signatura Σ, împreună cu o semantică, formează o Σ- algebră

03.05.23 23

Algebra termenilor (term algebra)• Orice signatură are o algebră- algebra termenilor.

– Termen de bază (fără variabile, ground term)-definiţie structurală• Orice constantă c:<>→X este un termen de tip X• Daca f este un simbol de functie f:S1x…Sn→X iar

t1,…tn sunt termeni de tipul S1,… respectiv Sn

atunci f (t1,…tn) este termen de tipul X• O secventa de simboluri este termen numai dacă se obţine din aplicarea de un număr

finit de ori a regulilor anterioare.

Notaţie: TΣ, mulţimea termenilor de bază– Termen (cu variabile dintr-o mulţime V)

Notaţie: TΣ(V), mulţimea termenilor cu variabile.– Algebra termenilor de bază:

• Mulţimea suport a unui sort S i este mulţimea termenilor de tip S i

• Operaţiile din Ω sunt interpretate ca operaţii în TΣ,

– Exemplu. Pentru signatura Numbers:• z,s(z), a(z, s(z)) etc. sunt termeni de bază de tip X • g (s(z), a(z, s(z)) sunt termeni de bază de tip Y• a(v1, s(z)) , unde v1 ∈ V, este termen (cu variabile) din TΣ(V),

• Simbolul de funcţie s este interpretat prin funcţia s TΣ: TΣ→ TΣ

unde s TΣ(t)=s(t) etc.

03.05.23 24

Homomorphism

• Homomorphism: functions preserving structure• Example

Let be f=(fX, fY), where:fX: |Num|X→|Num4|X, fY: |Num|Y→|Num4|Yand:fX(x)=x mod 4, fY(x)=x

f is a homomorphism: indeed, for all oparations in Ω we have:– fX(zNum)=zNum4 ( that is (zNum4 fX()))– fY(TNum)=TNum4 ,, – fY(FNum)=FNum4

– fX(sNum(n))=sNum4(fX(n)), that is (n+1)mod 4= ((n mod 4) +1)mod 4

– fX(aNum(n,p))=aNum4( fX(n), fX(p) ), that is(n+p)mod4=((n mod 4)+(p mod 4))mod 4

– fX(mNum(n,p))=mNum4( fX(n), fX(p) )

03.05.23 25

Ecuaţii,axiome, teorie, model • Mulţime E de ecuaţii peste o signatură Σ:

conţine construcţii sintactice de forma t=e, unde t şi e sunt termeni• Axioms, multimea axiomelor: submultime a lui E

– Exemplu: mulţimea NumberAxioms, cu ecuaţii peste signatura Numbers (i şi n sunt nume de variabile):A1. a(i,z)=i, adică i+0=iA2. a(i,s(n))=s(a(i,n)), adică i+(n+1)=(i+n)+1

A3. g(z,z)=F, adică 0>0 este falsA4. g(s(i),z)=TA5. g(z,s(i))=FA6. g(s(i),s(n))=g(i,n)

A7. l(z,z)=F, adică 0<0 este falsA8. l(s(i),z)=FA9. l(z,s(i))=TA10. l(s(i),s(n))=g(i,n)

A11. m(i,z)=zA12. m(i,s(n))=a(m(i,n),i) adică i(n+1)=in+i

• Teorie: signatură + axiome, (Σ,Axioms)• Model al unei teorii: Σ- algebră care satisface axiomele teoriei

– Numbers- algebra Num este model al teoriei (Numbers, NumberAxioms)– Numbers- algebra Num4 NU este model (Numbers,NumberAxioms)

• lNum4 (zNum4 ,sNum4 (3))=true (A9)• lNum4 (zNum4 ,sNum4 (3))= lNum4 (zNum4 , zNum4 )= false (A7), contradictie

03.05.23 26

Proof system (1/2)– Set of inductive rules of the form– It provides a deductive system at the syntactic level by which more equations may be generated from the original set of axioms. – The new generated equations are called theorems.– Example: rules of inference

1. Reflexivity

2. Symmetry

3. Tranzitivity

4. Substitution(for every f in signature and with suitable arity )

5. Instantiation(ρ is a substitution which instantiates the variables in t to values in the carrier of the appropriate sort.)

tt

conclusionpremise

ette

etefft

,

),...(),...(,...

11

11

kk

kk

eefttfetet

etet

03.05.23 27

Proof system (2/2)

• a(s(z), s2(z))=s3(z) is a theorem.It stands for (0+1)+((0+1)+1)=((0+1)+1)+1

– Indeed:(by axiom A2)t1. a(i,s(n))=s(a(i,n)) i+(n+1)=(i+n)+1by instantiation (rule 5), using the substitution i←s(z), n←s(z),

t2 . a(s(z),s(s(z)))=s(a(s(z),s(z))) (0+1)+((0+1)+1)=((0+1)+(0+1))+1(A2 and instantiation again)t3. a(s(z),s(z))=s(a(s(z),z)) (0+1)+(0+1)= ((0+1)+0)+1(A1, instantiation)t4. a(s(z),z) =s(z) (0+1)+0=0+1(t3, t4 and rule 4, substitution)t5. a(s(z),s(z))=s(s(z)) (0+1)+(0+1)= (0+1)+1 (t2, t5 and rule 4, substitution)t6. a(s(z),s(s(z)))= s(s(s(z))) (0+1)+((0+1)+1)=((0+1)+1)+1

• Remark. In case an elementary data type for a programming language is defined by the signature Numbers, Num is a correct implementation (it is a model) while Num4 it is not.

03.05.23 28

Modelling Concurrent Systems

Principles of Model CheckingChristel BaierJoost-Pieter KatoenThe MIT PressCambridge, MassachusettsLondon, England, 2008

03.05.23 29

Sisteme reactive• Sisteme reactive:

interacţiune continuă cu mediul în care se execută– Mediul trimite un stimul; sistemul răspunde printr-o reacţie , după care este

pregătit pentru o altă interacţiune– Executarea sistemelor reactive tipice nu se termină

• În contrast cu sistemele secvenţiale (transformaţionale): după ce primesc datele de intrare, acestea produc un rezultat şi se termină

• Sistemele transformaţionale pot fi specificate prin precondiţii şi postcondiţii– Descrierea proprietăţilor sistemelor reactive face referire la ordinea de apariţie a

evenimentelor din sistem, adică la comportamentul de-a lungul timpului– Exemplu. Automat de băuturi.– Categorii de proprietăţi ale sistemelor reactive (Lamport, 1977)

• safety (de siguranţă): something bad never happens:– Corectitudine parţială: sistemul nu produce răspunsuri greşite– Mutual exclusion: Excludere mutuală: două procese nu execută simultan o zonă critică– Deadlock- freedom: absenţa blocajului– Automatul de băuturi nu va livra niciodată ceai la o cerere pentru cafea– etc.

• liveness (bună funcţionare): something good will eventually happen– Terminarea programelor– Starvation-freedom (procesul va fi până la urmă servit)– Automatul de băuturi va furniza, în cele din urmă, băutura solicitată

03.05.23 30

Modelling concurrent systems• Asynchronous processes: evolving completely autonomously (modelled by

interleaving mechanism)– Comunicating via shared variables

• Synchronous processes: interact by a handshaking mechanism • Concurrent Systems

A concurrent system consists of a set of components that execute together and (normaly) have some means of communicating with each other.

• We will consider two modes of execution: – asynchronous or interleaved execution, in which only one component

makes a step at a time– synchronous execution, in which all of the components make a step at the

same time.• We will also distinguish three modes of communication.

– shared variables– exchanging messages using queues– handshaking protocol.

• mathematical basis for modeling reactive systems.– program graphs, – parallel composition, – channel systems

03.05.23 31

Transition Systems(Baier, Katoen)

• Transition systems: a (by now) standard class of models to represent hardware and software systems.

• In the literature, many different types of transition systems have been proposed. The variant we use: transition systems with – action names for the transitions (state changes) and – atomic propositions for the states (used to formalize temporal

characteristics; intuitively express simple known facts about the states of the system under consideration)

Definition. A transition system TS is a tuple (S, Act,→, I,AP, L) where– S is a set of states,– Act is a set of actions,– → ⊆ S × Act × S is a transition relation,– I S ⊆ is a set of initial states,– AP is a set of atomic propositions, and– L : S → 2AP is a labeling function.TS is called finite if S, Act, and AP are finite.

Φ a propositional logic

formula:

s |= Φ iff L(s) |= Φ.

03.05.23 32

Example

transition system (models a preliminary designof a beverage vending machine) (Baier, Katoen)

Act = { insert coin, get soda, get beer, τ }.

L(s) = { s } (here AP⊆ S; a state name act as atomic propositions)Another variant:AP = { paid , drink } L(pay) = ∅, L(soda) = L(beer) = { paid , drink }, L(select) = { paid }.

03.05.23 33

Direct Predecessors and Successors. Terminal states

The set of direct successors

The set of direct predecessors

s terminal

⇕

Post(s) = .∅

•for a transition system modeling a sequential computer program, terminal states occur as a natural phenomenon representing the termination of the program.•for transition systems modeling parallel systems, such terminal states are usually considered to be undesired

03.05.23 34

Determinism• it is often useful to consider transition systems where the ”observable” behavior is

deterministic, according to some notion of observables. There are two general approaches to formalize the visible behavior of a transition system:

– action-based approach assumes that only the executed actions are observable from outside,

– state-based approach ignores the actions and relies on the atomic propositions that hold in the current state to be visible.

Deterministic Transition SystemTS = (S, Act,→, I,AP, L)

– TS is called action-deterministic if • | I | ≤ 1 • and • | Post(s, α) | ≤ 1

for all states s and actions α.– TS is called AP-deterministic if

• | I | ≤ 1• and • |Post(s)∩{s S | L∈ (s) = A}| ≤ 1

for all states s and A ∈ 2AP.

have at most one outgoingtransition labeled with action α per state,

there is at most one outgoingtransition leading to a state with label A.

At most one initial state.

03.05.23 35

Executions (runs)• An execution of a transition system results from the resolution of the

possible nondeterminism in the system.

• Definition. Execution Fragment.Let TS = (S, Act,→, I,AP, L) be a transition system.A finite execution fragment of TS is an alternating sequence of states and actions ending with a stateρ= s0 α1 s1 α2 . . .αn sn such that si- αi→si+1 for all 0 ≤ i < n, where n ≥ 0. We refer to n as the length of the execution fragment . An infinite execution fragment ρ of TS is an infinite, alternating sequence of states and actions: ρ= s0 α1 s1 α2 . . .αn sn… such that si- αi→si+1 for all i ≥ 0.

• A state s S is called reachable in TS if there exists an initial, finite ∈execution fragment ρ= s0 α1 s1 α2 . . .αn sn with s= sn.

• A maximal execution fragment is either a finite execution fragment that ends in a terminal state, or an infinite execution fragment. An execution fragment is called initial if it starts in an initial state.

• Definition. Execution. An execution of transition system TS is an initial, maximal execution fragment.

03.05.23 36

Program Graphsfor Data Dependent Systems

(Baier, Katoen)

Definition. Program Graph (PG). A program graph PG over set Var of typed variables is a tuple (Loc, Act,Effect, →, Loc0, g0) where– Loc is a set of locations and Act is a set of actions,– Effect : Act × Eval(Var) → Eval(Var) is the effect function,– → ⊆ Loc × Cond(Var) × Act × Loc is the conditional transition

relation,– Loc0 Loc ⊆ is a set of initial locations,– g0 Cond∈ (Var) is the initial condition.

• Notation. x-g:α →y is used as shorthand for (x, g, α,y ) ∈→.

• The behavior in location x Loc ∈ depends on the current variable evaluation η. – A nondeterministic choice is made between all transitions x-g:α→y

which satisfy condition g in evaluation η (i.e., η |= g). The execution of action α changes the evaluation of variables according to Effect(α, ·). Subsequently, the system changes into location y.

– If no such transition is possible, the system stops.

03.05.23 37

Example. Program graph for a vending machine

start selecttrue:coin

true:refillnsoda>0:sget

nbeer>0:bget

nsoda=0 ∧ nbeer=0 :return_coin

VMRevisited:

Var = { nsoda, nbeer }Loc ={ start , select }Loc0 = { start }Act = { bget , sget, coin, ret coin, refill } Effect(coin, η) = ηEffect(ret coin, η) = ηEffect(sget, η) = η[nsoda := nsoda−1]Effect(bget, η) = η[nbeer := nbeer−1]Effect(refill, η) = [nsoda := max, nbeer := max]g0 = (nsoda = max nbeer = max).∧

03.05.23 38

Transition system TS(PG) of program graph PG

• Definition 2.15. Transition System Semantics of a Program GraphThe transition system TS(PG) of program graph PG = (Loc, Act,Effect, →, Loc0, g0) over set Var of variables is the tupleTS(PG)=(S, Act, →, I,AP, L) where– S = Loc × Eval(Var)– →⊆S × Act × S is defined by the following rule:– I = {<x, η> |x Loc0, η |= g0}∈– AP = Loc Cond(Var)∪– L(<x, η>) = {x} {g Cond(Var) | η |= g}.∪ ∈

03.05.23 39

Example. Transition system for VMRevisited

03.05.23 40

Parallelism and Communication(Baier, Katoen, 2.2)

03.05.23 41

Objectives(Baier, Katoen, 2.2)

Describe several mechanisms to provide operational models for parallelsystems by means of transition systems

– no communication between the participating transitions systems takes place, – messages can be transferred, either

• synchronously (i.e., by means of “handshaking”) or

• asynchronously (i.e., by buffers with a positive capacity).

Let us assume that the operational (stepwise) behavior of the processes that runin parallel are given by transition systems TS1, . . . ,TSn. The goal is to define an operator ∥such that:TS = TS1 ∥TS2 ∥ . . . ∥ TSnis a transition system that specifies the behavior of the parallel composition of transitionsystems TS1 through TSn.Here, it is assumed that is a commutative and associative operator.

03.05.23 42

Steps:• II parallel composition of TS (transition systems)

• III interleaving of TS

• III interleaving of PG (program graphs )• For program graphs PG1 (on Var1) and PG2 (on Var2) without shared variables (asynchronous, completely autonomous) (i.e., Var1 ∩Var2 = ), ∅

TS(PG1) ||| TS(PG2)

describes the behavior of the simultaneous execution of PG1 and PG2.• For program graphs PG1 (on Var1) and PG2 (on Var2) with shared variables

TS(PG1 |||PG2)

faithfully describes a parallel system whose components communicate (asynchronous communicating) via shared variables.Note that in general, TS(PG1 |||PG2) = TS(PG1) ||| TS(PG2).• For processe that interact in a synchronous fashion: handshaking

03.05.23 43

Interleaving (Ⅲ) of Transition SystemsDefinition. TS1 Ⅲ TS2.TS1 ||| TS2 = (S1 × S2, Act1 Act∪ 2,→, I1 × I2,AP1 AP∪ 2, L)where the transition relation → is defined by the following rules:

and the labeling function is defined by L(s1, s2) = L(s1) L∪ (s2).• Remark. The interleaving operator ||| can be used to model asynchronous concurrency in

which the subprocesses act completely independent of each other, i.e., without any form of message passing or contentions on shared variables. It is too simplistic for most parallel systems with concurrent or communicating components.

x=3

x=6

x=2x

x=3

x=6

x=x+1||| <x=3,x=4><x=6,x=3>

<x=6,x=4>

<x=3,x=3>

=

containsthe inconsistent states <x=6, x=4> and, thus, III does not reflect the intuitive behavior of the parallel execution

Interleaving Operator for Concurrent Processes comm by shared variables

03.05.23 44

Communication via Shared Variables(2.2.2, Baier, Katoen)

03.05.23 45

Communication via Shared Variables:interleaving Program Graphs

Definition. Program graph PG1 |||PG2 is defined byPG1 |||PG2 = (Loc1 × Loc2, Act1 ⊕Act2,Effect, →, Loc0,1 × Loc0,2, g0,1 g∧ 0,2)where → is defined by the rules:

and Effect(α, η) = Effecti(α, η) if α Acti.∈

The program graphs PG1 and PG2 have the variables Var1 ∩ Var2 in common ( shared or also called “global” variables).

The variables in Var1 \ Var2 are thelocal variables of PG1, and similarly, those in Var2 \ Var1 are the local variables of PG2.

03.05.23 46

Example. Modeling communications

via shared variables Actions that access (inspect or modify )

shared variables must be considered

as “critical”the actions α Act ∈

are indivisible.

Exercise. What if x:=2x si x:=x+1 are not considered critical?

A. In case t1:=x; t2:=x; t1:=2* t1; t2:=t2+1; x:=t1; x:=t2 ,

the state x=4 might be a finalstate in real parallel execution, but it does not appear in the model ( transition system)

03.05.23 47

Example. Mutual Exclusion in asynchronous processes: Mutual Exclusion with Semaphores (Baier,Katoen, 2008)(1/3).

Program graph of Processes:

Process

1,2:

loop forever ... (* noncritical actions *) request critical section release ... (* noncritical actions *)end loop

Mutual exclusion: two processes cannot be simultaneously in their critical section

y is a semaphore:y=0, locked

y=1, free

actionguard

03.05.23 48

Example. Mutual Exclusion in asynchronous processes: Mutual Exclusion with Semaphores (2/3).

The interleaved program graph P1 Ⅲ P2

03.05.23 49

Example. Mutual Exclusion in asynchronous processes: Mutual Exclusion with Semaphores (2/3).

Underlying transition system TS(P1 Ⅲ P2)of the interleaved program graph P1 Ⅲ P2 (generally, different from TS(P1) Ⅲ TS (P2) )

global state crit1, crit2, y = . . . is unreachable in TS_Sem, it followsthat the parallelsystem thus satisfies the so-called mutual exclusion property.

03.05.23 50

Peterson’s Mutual Exclusion Algorithm (1/4)P(eterson)=cobegin P1 P2 ∥ coend, whereP1= (and a similar P2, changing 1 to 2 and 2 to 1)while true do

noncritical actions<b1:=true; x:=2> wait until(x=1 not b2⋁ )critical actionsb1:= falsenoncritical actions

end Remarks. • Atomicity of <b1:=true; x:=2> is not essential, but te order

b1:=true; x:=2 does it.• b1=b2=false is a precondition• If both processes want to enter in critical zone, the value of x decides.• When starting to wait, P1 sets x to 2 giving privilege to P2 (as inviting P2) to

enter its critical zone

Mutual esclusion for two processes.

There is a generalisation of Peterson’s alg.

Filter lock

03.05.23 51

•

Peterson’s Mutual Exclusion Algorithm (2/4)

03.05.23 52

Peterson’s Mutual Exclusion Algorithm (3/4)

•Mutual excusion,

• but fair access to their critical sections: if both are waiting, they both will receive access, one after another

More exactly, each state has the form

< loc1, loc2, x>

<b1, b2>.

Initially, b1=b2=f(alse) <f,f><f,f>

<f,f>

<t,f> <f,t>

<t,f> <f,t>

<t,t> <t,t>

<t,t> <t,t>

⌝b2 ⌝b1

x=1 x=2

bk= wk ⋁ ck

03.05.23 53

Peterson’s Mutual Exclusion Algorithm (4/4)

•Atomicity of <b1:=true; x:=2> is not essential, but te order b1:=true; x:=2 does it.

x:=2; b1:=true does not guarantee mutual excusion.

The path shows that P2 enters its critical section while P1 is already there

P1 enters its

Critical section

P1 and P2 in their

Critical sections at the same time

03.05.23 54

Exercices. Peterson’s Mutual Exclusion Algorithm

Ex. 1. What if we do not use bk in Peterson’s algorithm?Ex. 2. What if we do not use x in Peterson’s algorithm?Answers.

<n1, n2, x=1> <n1, n2, x=2>

<w1, n2, x=2> <n1, w2, x=1>

<w1, w2, x=1> <w1, w2, x=2>

<c1, w2, x=1>

<w1, n2, x=2><n1, w2, x=1>

<w1, c2, x=2>

<n1, n2, f,f >

<w1, n2, t,f > <n1, w2, f,t >

<w1, w2, t,t>

<c1, n2, t,f > <n1, c2, f,t >

A.1 A.2

•Critical sections executed only in case both are waiting•Fair execution of c1, c2 in this case

•Possible unfair execution of c1, c2

•terminal state if both are waiting!

03.05.23 55

Handshaking

03.05.23 56

Handshaking• Interleaving and shared variables describe processes that evolves

completely autonomously (asynchronous processes)• Handshaking: a mechanism by which processes interact in a

synchronous fashion

03.05.23 57

Handshaking, Synchronous Message Passing ●

03.05.23 58

Notations and some considerations on handshaking

●

●

●

● Handshaking is commutative, but not associative

03.05.23 59

Pairwise synchronization over the common actions

03.05.23 60

Example: mutual exclusion by means of an Arbitrer

noncrit1 crit1

release

request

noncrit2 crit2

request

release

T1 and T2, simplified versions of two processes with mutual excusion

- No wait state is necessary: Arbitrer mimics the semaphore

unlock

lock

releaserequest

T1T2Arbitrer

TSArb= (TS1 III TS2)IIH Arbiter

H={request, release}

Note.(TS1 III TS2)III Arbiter

Does not assure mutual exclusion!

03.05.23 61

Example. Booking system at a cashier of a supermarket (1/2)

BCR

Bar Code Reader

-Reads a bar code and communicates the (ID,price) of the just scanned product to the BP

Actions:

•scan: put (ID,price) in buffer A

•store: move A to B

BP

Booking Program

-on receaving (ID,price) transmits to printer P and comands to print

Actions:

•prt_cmd: move B to C

P

Printer-prints on receaving a print command and (ID,price) from BP

Actions:print: prints C

Every process has a one location buffer:

A, B and respectively C

(BCR ∥BP ∥ P): interaction by handshaking guarantees correct printing of all scaned articles (see path scan scan etc. in the next slide )

03.05.23 62

Example. Booking system at a cashier of a supermarket (2/2)

Pairwise synchronisation

Transition system

(BCR ∥BP ∥ P):

03.05.23 63

Example. Railroad Crossing (1/2)

Interaction by handshaking (next slide): Train ∥ Controller ∥ GateIt suffers from a design flaw: the gate is about to close while the train is already at the crossingThe considered models is time-abstract.Specification needs real time constraints: closing the gate does not take more time than the train needs to get to the crossing after signalling approach.

03.05.23 64

Example. Railroad Crossing (2/2)

Transition system (there are some errors!)

03.05.23 65

Example. The Scheduler FAIRPRINT:

signal:=false; full_page:= false; lines:=0;

do 1: not signal→ PrintLine; lines:=(lines+1)mod 30

⌷ 2: not signal ∧ full_page → signal:= trueod

FAIR transition system, with

states (z1,z2)≤(0,0)

(0,0)

(-1,0) (0,-1)({1},1)

({2},2)

({1},1)

({1,2},2)

({2},2)

({1},1)

({1,2},1)({1,2},2)({1,2},1)

PRINT transition system, with states

(signal,full_page,lines) (0,0,0) (0,0,1)({1},1) (0,0,29)({1},1) ({1},1)

(0,1,0)({1},1)

(1,1,0)({1,2},2)

({1,2},1)

FAIR ∥PRINT,Handshaking synchronization:Prints 1 or 2 pages and stops

({2},2)

03.05.23 66

Channel systems

03.05.23 67

Channel Systems• processes communicate via so-called channels, i.e., FIFO buffers that may

contain messages• closed channel system: processes may communicate with other processes

in the system (via channels), but not with processes outside the system.• each process Pi is specified by a program graph PGi which is extended with

communication actions:– c!v transmit the value v along channel c,– c?x receive a message via channel c and assign it to variable x.

• a channel c has a cap(c) (finite or infinite; may be zero) capacity indicating the maximum number of messages it can store, and a type (or domain) specifying the type of messages that can be transmitted over c

• both synchronous and asynchronous message passing can be modeled.– cap(c) > 0, asynchronous message passing,

there is a “delay” between the transmission and the receipt of a message: sending and reading a message from a channel with a nonzero capacity can never appear simultaneously

– cap(c) = 0, synchronous message passing,In this case, channel c has no buffer. Communication via such a channel c corresponds to handshaking (simultaneous transmission and receipt,

• A channel system CS over (Var, Chan) consists of program graphs PGi over (Vari, Chan) (for 1 ≤i ≤ n) with Var union of Vari. We denote

– CS = [PG1 | . . . | PGn] .

03.05.23 68

Communication transitions

• g:c!v (for sending v along c) • g:c?x (for receiving a message in x along c)• Handshaking. If cap(c) = 0, then process Pi can transmit a value v over channel c

only if another process Pk , say, “offers” a complementary receive action, i.e., can perform c?x .

– Pi and Pk should thus be able to perform → c!v → (in Pi) and → c?x → (in Pk) simultaneously.– The effect of message passing corresponds to the (distributed) assignment

x := v.– when handshaking is only used for synchronization purposes and not for data

transfer, the name of the channel as well as the value v are not of any relevance.

• Asynchronous message passing. If cap(c) > 0, then – process Pi can perform the conditional transition → c!v → if and only if channel

c is not full; v is stored at the rear of the buffer c.– Accordingly, Pk may perform → c?x → if and only if the buffer of c is not

empty. In this case, the first element v of the buffer is extracted and assigned to x (in an atomic manner).

e e’g: c!v

e e’g: c?x

Cap()c>0

03.05.23 69

Rules for the transition relation of a channel system

03.05.23 70

Alternating Bit Protocol (1/5)• The system consists of a sender S and a receiver R that communicate with

each other over channels c and d, – both channels have an unlimited buffer, i.e., cap(c) = cap(d) = ∞. – channel c is unreliable in the sense that data may get lost when being

transmitted from the sender S to channel c.– once messages are stored in the buffer of channel c, they are neither corrupted

nor lost.– channel d is assumed to be perfect.

• The goal is to design a communication protocol that ensures any distinct transmitted datum by S to be delivered to R.

– To ensure this in the presence of possible message losses, sender S resorts to retransmissions.

– Messages are transmitted one by one, i.e., S starts sending a new message once the transmission of the previous message has been successful (send-and-wait)

• S sends the successive messages m0,m1, . . . together with control bits b0, b1, . . . over channel c to R.

– Transmitted messages are thus pairs: (m0, 0), (m1, 1), (m2, 0), (m3, 1), . . .– On receipt of (m, b) (along channel c), R sends an acknowledgment (ack)

consisting of the control bit b just received. – On receipt of ack b, S transmits a new message with control bit ¬b.

• If, however, S has to wait “too long” for the ack, it timeouts and retransmits (m,b).

– The timeout mechanism of S is modeled by a Timer process.– The communication between the timer and S is modeled by means of

handshaking, i.e., by means of channels with capacity 0.

03.05.23 71

Alternating Bit Protocol (2/5)

Sender S

Chanel d is also considered unreliable

Since the transmission of acks (over channel d) is reliable, it is unnecessary (but not wrong) for S to verify the control bit of the ack in location chk ack(·).

03.05.23 72

Alternating Bit Protocol (3/5)

Receiver R Timer T

ABP = [S | Timer | R ]

03.05.23 73

Alternating Bit Protocol (4/5)• The underlying transition system TS(ABP) has, despite various simplifying

assumptions, infinitely many states. This is, e.g., due to the fact that the timer may signal a timeout on each transmission of a datum by S resulting in infinitely many messages in channel c.

Execution fragment: the loss of a message.

03.05.23 74

Alternating Bit Protocol (5/5)• Note: When the receiver R is in location wait(0) and receives a

message, it anticipates receiving a message with either control bit 0 (as it expects) or with (unexpected) control bit 1 (and symmetrically, in location wait(1) )

• The following execution fragment indicates why this unexpected possibility is essential to take into consideration.

03.05.23 75

Formalisms to specify the behavior of reactive systems

03.05.23 76

Promelaspecification language (Process metalanguage)

• the input language for the prominent model checker SPIN by Holzmann.• Promela programs P consist of a finite number of processes P1, . . . ,Pn to

be executed concurrently.– supports communication over shared variables

and– message passing along either synchronous or buffered FIFO-

channels.• The formal semantics of a Promela-program can be provided by means of a

channel system, which then can be unfolded into a transition system.• The stepwise behavior of the processes Pi is specified in Promela using a

guarded command language with several features of classical imperative programming languages

– variable assignments,– conditional commands (if fi)– repetitive commands (do od)– sequential composition (;)– communication actions (c!v, c?x :send and receive messages from the channels)– atomic regions that avoid undesired interleavings.

03.05.23 77

nanoPromela(a fragment of Promela) Baier, Katoen

• nanoPromela programs:P = [P1| . . . |Pn], where Pi are processes

• Syntax of process statements:stmt ::=

– skip – | x := expr – | c?x | c!expr – |stmt ; stmt– | atomic{assignments} – |if :: g1 stmt1 . . . :: gn stmtn⇒ ⇒ fi – |do :: g1 stmt1 . . . :: gn stmtn ⇒ ⇒ od

• Nondeterministic choice•Test and set semantics•Blocking, if no guard is fulfilled

cannot be interleaved with the activities of other

processes.

Informal meaning:

03.05.23 78

Examples: nanoPromela programs

Peterson’s Mutual Exclusion AlgorithmProcess P1 (P2 is similar)do :: true ⇒ skip;

atomic{b1 := true; x := 2};if :: (x = 1) ∨ ￢ b2 crit⇒ 1 := true fiatomic{crit1 := false; b1 := false}

od

Waiting phaseand

Critical section

•use of atomic regions is not necessary, but•if we drop atomic, the order of assignement must be preserved; otherwise themutual exclusion property cannot be ensured

Vending Machinedo :: true ⇒ skip;

if :: nsoda > 0 nsoda ⇒ := nsoda − 1 :: nbeer > 0 nbeer ⇒ := nbeer − 1 :: nsoda = nbeer = 0 ⇒ skip

fi :: true ⇒ atomic{nbeer := max; nsoda := max}od

Coin insertio

n

03.05.23 79

Formal Operational semantics of nanoPromela

• The operational semantics of a nanoPromela-statement with variables and channels from (Var, Chan) is given by a program graph over (Var, Chan).

• The program graphs PG1, . . ., PGn for the processes P1, . . . ,Pn of a nanoPromela program P = [P1| . . . |Pn] constitute a channel system over (Var, Chan).

• The transition system semantics for channel systems then yields a transition system TS(P) that formalizes the stepwise behavior of P.

Example. Program graph for a looploop = do :: x > 1 y ⇒ := x + y

:: y < x x ⇒ := 0; y := xod

Test and set semanticsTest and set

semantics

03.05.23 80

Substatements: locations in program graphsThe set of substatements of a nanoPromela-statement stmt is recursively

defined• For statements stmt {skip, x := expr, c?x, c!expr}∈ the set of

substatements is sub(stmt) = {stmt, exit}. • For sequential composition let

sub(stmt1 ; stmt2) = { stmt ; stmt2 | stmt sub(stmt1) \ {exit}} ∈ sub(stmt2).∪

• For cond_cmd if :: g1 stmt1 . . . :: gn stmtn fi⇒ ⇒ we havesub(cond_cmd) = { cond_cmd} ∪1≤i≤n sub(stmti).

• For loop do :: g1 stmt1 . . . :: gn stmtn od⇒ ⇒we havesub(loop) ={ loop, exit} ∪1≤i≤n { stmt ; loop | stmt sub(stmti) \ {exit}}.∈

03.05.23 81

Inference rules for the nanoPromela constructs• The edges in a program graph

have the form stmt g:α→stmt’orstmt g:comm →stmt’where – stmt is a nanoPromela

statement, – stmt’ a substatement of

stmt, – g a guard, – α an action, – comm a communication

action c?x or c!expr.

03.05.23 82

Test-and-Set Semantics vs. Two-Step Semantics (1/2)

• The rules for if–fi- and do–od-statements formalize the so-called test-and-set semantics of guarded commands. – evaluating guard gi and performing

the first step of the selected enabled guarded command gi ⇒ stmti are performed atomically.

• In contrast, SPIN’s interpretation of Promela relies on a two-step-semantics– the selection of an enabled guarded

command and the execution of its first action are split into two steps.

– The rule for a conditional command, two steps semantics, is formalized by the axiom

– Similarly, the first two rules for loops have to be replaced for the two-step semantics by the following rule:

03.05.23 83

Test-and-Set Semantics vs. Two-Step Semantics (2/2)

• As long as we consider the statements in isolation, the test-and-set semantics and the two-step semantics are equal.

• However, when running several processes in parallel, the interleaving might cause undesired side effects.

Semaphore-basedsolution of the mutual exclusion problem•The initial value of the semaphore y is 1. •Under the two-step semantics the mutual exclusion property is not guaranteed

•it allows the both processes to verify that the guard y > 0 holds, without decreasing the value of y, and •moving control to the assignment y := y−1.•But from there the processes can enter their critical sections.

•However, the protocol works correctly for the test-and-set semantics

03.05.23 84

The State-Space Explosion Problem• Program Graph Representation Transition systems generated by means of

“unfolding” a program graph may be extremely large.the number of states in the transition system is| Loc | · | dom(x1) | … | dom(xN) |The number of states thus grows exponentially in the number of variables in the program graph: for N variables with a domain of k possible values, the number of states grows up to kN. This exponential growth is also known as the state-space explosion problem.

– For instance, a program graph with ten locations, three Boolean variables and five bounded integers (with domain in { 0, . . . , 9 }) has 10·23·105 = 8, 000, 000 states.

• Parallelism. In all variants of parallel operators for transition systems and program graphs, the state space of the complete system is built as the Cartesian product of the local state spaces Si of the components. For example, for state space S of transition systemTS = TS1 ||| . . . ||| TSnthe total state space S is thus |S1| · · · |Sn|.The parallel composition of N components of size k each yields kN states. Even for small parallel systems this may easily run out of control.

• Channel Systems. Let CS = [PG1 | . . . |PGn] be a channel system. The state space of CS is of cardinality|PG1|··· |PGn|·|dom(c1) |cp(c1) ··· |dom(ck) |cp(ck)

• Example. State-Space Size of the Alternating Bit Protocol.– c and d have a fixed capacity, 10 say.– data items are also simply bits– timer has two locations, the sender eight, and the receiver six.– the total number of states is 2·8·6·410·210=3·235≈1011 states.

03.05.23 85

Summary of Modelling Concurrent Systems• Transition systems are a fundamental model for modeling software and

hardware systems.• An execution of a transition system is an alternating sequence of states and

actions that starts in an initial state and that cannot be prolonged.• Interleaving amounts to represent the evolvement of “simultaneous” activities

of independent concurrent processes by the nondeterministic choice between these activities.

• In case of shared variable communication, parallel composition on the level of transition systems does not faithfully reflect the system’s behavior. Instead, composition on program graphs has to be considered.

• Concurrent processes that communicate via handshaking on the set H of actions execute actions outside H autonomously whereas they execute actions in H synchronously.

• In channel systems, concurrent processes communicate via FIFO-buffers (i.e., channels). Handshaking communication is obtained when channels have capacity 0. For channels with a positive capacity, communication takes place asynchronously—sending and receiving a message takes place at different moments.

• The size of transition system representations grows exponentially in various components, such as the number of variables in a program graph or the number of components in a concurrent system. This is known as the state-space explosion problem.

03.05.23 86

Bibliographic Notes, Modelling Concurrent Systems

• Transition systems. Keller was one of the first researchers that explicitly used transition systems for the verification of concurrent programs. Transition systems are used as semantical models for a broad range of high-level formalisms for concurrent systems, such as process algebras Petri netsand statecharts. The same is true for hardware synthesis and analysis, in which variants of finite-state automata (Mealy and Moore automata) play a central role; these variants can also be described by transition systems. Program graphs and their unfolding into transition systems have been used extensively by Manna and Pnueli in their monograph(s) on temporal logic verification.

• Synchronization paradigms. Shared variable “communication” dates back to the midsixties and is due to Dijkstra. He also coined the term interleaving in 1971. Handshaking communication has been the main interaction paradigm in process algebras such as ACP, CCS , CSP and LOTOS. The principle of synchronized parallelism has been advocated in Milner’s synchronous variant of CCS, SCCS and is used by Arnold to model the interaction between finite transition systems. Synchronous parallelism is also at the heart of Lustre, a declarative programming language for reactive systems, and is used in many other hardware-oriented languages.

• The interaction between concurrent processes by means of buffers (or channels) has first been considered by Dijkstra. This paradigm has been adopted by specification languages for communication protocols, such as SDL (Specification and Description Language) which is standardized by the ITU. The idea of guarded command languages goes back to Dijkstra. The combination of guarded command languages in combination with channel-based communication is also used in Promela.. Structured operational semantics has been introduced by Plotkin in 1981. Atomic regions have been first discussed by Lipton, Lamport and Owicki.

03.05.23 87

Linear Time Properties(Baier, Katoen)

03.05.23 88

Linear Time Properties(Baier, Katoen)

• In the following it is assumed that a transition system has no terminal states. In this case, all traces are infinite words.

• First of all, prior to checking any (linear-time) property, a reachability analysis could be carried out to determine the set of terminal states.

• If indeed some terminal state is encountered, the system contains a deadlock and has to be repaired before any further analysis.

03.05.23 89

Deadlock

Example 1.

Fault Designed Traffic Lights

Example 2.

Dijkstra’s problem of Dining Philosophers

•A deadlock occurs if the complete system is in a terminal state, although at least one component is in a (local) nonterminal state. •The entire system has thus come to a halt, whereas at least one component has the possibility to continue to operate. •A typical deadlock scenario occurs when components mutually wait for each other to progress.

The problem is to design a protocol such that the complete system is deadlock-free.

03.05.23 90

Dijkstra’s problem of Dining Philosophers (a fault design)

• Phil 4 ∥ Stick 3 ∥ Phil 3 ∥ Stick 2 ∥ Phil 2 ∥ Stick 1 ∥ Phil 1 ∥ Stick 0 ∥ Phil 0 ∥ Stick 4(processes communicate in a pairwise fashion over their common actions)

• Fault design: leads to a deadlock situation(think 4, avail 3, think 3, avail 2, think 2, avail 1, think 1, avail 0, think 0, avail 4)→*

(wait 4,0, occ4,4, wait 3,4, occ3,3, wait 2,3, occ2,2, wait 1,2, occ1,1, wait 0,1, occ0,0). (terminal state) the i-th

philosopher

the i-th stick

reqs,p, rels,p

phil p, stick s

03.05.23 91

Dijkstra’s problem of Dining Philosophers (deadlock free variant)

03.05.23 92

Two Dining Philosophers (deadlock free variant,simplified, 1/2)

rel 0,0

t

wl wr

e

rl rr

rec 1,0 rec 0,0

rec 0,0 rec 1,0

rel 0,0 rel 1,0

rel 1,0

t

wl wr

e

rl rr

rec 0,1 rec 1,1

rec 1,1 rec 0,1

rel 1,1 rel 0,1

rel 1,1 rel 0,1

a0

a1

O1 O2

Stick 0Prima data

il ridica doar Phil 0

rec 0,0

rel 0,0 rec 0,1

rel 0,1

Phil 0 Phil 1

a1

a0

O1 O2

Stick 1Prima data il ridica doar

Phil 0

rec 1,1

rel 1,1 rec 1,0

rel 1,0

03.05.23 93

Two Dining Philosophers (deadlock free variant,simplified, 2/2)

• The chanel System [Phil0 II Phil1 II Stick0 II Stick 1]

t,t,a0,a1

w,t,O1,a1 w,t,a0,O2

req 0, 0 req 1, 0

e,t,O1,O2req 1, 0

req 0, 0

r,t,a1,O2 r,t,O1,a1

rel 0, 0 rel 1, 0

Etc.

Deadlock and Starvation

free

03.05.23 94

Path and State graphs• Paths and State Graph

Let TS = (S, Act,→, I,AP, L) be a transition system.– The state graph of TS, notation G(TS), is the digraph (V,E) with

vertices V = S and edges E = {(s, s) S × S | s Post∈ ∈ (s)}.(It is simply obtained from TS by omitting all state labels (i.e., the atomic propositions), all transition labels (i.e., the actions), and by ignoring the fact whether a state is initial or not. Moreover, multiple transitions (that have different action labels) between states are represented by a single edge.

– Let Post∗(s) denote the states that are reachable in state graph G(TS) froms. For C S ⊆ let Post∗(C) = ⋃s∈Cpost(C)

– Notation. Reach(TS)=Post*(I)– The notations Pre∗(s) and Pre∗(C) have analogous meaning.

03.05.23 95

Path fragment and path

• A finite path fragment π of TS is a finite state sequence s0 s1 . . . sn such that si Post∈ (si−1) for all 0 < i ≤ n, where n ≥ 0.– An infinite path fragment π is an infinite state sequence s0 s1 s2

. . . such that si Post∈ (si−1) for all i > 0.– Notation: first (π)=s0; π[j]=sj; π[..j]=s0…sj; π[j..]=sj…;

For a finite path π =s0…sn, last (π)=sn, len(π)=nFor a infinite path π =s0…, last (π)=⊥, len(π)=∞

– A maximal path fragment is either a finite path fragment that ends in a terminal state, or an infinite path fragment.

– A path fragment is called initial if it starts in an initial state,• A path of transition system TS is an initial, maximal path fragment.• Paths(TS) denote the set of all paths in TS, and Pathsfin (TS) the set

of all initial, finite path fragments of TS.

03.05.23 96

Example. A transition system of a simple beverage vending machine.

• Example. Beverage Vending MachineThe state labeling is simply L(s) = { s }.Example path fragments:– π1 = pay select soda pay select soda . . . (Only π1 is a path) – π2 = select soda pay select beer . . . (maximal but not initial)– π = pay select soda pay select soda. (initial but not maximal)

.We have last(π) = soda, first(π2) = select, π1[0] = pay, π1[3] = pay ,

– π1[..5] = π, π[..2] = π[3..], len(π) = 5, and len(π1) = ∞.

03.05.23 97

Traces• We focus on the states that are visited during executions. (in fact, the

states themselves are not “observable”, but just their atomic propositions).

• Thus, rather than having an execution of the form

we consider traces of the form

L(s0)L(s1)L(s2) . . .

that register the (set of) atomic propositions that are valid along the execution.

• Traces of a transition system are thus words over the alphabet 2AP

• In the following it is assumed that a transition system has no terminal states. In this case, all traces are infinite words.– each transition system TS (that probably has a terminal state) can

be extended such that for each terminal state s in TS there is a new state trap, transition s→trap, and trap is equipped with a self-loop

• Definition. Trace and Trace FragmentLet TS = (S, Act,→, I,AP, L) be a transition system without terminal states. The trace of the infinite path fragment π = s0 s1 . . . is defined as trace(π) = L(s0)L(s1) . . .. The trace of the finite path fragment π = s0 s1 . . . sn is defined as trace(π) = L(s0)L(s1) . . .L(sn).

trace(Π) = { trace(π) | π ∈ Π}.

Traces(s) = trace(Paths(s)) Traces(TS) = ⋃s∈ITraces(s).

03.05.23 98

Example. Semaphore-Based Mutual Exclusion• The path π in the state graph of TSSem where process P1 is the first

to enter its critical section is of the formπ = <n1, n2, y = 1 >→ <w1, n2, y = 1 > → <c1, n2, y = 0> → <n1, n2, y = 1> → <n1,w2, y = 1> → <n1, c2, y = 0 >→ . . .

• The trace of this path is the infinite word:trace(π) = ∅∅{ crit1 }∅∅{ crit2 }∅∅{ crit1 }∅∅{ crit2 } . . . .

• The trace of the finite path fragmentπ = <n1, n2, y = 1> → <w1, n2, y = 1> → <w1,w2, y = 1> →<w1, c2, y = 0> → <w1, n2, y = 1> → <c1, n2, y = 0>is trace(π) = ∅∅∅{ crit2 }∅{ crit1 }.

TSSem

Assume the available atomic propositions are crit1 and crit2, i.e.,AP = { crit1, crit2 }.

03.05.23 99

Linear-Time Properties• Definition. LT Property.

A linear-time property (LT property) over the set of atomic propositions AP is a subsetof (2AP)ω.– Here, (2AP)ω denotes the set of words that arise from the infinite

concatenation of words in 2AP. An LT property is thus a language (set) of infinite words over the alphabet 2AP.

• Definition. Satisfaction Relation for LT Properties.Let P be an LT property over AP and TS = (S, Act,→, I,AP, L) a transition system without terminal states. – TS satisfies P, denoted TS |= P,

iff Traces(TS) P⊆ . – state s S ∈ satisfies P, notation s |= P, whenever Traces(s) P⊆ .

Thus, a transition system satisfies the LT property P if all its traces respect P, i.e., if all its behaviors are admissible. A state satisfies P whenever all traces starting in this state fulfill P.

• Often, an LT property does not refer to all atomic propositions occurring in a transition system, but just to a relatively small subset thereof AP1 AP⊆ ,traceAP1(π) = (L(s0) ∩ AP1) (L(s1) ∩ AP1) . . .

03.05.23 100

Example. Traffic Lights 1/2• AP = { red1, green1, red2, green2 }

Two fully synchronized traffic lights (left and middle) and their parallel composition(right).

03.05.23 101

Example. Traffic Lights 2/2• Consider the property P that states:

“The first traffic light is infinitely often green”.– This LT property corresponds to the set of infinite words of the form A0 A1 A2 …

over 2AP, such that green1 Ai ∈ holds for infinitely many i. For example, P contains the infinite words

• { red1, green2 }{green1, red2 }{red1, green2 }{green1, red2 } . . . • ∅{ green1 }∅{ green1 }∅{ green1 }∅{ green1 } ∅. . .• { red1, green1 }{red1, green1 }{red1, green1 }{red1, green1 } . . . and• { green1, green2 }{green1, green2 }{green1, green2 }{green1, green2 } . .

– The infinite word { red1, green1 }{red1, green1 }∅∅∅∅. . . is not in P as it contains only finitely many occurrences of green1.

• Consider P’:“The traffic lights are never both green simultaneously”.

– This property is formalized by the set of infinite words of the form A0 A1 A2 . . . such that either green1 ∉ Ai or green2 ∉ Ai, for all i. For example, the following infinite words are in P:

• { red1, green2 }{green1, red2 }{red1, green2 }{green1, red2 } . . . ,• ∅{ green1 }∅{ green1 }∅{ green1 }∅{ green1 }∅. . . and• { red1, green1 }{red1, green1 }{red1, green1 }{red1, green1 } . . . ,

– The infinite word { red1 green2 }{green1, green2 }, . . . is not in P.

03.05.23 102

The Mutual Exclusion LT Property• Pmutex = set of infinite words A0 A1 A2 . . . with { crit1, crit2 } ⊊ Ai

for all i.• For example, the infinite words

– { crit1 }{crit2 }{crit1 }{crit2 }{crit1 }{crit2 } . . . , and– { crit1 }{crit1 }{crit1 }{crit1 }{crit1 }{crit1 } . . . , and– ∅∅∅∅∅∅∅. . .

are all contained in Pmutex . • However, this does not apply to words of the form

– { crit1 }∅{ crit1, crit2 } . . .• The following transition systems fulfill the mutex property, i.e., TS |=

Pmutex .– TSArb = (TS1 ||| TS2) Arbiter – the semaphorebased mutual exclusion algorithm – Peterson’s algorithm

03.05.23 103

Starvation Freedom LT Property• Guaranteeing mutual exclusion is a significant property of mutual exclusion

algorithms, but is not the only relevant property. • An algorithm that never allows a process to enter its critical section will do,

but is certainly not intended. Besides, a property is imposed that requires a process that wants to enter the critical section to be able to eventually do so.

• This property prevents a process from waiting ad infinitum and is formally specified as the LT property (we assume AP = { wait1, crit1, wait2, crit2 }).Pfinwait = set of infinite words A0 A1 A2 . . . such that– ∀j.waiti A∈ j k ⇒ ∃ ≥ j.waiti A∈ k for each i {∈ 1, 2 }.

or by

Pnostarve:– ∃∞k.waiti A∈ k ⇒ ∃∞k .criti A∈ k

where ∃∞ stands for “there are infinitely many”.• This natural requirement is, however, not satisfied for the

semaphore-based solution, since– ∅ ({ wait2 }{wait1, wait2 }{crit1, wait2 } )ω is a possible trace of the

transition system but does not belong to Pnostarve.• Peterson’s algorithm does indeed satisfy Pnostarve .

03.05.23 104

Safety Properties

a bad prefix

A safety properties for a traffic light: Yellow-Red

03.05.23 105

03.05.23 106

Regular Safety Properties

Yellow-Red is a regular safety property

Pay-Drink is not regular!

The set of minimal bad prefixes

03.05.23 107

Alternative Characterization of Safety PropertiesP safety propertiy ⇔ closure (P)=P

Example. The property

Fair={σ | σ∈{A,B}ω , A occurs infinitely often⇒ B occurs infinitely often}

is not a safety property.

Indeed, aω ∈ closure(Fair) but aω is not in Fair.

03.05.23 108

Exemplu de specificare a unui sistem reactiv de inchidere a barierei la trecerea trenului

• Propoziţii atomice:td ≡ trenul e departe, bd ≡ bariera deschisăta ≡ trenul e aproape, bc ≡ bariera coboarăbi ≡ bariera inchisă, tt ≡ trenul trece pe la barierăvt ≡ ultimul vagon a trecut br ≡ bariera se ridică

• Safety properties:⌉ F G bi, bariera nu rămâne închisă definitiv niciodată G ⌉ (bd ∧ tt), la trecerea trenului bariera nu este deschisă

• Liveness properties:G(ta → Fbi), G(vt → Fbd), G F bd, G (ta → X (bc ∨ bi))G(bi → bi U vt ), bariera inchisă cât timp trece trenul

0 1 2 3 4

Modelul

{ td,bd} { ta,bc} { ta,bi} { tt,bi} { vt,br}

03.05.23 109

Trace Equivalence and Safety Properties

03.05.23 110

03.05.23 111

03.05.23 112

Reguli de echivalenţă semanticăEchivalenţă semantică:

φ≡ψ (adică în orice model şi în orice stare s, s⊨φ ⇔ s⊨ψ)

• Dualitate:– ⌉ Gφ ≡ F ⌉φ– ⌉ Fφ ≡ G⌉φ– ⌉ Xφ ≡ X ⌉ φ

• Idempotenţă:– G Gφ ≡ G φ– F Fφ ≡ Fφ – φU(φ U ψ) ≡ φ U ψ– (φUψ) U ψ ≡ φ U ψ

• Absorbţie:– G F G φ ≡ F G φ– F G F φ ≡ G F φ

• Comutare– X (φ U ψ) ≡ (Xφ) U (X ψ)

• Expansiune– φ U ψ ≡ ψ ∨ [φ ∧ X (φ U ψ )]– F φ ≡ φ ∨ X F φ– G φ ≡ φ ∧ X G φ

03.05.23 113

Logică temporală• În filozofie: A. Prior, 1960• În informatică: A. Pnueli, 1977• Modele de timp:

– continue (mulţimea numerelor reale)– discrete (mulţimea numerelor naturale)– Lineare (unui moment de timp îi succede un singur moment următor)– Ramificate (un moment de timp poate avea mai multe momente care îi succed)

03.05.23 114

Logică temporală lineară şi discretă, cu propoziţii(PLTL)

• PLTL, Propositional Linear Temporal Logic• Sintaxa PLTL

Alfabet:– AP, mulţime de propoziţii atomice

• Exemplu: x≥0– Conectori logici (clasici): ⋀, ∨, →, ↔– Conectori logici (temporali):

G (always)F (eventually, sometime, în cele din urmă) X (next)

– ParantezeDefiniţie. Formule PLTL (φ, nota).

φ ::=p| ⌉ φ | ( φ⋀ φ) |( φ ∨ φ) |( φ → φ) | ( φ ↔ φ) | G φ | F φ | X φ unde p∈AP

03.05.23 115

Semantica PLTL• Definiţie. Model PLTL (structură Kripke), M=(S,R,Label),

unde:– S este o multime nevidă, finită sau numărabilă de stări– R : S → S, funcţia succesor – Label: S →2AP, asociază fiecărei stări s o mulţime Label(s) a tuturor propoziţiilor

atomice valide (adevărate) în s.

Exemplu.S={0,1,2,3}Label(0)={x≠0}, Label(1)= Label(2)={x=0}, Label(3)={x=1, x≠0}unde R este data prin diagrama

Observaţie: x=1, x≠0 sunt propoziţii atomice, fără legătură între ele; din x=1în starea 3 nu rezultă că x≠0 în această stare.

• Secvenţe (infinite) de stări:s0, s1, ...si, ...unde s0 =R0 (s)=s, (starea iniţială) şi si+1=R (Ri (s))Exemplu:0,1,2,3,0,1,2,3,....

0 1 2 3

03.05.23 116

Semantica formulelor PLTL

Definiţie (). Fie M=(S,R,Label) model PLTL, φ formulă PLTL şi s stare.Relaţia s⊨ φ (s satisface pe φ) este definită prin inducţie structurală:

• φ∈Label(s), dacă φ∈AP• s⊨ ⌉φ ⇔ nu s⊨ φ • s⊨ (φ⋀ψ) ⇔ s⊨ φ şi s⊨ ψ etc.• s⊨ G φ ⇔ ∀i( Ri( s) ⊨ φ ) (always, generally, G)• s⊨ F φ ⇔ ∃i( Ri( s) ⊨ φ ) (eventually, in the future, F)• s⊨ X φ ⇔ R( s) ⊨ φ (next, X)

Alţi operatori:• s⊨ Φ U ψ, (Φ until ψ) ⇔ ∃i( Ri( s) ⊨ ψ ) şi ∀k( 0≤k<i ⇨ Rk( s) ⊨ φ )Exemplu.

M

⇔ {q} {q} {p,q} ⇔Fp Fp Fp Fp ⌉ Fp

⌉ G p ⌉ G p ⌉ G p ⌉ G p ⌉ G p

q U p q U p q U p

03.05.23 117

Formule PLTL frecvent utilizate• φ→ F ψ dacă iniţial φ, în cele din urmă şi ψ• G( φ→ F ψ) dacă la un moment dat φ, ulterior ψ• G F φ φ, de o infinitate de ori• F G φ φ permanent, de la un moment dat• G( φ→ X ψ) totdeauna φ este urmat de ψ • G( φ→ G φ) dacă la un moment dat φ, de atunci încolo mereu φ

(dacă o dată, atunci pentru totdeauna) • G( φ→ φ U ψ) dacă la un moment dat φ, ulterior ψ

dar φ se păstrează până la momentul ce precede aparitia lui ψ

03.05.23 118

First order representation of a Kripke structure• V, the set of system variables. We assume that the variables in V range over a

finite set D (the domain or universe of the interpretation). • A state is just a valuation s : V →D for the set of variables in V. • We can describe certain sets of states by first order formulas. In particular, the

initial states of the system can be described by a first order formula S0 over the variables in V.

• In order to represent sets of transitions between states, we create a second set of variables V' (the variables in V are present state variables and the variables in V' are next state variables.

• We refer to a set of pairs of states as a transition relation. If R is a transition relation, then we write R(V, V') to denote a formula that represents it.

• We now show how to derive a Kripke structure M = (S, S0, R, L) from the first order formulas S0 and R that represent the concurrent system.

– The set of states S is the set of all valuations for V. – The set of initial states So is the set of all valuations So for V that satisfy the formula

So. – Let s and s' be two states, then R(s, s') holds if R evaluates to True when each v is

assigned the value s(v) and each v’ is assigned the value s'(v). – The labeling function L : S → 2 AP is defined so that L(s) is the subset of all atomic

propositions true in s. – If v is a variable over the boolean domain, then v ∈L(s) indicates that s(v) = True, and

v ∉ L(s) indicates that s(v) = False• Because we require that the transition relation of a Kripke structure is always

total, we modify R so that R(s, s) holds. •

03.05.23 119

Kripke structures associated to sequential programs (1/2)

Sequential programs:• We describe a translation procedure C that takes the text of a sequential

program P and transforms it into a first order formula R that represents the set of transitions of the program. (Clarke Jr., Grunberg,)

• First, we define a labeling transformation that given an unlabeled program P results in a labeled program PL.– If P is not a composite statement (e.g., P is x := e, skip, wait, lock,

unlock, etc.), then PL=P. – If P = P1; P2 then PL = P1L; I": P2L. – If P = if b then P1else P2 end if, then

PL = if b then l1: P1L else l2 : P2L end if. – If P = while b do P1 end while, then

PL = while b do l1: P1L end while. • In the remainder of this section, we assume that P is a labeled statement

and that the entry and exit points of P are labeled by m and m' respectively. • Let pc be a special variable called the program counter that ranges over the

set of program labels and an additional value ⊥ called the undefined value. • The undefined value is needed when concurrent programs are considered.

In this case, pc = ⊥ indicates that the program is not active.

03.05.23 120

Kripke structures associated to sequential programs (2/2)• The set of initial states of the program P:

So (V ,pc) == pre(V) /\ pc = m.

• C(l, P, I') describes the set of transitions in P as a disjunction of all the transitions in the set.

• Assignment: C(l, v := e, l') ≡ pc = I /\ pc' = l' /\ v' = e /\ same(V \ {v})

• Skip: C(l, skip, 1') ≡ pc = I /\ pc' = l' /\ same(V)

• Sequential composition: C(l, PI; I": P2, l') ≡ C(I, P1, l") V C(l", P2, 1')

• Conditional: C(I, if b then l1 : P1 else l2 : P2 end if, I') is the disjunction of the following four formulas:

– pc = I /\ pc' = l1 /\ b /\ same(V) – pc = I /\ pc' = l2/\ not b /\ same(V) – C(l1, P1, l') – C (l2, P2, l')

• While: C(l, while b do I1 : P1 end while, l') is the disjunction of the following three formulas:

– pc = I /\ pc' = I1 /\ b /\ same(V) – pc = I /\ pc' = I' /\ not b /\ same(V) – C(l1, P1, I)

03.05.23 121

Kripke structures associated to concurrent programs (1/2)

• Concurrent program: P=cobegin P1 lI P2 lI . . . II Pn coend

• Labeling transformation:PL=cobegin l1:P1L l1’ lI. . . II ln: PnL ln’ coend

– we assume that no two labels are identical and that the entry and exit points of P are labeled m and m', respectively.

• Initial states of a concurrent program P is So(V, PC) == pre (V) /\ pc = m /\ /\j (pcj = ⊥),

• C (I, P=cobegin P1 lI P2 lI . . . II Pn coend, l') is the disjunction of three formulas:

– pc = I /\ pc1’ = l1/\ ... /\ pcn’=ln /\ pc' = ⊥ (initialisation)– pc = ⊥ /\ pc1 = l1’/\ ... /\ pcn=ln’ /\ pc' = l’ /\ pc1’ =⊥ /\ ... /\ pcn’=⊥

(termination)– (C(li, Pi, li’)∧ same(V\Vi) ∧ same(PC\{pci}))

03.05.23 122

Example: Asynchronous processes with shared variables (1/2)

Let us consider P= cobegin P1 P∥ 2 coendwhereP1= e1: x:=1; x:=x+1 e’1 and P2= e2: x:=1; x:=x+1 e’2,

• Labeling transformation: PkL= ek: x:=1; tk : x:=x+1 e’k

• We haveC(ek, Pk, e’k)≡ C(ek, x:=1, tk) ⋁ C(tk, x:=x+1, e’k)andC(ek, x:=1, tk) ≡ pck=ek pc’∧ k=tk x’=1 ∧ (Ck.a) C(tk, x:=x+1, e’k) ≡ pck=tk pc’∧ k=e’k x’=x+1 ∧ (Ck.b)

• Initial states:pc=m pc∧ 1= pc⊥ ∧ 2= ⊥

• C(m,P,m’) ≡(pc=m pc’∧ 1=e1 pc’∧ 2=e2) initialisation⋁(pc= pc⊥ ∧ 1=e’1 pc∧ 2=e’2 ∧ pc’=m’ pc’∧ 1= pc’⊥ ∧ 2= )⊥ termination⋁ C(e1, P1, e’1) ∧ pc’2=pc2⋁ C(e2, P2, e’2) ∧ pc’1=pc1

03.05.23 123

Example: Asynchronous processes with shared variables: Kripke structure (2/2)

(m, , , ?⊥ ⊥)

( ,e1,e2, ?⊥ )

initialization

( ,t1,e2, 1⊥ ) ( ,e1,t2, 1⊥ )

C2.a

( ,t1,t2, 1⊥ )( ,e’1,e2, 2⊥ ) ( ,e1,e’2, 2⊥ )

formulas C2.bC1.b

( ,e’1,t2, 1⊥ )

( ,e’1,e’2, 2⊥ )

(m’, , , ⊥ ⊥ 2)

( ,e’1,t2, 1⊥ )

( ,e’1,e’2, 2⊥ )

C2.b

termination

( ,e’1,t2, 2⊥ ) ( ,t1,e’2, 1⊥ )

( ,e’1,e’2, 3⊥ )

(m’, , , ⊥ ⊥ 3)

C1.b

C2.b

C2.a

C1.a

03.05.23 124

Kripke structures associated to concurrent programs (2/2)(shared variables and mutual esclusion)

• Shared variables: Vi is the set of variables that may be changed by process P i. Concurrent pro- • grams for which the sets Vi overlap are called shared variable programs. • process synchronization statements: provide processes with exclusive access to shared variables.

– These statements are atomic and treated by the labeling transformation accordingly. • Wait(b)

C(l, wait(b), l') is a disjunction of the following two formulas: – pci = l /\ pci’ = I /\ not b /\ same(Vi) – pci = l /\ pci’ = I’ /\ b /\ same(Vi)

• Lock(v)– similar to the statement wait(v = 0), except that when v = 0 is true the

transition changes the value of v to 1. This statement is often used to guarantee mutual exclusion by preventing more than one process from entering its critical region.

C(l, lock(v), I') is a disjunction of thefollowing two formulas: – pci = l /\ pci’ = I /\ v=1 /\ same(Vi) – pci = l /\ pci’ = I’ /\ v=0 /\ v’=1 /\ same(Vi)

• Unlock(v): – assigns the value 0 to the variable v. Typically, this statement enables

some other process to enter its critical region. C(l, unlock(v), I') is`pci = l /\ pci’ = I’ /\ v’=0 /\ same(Vi \{v})

03.05.23 125

The Filter Lock (1/4)• mutual exclusion protocols that work for n threads, where n is greater than

2. Filter lock, is a direct generalization of the Peterson lock to multiple threads.

class Filter implements Lock { int[] level; int[] victim; public Filter(int n) { level = new int[n]; victim = new int[n]; // use 1..n-1 for (int i = 0; i < n; i++) {

level[i] = 0;}

}

03.05.23 126

The Filter Lock (2/4) public void lock() {

int me = ThreadID.get();for (int i = 1; i < n; i++) { //attempt level 1

level[me] = i;victim[i] = me;// spin while conflicts existwhile (( k != me) (level[k] >= i && victim[i] == me)) {};∃

} } public void unlock() {

int me = ThreadID.get();level[me] = 0;

}}The Filter lock algorithm.

03.05.23 127

The Filter Lock (3/4)

03.05.23 128

The Filter Lock (4/4)

Lemma. For j between 0 and n − 1, there are at most n − j threads atlevel j.Proof: By induction on j.

Corollary. The Filter lock algorithm satisfies mutual exclusion.

Lemma. The Filter lock algorithm is starvation-free.

Proof: We argue by reverse induction on the levels. The base case, level n − 1, istrivial, because it contains at the most one thread. For the induction hypothesis,assume that every thread that reaches level j + 1 or higher, eventually enters (and leaves) its critical section.

Corollary. The Filter lock algorithm is deadlock-free.

03.05.23 129

Lamport’s Bakery Algorithm

03.05.23 130

Exemplu de demonstraţie a echivalenţei semantice (1/2)

• φ U ψ ≡ ψ ∨ [φ ∧ X (φ U ψ )] s⊨ψ ∨ [φ ∧ X (φ U ψ )]⇅s⊨ψ ∨ ( s⊨φ ∧ s⊨ X (φ U ψ ))⇅ s⊨ψ ∨ ( s⊨φ ∧ R(s)⊨ φ U ψ )⇅ s⊨ψ ∨ s⊨φ ∧ ∃ j≥0 (Rj( R(s))⊨ ψ ∧ ∀k (0≤k<j ⇨ Rk (R(s)) ⊨ φ ))⇅ s⊨ψ ∨ (deoarece ∃ j F(j) ∧ G ≡ ∃ j [F(j) ∧ G ]∃ j≥0 (Rj+1(s)⊨ ψ ∧ ∀k (0≤k<j ⇨ Rk+1(s) ⊨ φ )∧ s⊨φ )⇅ ∃ j≥0 (j=0 ∧ Rj (s)⊨ ψ ∧ ∀k (0≤k<j ⇨ Rk(s) ⊨ φ )) ( adica s⊨ψ )∨ (substituind k+1 prin k si deoarece R0(s)=s ) ∃ j≥0 (Rj+1(s)⊨ ψ ∧ ∀k (0≤k<j+1 ⇨ Rk(s) ⊨ φ ))⇅ (substituind j+1 prin j) ∃ j≥0 (Rj (s)⊨ ψ ∧ ∀k (0≤k<j ⇨ Rk(s) ⊨ φ ))

03.05.23 131

Exemplu de demonstraţie a echivalenţei semantice (2/2)• φU(φ U ψ) ≡ φ U ψ

s⊨φU(φ U ψ) ⇅∃ j≥0 (Rj( s)⊨ φ U ψ

∧ ∀k (0≤k<j ⇨ Rk (s) ⊨ φ ))⇅ ∃ j≥0 (∃ i≥0 (Rj+i( s)⊨ ψ ∧ ∀k (j≤k<j+i ⇨ Rk (s) ⊨ φ ) )

∧ ∀k (0≤k<j ⇨ Rk (s) ⊨ φ ))⇅ (deoarece ∃ i≥0 (F(i) ∧ G) ≡ ∃ i≥0 F(i) ∧ G, i∉var(G) ) ∃ j≥0 (∃ i≥0 (Rj+i( s)⊨ ψ ∧ ∀k (j≤k<j+i ⇨ Rk (s) ⊨ φ )

∧ ∀k (0≤k<j ⇨ Rk (s) ⊨ φ )))⇅ (deoarece ∀k (F(k) ∧ G(k)) ≡ ∀k F(k) ∧ ∀k G(k) ) ∃ j≥0 (∃ i≥0 (Rj+i( s)⊨ ψ ∧ ∀k (j≤k<j+i ⇨ Rk (s) ⊨ φ ∧ (0≤k<j ⇨ Rk (s) ⊨ φ )))⇅ (deoarece F ⇨ G ∧ H⇨ G ≡ (F ∨ H) ⇨G) ∃ j≥0 (∃ i≥0 (Rj+i( s)⊨ ψ ∧ ∀k (j≤k<j+i ∨ 0≤k<j ⇨ Rk (s) ⊨ φ)))⇅ ∃ j≥0 ( (Rj( s)⊨ ψ ∧ ∀k (0≤k<j ⇨ Rk (s) ⊨ φ)))

03.05.23 132

The Computation Tree Logic CTL *, syntax • Syntax: there are two types of formulas in CTL *:

– state formulas (which are true in a specific state) – path formulas (which are true along a specific path).

Let AP be the set of atomic proposition names. state

– If p∈A P, then p is a state formula. – If f and g are state formulas, then ⌉ f, f V g and f /\ g

are state formulas.

state to path

– If f is a state formula, then f is also a path formula.

Path

– If f and g are path formulas, then

⌉f, f V g, f /\ g, X f, F f, G f, f U g, (and f R g) are path formulas.

path to state

– If f is a path formula, then E f and A f are state formulas.

AP

state⌉,∨,∧

path

⌉,∨,∧

X,F,G,U

A, E

03.05.23 133

The Computation Tree Logic CTL *, semantics Semantics:

M=(S,R,L) , Kripke structure, where R SxS, total transition relation⊆

s, state; x, infinite path in M, xk, suffix of x starting at the state xk

p, atomic proposition; f state formulas; g path formulas1. M, s ⊧ p ⇔p ∈ L(s). 2. M,s ⊧ ⌉f ⇔ M,s ⊭ f. 3. M, s ⊧ f1 V f2 ⇔ M,s f⊧ 1 or M,s⊧ f2. 4. M, s E g ⇔ there is a path ⊧ x from s such that M, x g. ⊧5. M,s A g ⇔ for every path ⊧ x starting from s, M, x g. ⊧6. M, x ⊧ f ⇔ s is the first state of x and M, s f. ⊧7. M,x⊧ ⌉ g⇔ M,x ⊭ g 8. M, x g⊧ 1 V g2⇔ M, x g⊧ 1 or M, x g⊧ 2. 9. M, x X g⇔ M, ⊧ x1 g. ⊧10. M,x F g ⇔ there exists a k ⊧ ≥0 such that M, xk g. ⊧11. M, x G g⇔ for all i ⊧ ≥0, M, xi g. ⊧12. M, x g⊧ 1 U g2 ⇔ there exists a k ≥0 such that M, xk g⊧ 2 and

for all 0 ≤j < k, M, xj g⊧ 1.

13. M, x g⊧ 1 R g2 ⇔ for all j ≥0, if for every i < j M, xi g⊧ 1 then M, xj g⊧ 2.

03.05.23 134

CTL, LTL• CTL is a restricted subset of CTL*, in

which each temporal operator X,F,G,U,R must be imediatelly precede by a path quantifier A, E.Basic CTL operators:AX, EXAF, EFAG, EGAU, EUAR, ER

• LTL (Linear Temporal Logic ) consists of formulas that have the form A f where f is a path formula in PLTL in which the only state subformulas permitted are atomic propositions. • More precisely, the path formula f is

either: • p ∈AP, • ⌉h, h V g, h /\ g, X h, F h, G h, hU g,

and hR g where h and g are path formulas.

• LTL,CTL, CTL* have different expressive powers. – A (FG p) :along every path, there is

some state from which p will hold forever.

CTL*

CTL

LTL

A (FG p)

AG(EF p).

A (FG p) ∨ AG(EF p)

03.05.23 135

Equivalence rules in CLT*AXf ≡ ⌉EX(⌉f) EF f ≡ E[TrueU f]AG f ≡ ⌉EF(⌉f) AF f ≡ ⌉EG(⌉f) A[f U g] ≡ ⌉E[⌉g U (⌉f /\ ⌉g)] /\ AFg A[fRg] ≡ ⌉E[⌉fU⌉g] E[fRg] ≡ ⌉A[⌉fU⌉g] • Some typical CTL formulas that might

arise in verifying a finite state concurrent program

– EF(Start /\ ⌉Ready): It is possible to get to a state where Start holds but Ready does not hold.

– AG(Req → AF Ack): If a request occurs, then it will be eventually acknowledged.

– AG(AF DeviceEnabled): The proposition DeviceEnabled holds infinitely often on every computation path.

• AGF Device Enabled has the same meaning, but it is not a CTL formula

– AG(EF Restart): From any state it is possible to get to the Restart state.

03.05.23 136

Model Checking• The model checking problem :

Given a Kripke structure M = (S, R, L) that represents a finite-state concurrent system and a temporal logic formula f expressing some desired specification, find the set of all states in S that satisfy f: {s ∈ S I M, s ⊨ f }

03.05.23 137

CTL Model checking

• CTL model checking– The algorithm will operate by labeling each state s with the set

label(s) of subformulas of f which are true in s. Initially, label(s) = L(s).

– The algorithm then goes through a series of stages. During the ith stage, subformulas with i-1 nested CTL operators are processed.

– When a subformula is processed, it is added to the labeling of each state in which it is true.

– Once the algorithm terminates, we will have M, s ⊨ f iff f ∈ label(s).

• Any CTL formula can be expressed in terms of ⌉, V, EX, EU and EG. Thus, for the intermediate stages of the algorithm it is sufficient to be able to handle six cases, depending on whether g is atomic or has one of the following forms:

1. ⌉f, (label those states that are not labeled by f. )2. f V g, (label those states that are labeled by f or by g. )3. EX f, (label every state that has some successor labeled by f). 4. E[f U g], (see algorithm checkEU)5. EG f. (see algorithm checkEG)

03.05.23 138

Procedure for labeling states satisfying E(f U g)

procedure checkEU(f, g) T := {s | g ∈ label(s) }; for all s∈T do label(s) := label(s) U { E[f U g] }; while T≠ ∅ do choose s∈T; T:= T \ {s}; for all t such that R(t, s) do if E[f U g] not in label(t) and f in label(t) then label(t) := label(t) U { E[f U g] }; T:=TU{t}; endif;end for all; end while;

end procedure Inv:

(f∈label(s) ⇒ s⊨f) ∧(t∈T ⇒ t⊨ E(fUg))[E(fUg)∉label(s) ∧ s⊨E(fUg)⇒∃t(t∈T ∧∃p=s0,…sk,t ∧ s0=s ∧ k≥0 ∧ ∀i(si f⊨ )]

term:

(|T|, |E ∖ M|)

where:E={s| s E(fUg)}⊨M={s| E(fUg) f label(s) }∈

03.05.23 139

Auxiliary results for EG• The case in which g = EG f is based on the decomposition of the

graph into nontrivial strongly connected components. • A strongly connected component (SCC) C is a maximal subgraph

such that every node in C is reachable from every other node in C along a directed path entirely contained within C.

• C is nontrivial iff either it has more than one node or it contains one node with a self-loop.

• Let M' be obtained from M by deleting from S all of those states at which fl does not hold and restricting R and L accordingly. Thus, M' = (S', R', L') – Note that R' may not be total in this case.

• The states with no outgoing transitions may be eliminated, but this is not essential for the correctness of our algorithm. The algorithm depends on the following observation.

• LEMMA. M, s ⊨ EG f iff the following two conditions are satisfied:

1. s E S'. 2. There exists a path in M' that leads from s to some node t in a nontrivial

strongly connected component e of the graph (S', R').

03.05.23 140

Procedure for labeling states satisfying EGf

procedure checkEG(fJ) S' := { s I f ∈ label(s) }; SCC := { C I C is a nontrivial SCC of S'}; T := union of all C in SCC; for all s in T do label(s) := label(s) U { EG f }; while T <> 0 do

choose s in T; T:=T\{s}; for all t such that t in S' and R(t, s) do

if EG f not in label(t) then label(t) := label(t) U { EG f }; T:=TU{t};

end if; end for all;

end while; end procedure

03.05.23 141

Example EGf• C1 ={1,2,3}• C2 ={6}• C3 ={7}

{4} si {5} sunt triviale

• Answer from Algorithm EG:• 8, 5 does not satisfy EGf

1

2

3

4

5

6

7

f

f f

f

f

ff

f

8 not f

03.05.23 142

Time complexity of CTL Model Checking

• THEOREM.There is an algorithm for determining whether a CTL formula f is true in a states of the structure M = (S, R, L) that runs in time O(l f l * (ISI + IRI)). – In order to handle an arbitrary CTL formula f, we

successively apply the state-labeling algorithm to the subformulas of f, starting with the shortest, most deeply nested, and work outward to include all of f. By proceeding in this manner we guarantee that whenever we process a subformula of f all its subformulas have already been processed. Since each pass takes time O(ISI + IRI) and since f has at most If I different subformulas, the entire algorithm requires time O(l f l . (ISI + IRI)).

03.05.23 143

Example. Microwave oven specification

03.05.23 144

Check AG(Start→AF Heat)• AG(Start→AF Heat)≡ EF(Start EG Heat)⌉ ∧ ⌉• S(g) denote the set of all states labelled by g• S(Start)={2,5,6,7}• S’=S(⌉Heat) = {I, 2, 3, 5, 6}. • SCC = {{l, 2, 3, 5}}. • Initially T = {I, 2, 3, 5}. • The computation terminates with

S(EG ⌉Heat) = {I, 2, 3, 5}. • S(Start /\ EG.....H eat) = {2, 5}. • We get S(EF(Start /\ EG⌉Heat» = {1, 2, 3, 4,5,6, 7}. • Finally, we compute that

• S(⌉ EF(Start /\ EG ⌉Heat)) = 0.

• Since the initial state 1 is not contained in this set, we conclude that the system described by the Kripke structure does not satisfy the given specification.

03.05.23 145

Reţele Petri • Petri nets: originated from the doctoral thesis of C.A. Petri in 1962

03.05.23 146

Firing a transition

03.05.23 147

Infinite/finite capacity net

Weak tranzition rule

(infinite capacity)

Strong tranzition rule

(finite capacity)

03.05.23 148

Complementary place transformation

pn i

p’

in

K(p)=k

M(p)=m

M(p’)=k-m

Strict tr. Rule

n+m<=k

weak tr. Rule

n<=M(p’)

03.05.23 149

03.05.23 150

Concurrency

t1

p1

p2

at2

p3

p4

b

Asynchronous concurrency

Shuffle((t1 a)*, (t2 b)*)

t1

p1

p2

at2

p3

p4

b

Synchronous concurrency

(Shuffle(t1, t2) t3 Shuffle(a t1, b t2))*

t3

p5 p6

03.05.23 151

03.05.23 152

Parallel activities with synchronisation

03.05.23 153

Communication protocols

• Model de comunicare: nu se transmite un alt mesaj daca nu s-a primit confirmare de primire a celui anterior

process

Ready to send

send msg

Ready to process

process

Receive ack

Waiting for ack

Transmiter

Ready to receive

receive msg (copy in a private buffer)

Msg received

Send acknoledgement

Process msg from private buffer

Ack sent

Receiver

Msg buffer full

Ack buffer full

03.05.23 154

Synchronization control: mutual exclusion

Working independently

Request accesss

Waitimg for CS

Receive accesss

CS busy with C1 CS busy with C2

p3 şi p7,

nu sunt amandoua marcate în acelaşi timp

03.05.23 155

Synchronization control: producer-consumer,unbounded buffer

Ready to produce Ready to consume

produces receives

send

Ready to consume

consume

03.05.23 156

Synchronization control: producer-consumer,finite buffer

free

filled

produce

send

receive

consume

03.05.23 157

Synchronization control: readers-writers

03.05.23 158

Formal languages

03.05.23 159

Behavioral properties(marking dependent)

(Tadao Murata)

03.05.23 160

ReachabilityBoundness

• A. Reacheability: M∈L(M0)?

– Reachebility is decidable– Equivalence

(L(N1,M1)=L(N2,M2)) is not decidable

• B. Boundedness

03.05.23 161

Liveness

• C. Liveness

L4⇒ L3⇒ L2⇒ L1

03.05.23 162

Liveness, examples

03.05.23 163

Reversibility and Home state

03.05.23 164

Boundness, Liveness and Reversibilityare inependent of each other (1/3)

03.05.23 165

Boundness, Liveness and Reversibilityare inependent of each other (2/3)

03.05.23 166

Boundness, Liveness and Reversibilityare independent of each other (3/3)

03.05.23 167

Coverability

03.05.23 168

Persistence

marked graph ⇒ persistenceBut not conversely!

03.05.23 169

G. Synchronic distance

03.05.23 170

H. Fairness

03.05.23 171

Analysis techniques• The reachability tree and reachability graph

– The reachability set R(M1) of a PN is generated by means of the reachability tree (markings are nodes, transitions are arcs).

– By properly identifying the frontier nodes of the tree, the generation of the reachability tree involves a finite number of steps even if the PN is unbounded.

• Three kinds of frontier nodes:– ² terminal (dead) nodes: nodes in which no transitions are enabled;– ² duplicate nodes: nodes which have been already generated in the tree;– infinitely reproducible nodes.

03.05.23 172

Example

03.05.23 173

Example: reacheability graph

03.05.23 174

Reacheability graph for mutual exclusion

03.05.23 175

Reacheability graph for producer- consumer with unbounded buffer

03.05.23 176

Bibliografie1. Alagar, V.S.; Periyasamy, K.: Specification of software systems,

Springer, 19982. Katoen, J.-P.: Concepts, Algorithms, and Tools for Model

Checking, Friedrich-Alexander Universität Erlangen-Nürnberg, 1998

3. Baier, Ch., Katoen, J.-P.: Principles of model checking , Massachusetts Institute of Technology, 2008

4. Bailie, J.: An Introduction to the Algebraic Specification of Abstract Data Types, 1989

5. Clarke, E. M. Jr., Grumberg, O., Peled, D. A.: Model Checking, 2000

6. Meyer, B.: Object Oriented Software Construction, Prentice Hall, 1997, second edition

7. http://www.masterliness.com/a/Abstract.data.type.htm8. http://www.cs.unc.edu/~stotts/COMP204/senotes/L06.html9. http://www.cise.ufl.edu/~jnw/COP5555-200308/Lectures/Algebrai

cSpec.ppt#210. Pinzon, L., Jafari

, M., Boucher, T.: A Comparative Study of Synthesis Methods for Discrete Event Controllers

03.05.23 177

GARBAGE

03.05.23 178

Example. Mutual Exclusion in asynchronous processes: Mutual Exclusion with Semaphores (Baier,Katoen, 2008)(1/3).

noncrit k wait k crit kProgram graph of Process k:

y=1: y:=0

guard action

y:=1

Process k:loop forever ... (* noncritical actions *) request critical section release ... (* noncritical actions *)end loop

Mutual exclusion: two processes cannot be simultaneously in their critical section

y is a semaphore:y=0, locked

y=1, free

label