Milners Kalkül Kommunizierender Systeme (CCS)

Milners Kalkül Kommunizierender Systeme(CCS)

Arnaud Fietzkebetreut durch Tim Priesnitz, Guido Tack

Programming Systems Lab – Prof. Gert Smolka

Proseminar: Theorie kommunizierender Systeme

Modellierung nebenläufiger Systeme

A A‘

a

B‘ Bc_

_b

>

b

A = a.A‘ B = b.B‘A‘ = b.A B‘ = c.B

<

_ _

Modellierung nebenläufiger Systeme

A A‘

a

B‘ Bc_b

_b

>

<

A = a.A‘ B = b.B‘A‘ = b.A B‘ = c.BA = a.A‘ B = b.B‘A‘ = b.A B‘ = c.B

A|B mit

_ _

CCS

Übersicht

• Einführung

• Syntax CCS

• Semantik CCS• Idee• Strukturelle Kongruenz• Reaktion

Einführung

Prozessalgebra:

• algebraische Modellierung von nebenläufigen Prozessen

• Darstellung komplexer Systeme mit Hilfe weniger Operatoren

• ermöglicht automatische Verifikation

Prozessalgebren: Ansätze

• CCS (Calculus of Communicating Systems)[Milner '80]

• CSP (Communicating Sequential Processes)[Hoare '85]

• ACP (Algebra of Communicating Processes)[Bergstra & Klop '84]

• LOTOS (Language of Temporal Ordered Specification)[Brinksma & Draft '88]

Syntax CCS

Definition:

P ::= A<a1,...,an>Menge P der Prozessausdrücke:

mit I endliche IndexmengeiI

| i.Pi

0 := mit I = 0iI

i.Pi

N N { }N = {a,b,c,…} Namen

_

| P1|P2 | new a P

System von nebenläufigen Prozessen:

P1 | … | Pn mit P1 ...=

Pn ...=

...

Semantik CCS

Idee: "chemical machine"

An “Ports“ können beobachtbare Aktionenstattfinden ( N N)

_

[Berry & Boudol '89]

Semantik CCS

Idee: "chemical machine"

Komplementäre “Ports“ sind Reaktionspunktez.B. und

_

[Berry & Boudol '89]

Semantik CCS

Idee: "chemical machine"

"Moleküle" können sichannähern und reagierenannähern

[Berry & Boudol '89]

Prozess-Kongruenz

Definition :

Äquivalenzrelation (reflexiv, symmetrisch, transitiv) über P mit

.P + Mnew a PP|RR|P

.Q + Mnew a QQ|RR|Q

falls P Q

Prozess-Kontext

Definition :

C ::= | a.C+M | new a C | C|P | P|C

C[Q] : Substitution von [] in C durch QFür C=[] gilt: C[Q] = Q

[]

Eine bestimmte Prozess-Kongruenz lässt sich durchein Gleichungssystem definieren :

3

Prozess-Kongruenz

Eine bestimmte Prozess-Kongruenz lässt sich durchein Gleichungssystem definieren :

3

• erfüllt alle Gleichungen aus• für jede Sequenz Q1,…Qn (n≥1) von Ausdrücken gilt Q1 Qn falls Qi = C[P] und Qi+1 = C[P‘] und es gilt: P P‘ oder P‘ P

3

Strukturelle Kongruenz

Definition:

(1) Änderung gebundener Namen

Prozess-Kongruenz , definiert durch Gleichungen:

(new b) a.b (new c) a.cBeispiel:

Strukturelle Kongruenz

Definition:

(1) Änderung gebundener Namen

(2) Umordnung der Terme in Summen

Prozess-Kongruenz , definiert durch Gleichungen:

a.0 + b.0 b.0 + a.0Beispiel:

Strukturelle Kongruenz

Definition:

(1) Änderung gebundener Namen

(2) Umordnung der Terme in Summen(3) P|0 P

Prozess-Kongruenz , definiert durch Gleichungen:

, P|Q Q|P, P|(Q|R) (P|Q)|R

Strukturelle Kongruenz

Definition:

(1) Änderung gebundener Namen

(2) Umordnung der Terme in Summen(3) P|0 P, P|Q Q|P, P|(Q|R) (P|Q)|R

(4) new a (P|Q) P|new a Q falls a nicht frei in P

Prozess-Kongruenz , definiert durch Gleichungen:

, new ab P new ba Pnew a 0 0,

Strukturelle Kongruenz

Definition:

(1) Änderung gebundener Namen

(2) Umordnung der Terme in Summen(3) P|0 P, P|Q Q|P, P|(Q|R) (P|Q)|R

(5) A<b> { } PA falls A(a) = PA

Prozess-Kongruenz , definiert durch Gleichungen:

ba

(4) new a (P|Q) P|new a Q falls a nicht frei in P , new ab P new ba Pnew a 0 0

,

Strukturelle Kongruenz

Definition:

(1) Änderung gebundener Namen

(2) Umordnung der Terme in Summen(3) P|0 P, P|Q Q|P, P|(Q|R) (P|Q)|R

(5) A<b> { } PA falls A(a) = PA

Prozess-Kongruenz , definiert durch Gleichungen:

ba

(4) new a (P|Q) P|new a Q falls a nicht frei in P , new ab P new ba Pnew a 0 0

,Notation:a Sequenz von Namen a1,…,an

Standardform

Definition:

Ausdrucknew a (M1|…|Mn) mit Mi nichtleere Summe (1 ≤ i ≤ n)

ist in Standardform.

Falls n=0, M1|…|Mn = 0Falls a leer, fällt new a weg

Theorem:

Jeder Prozessausdruck ist strukturell kongruent zu einerStandardform.

Semantik nebenläufiger Prozessausdrücke

Idee: "chemical machine"

"Moleküle" können sichannähern und reagierenreagieren

[Berry & Boudol '89]

Semantik nebenläufiger Prozessausdrücke

Idee: "chemical machine"

"Moleküle" können sichannähern und reagieren

[Berry & Boudol '89]

Semantik nebenläufiger Prozessausdrücke

Idee: "chemical machine"

"Moleküle" können sichannähern und reagieren

Reaktionen sind von aussennicht mehr beobachtbar:-Transitionen

[Berry & Boudol '89]

Reaktion

Definition:Relation auf P wird durch Regeln definiert:

TAU : .P + M P

PAR : P P'P|Q P'|Q

RES : P P'new a P new a

P'STRUCT : P P'

Q Q'falls P Q und P' Q'

REACT : (a.P + M)|(a.Q + N) P|Q

Beispiel

A = a.A‘ B = b.B‘

A‘ = b.A B‘ = c.B_ _

A‘|B mit

Inferenzbaum:

A‘|B A|B‘

b.A|b.B‘ A|B‘_

STRUCT

REACT

Beispiel

Alternative Reaktionen:

P = a.0 | a.A | a.B_ _

Zwei Reaktionen sind möglich:

P A|a.B_

Beispiel

Alternative Reaktionen:

P = a.0 | a.A | a.B_ _

P A|a.BP a.A| Bund

Zwei Reaktionen sind möglich:

Indeterminismus durch Reaktion

__

Referenzen

• Milner, R., Communicating and Mobile Systems: the π – Calculus, Cambridge University Press, 1999

• Milner, Operational & Algebraic Semantics of Concurrent Processes Handbook of Theoretical Computer Science B, Elsevier, 1990