Počet komunikačních systémů - Calculus of communicating systems

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Počet komunikačních systémů"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Listopadu 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

The počet komunikačních systémů (CCS) je procesní kalkul představil Robin Milner kolem roku 1980 a název knihy popisující počet. Jeho akce modelují nedělitelnou komunikaci mezi přesně dvěma účastníky. Formální jazyk obsahuje primitiva pro popis paralelního složení, volby mezi akcemi a omezení rozsahu. CCS je užitečné pro hodnocení kvalitativní správnosti vlastností systému, jako je zablokování nebo živý zámek.^[1]

Podle Milnera „Není nic kanonického na výběru základních kombinátorů, i když byly vybrány s velkou pozorností k ekonomice. To, co charakterizuje náš počet, není přesná volba kombinátorů, ale spíše volba interpretace a matematického rámce ".

Výrazy jazyka jsou interpretovány jako a označený přechodový systém. Mezi těmito modely bisimilarity se používá jako sémantická ekvivalence.

Syntax

Vzhledem k sadě názvů akcí je sada procesů CCS definována následujícím způsobem BNF gramatika:

${ Displaystyle P :: = 0 , , , | , , , a.P_ {1} , , , | , , , A , , , | , , , P_ {1} + P_ {2} , , , | , , , P_ {1} | P_ {2} , , , | , , , P_ { 1} [b / a] , , , | , , , P_ {1} { zpětné lomítko} a , , ,}$

Části syntaxe jsou v pořadí uvedeném výše

neaktivní proces

neaktivní proces ${ displaystyle 0}$ je platný proces CCS

akce

proces ${ displaystyle a.P_ {1}}$ může provést akci ${ displaystyle a}$ a pokračujte jako proces ${ displaystyle P_ {1}}$

identifikátor procesu

psát si ${ displaystyle A { overset { underset { mathrm {def}} {}} {=}} P_ {1}}$ použít identifikátor ${ displaystyle A}$ odkazovat na proces ${ displaystyle P_ {1}}$ (který může obsahovat identifikátor ${ displaystyle A}$ samotné, tj. rekurzivní definice jsou povoleny)

výběr

proces ${ displaystyle P_ {1} + P_ {2}}$ může pokračovat buď jako proces ${ displaystyle P_ {1}}$ nebo proces ${ displaystyle P_ {2}}$

paralelní složení

${ displaystyle P_ {1} | P_ {2}}$ říká, že procesy ${ displaystyle P_ {1}}$ a ${ displaystyle P_ {2}}$ existují současně

přejmenování

${ displaystyle P_ {1} [b / a]}$ je proces ${ displaystyle P_ {1}}$ se všemi pojmenovanými akcemi ${ displaystyle a}$ přejmenován na ${ displaystyle b}$

omezení

${ displaystyle P_ {1} { zpětné lomítko} a}$ je proces ${ displaystyle P_ {1}}$ bez akce ${ displaystyle a}$

Související kameny, modely a jazyky

• Komunikace postupných procesů (CSP), vyvinutý společností Tony Hoare, je formální jazyk, který vznikl ve stejnou dobu jako CCS.
• The Algebra komunikačních procesů (ACP) vyvinula Jan Bergstra a Jan Willem Klop v roce 1982 a používá axiomatický přístup (ve stylu Univerzální algebra ) uvažovat o podobné třídě procesů jako CCS.
• The pí-počet, vyvinutý společností Robin Milner, Joachim Parrow a David Walker na konci 80. let rozšiřují CCS o mobilitu komunikačních spojení tím, že umožňují procesům komunikovat názvy samotných komunikačních kanálů.
• PEPA, vyvinutý společností Jane Hillston zavádí načasování aktivity z hlediska exponenciálně distribuovaných rychlostí a pravděpodobnostní volby, což umožňuje vyhodnocování metrik výkonu.
• Reverzibilní komunikující souběžné systémy (RCCS) zavedené Vincent Danos, Jean Krivine a další zavádí (částečnou) reverzibilitu při provádění procesů CCS.

Některé další jazyky založené na CCS:

• Počet vysílacích systémů
• Jazyk specifikace dočasného objednání (LOTOS)
• Procesní kalkul pro prostorově explicitní ekologické modely (PALPS) je rozšíření CCS s pravděpodobnostní volbou, umístěním a atributy pro umístění^[2]
• Stroj pro tlumočení jazyka Java Orchestration (Jolie)^[3]

Modely, které byly použity při studiu systémů podobných CCS:

• Historie monoidů
• Herecký model

Reference

• Robin Milner: Počet komunikačních systémůSpringer Verlag, ISBN  0-387-10235-3. 1980.
• Robin Milner, Komunikace a souběžnost, Prentice Hall, International Series in Computer Science, ISBN  0-13-115007-3. 1989