Komunikující stroj konečného stavu - Communicating finite-state machine

v počítačová věda, a komunikující konečný stavový stroj je konečný stavový stroj označeny operacemi „příjem“ a „odeslání“ přes nějakou abecedu kanálů. Představili je Brand a Zafiropulo,^[1] a lze jej použít jako model souběžně procesy jako Petriho sítě. Komunikační stroje s konečným stavem se často používají pro modelování komunikačního protokolu, protože umožňují detekovat hlavní chyby návrhu protokolu, včetně omezenosti, zablokování a nespecifikovaných příjmů.^[2]

Výhodou komunikace strojů s konečným stavem je to, že umožňují rozhodovat o mnoha vlastnostech v komunikačních protokolech nad úroveň pouhé detekce takových vlastností. Tato výhoda vylučuje potřebu lidské pomoci nebo omezení obecnosti.^[1]

Komunikace konečných stavových automatů může být výkonnější než konečných stavových automatů v situacích, kdy zpoždění šíření není zanedbatelné (aby bylo možné přenášet několik zpráv najednou) a v situacích, kdy je přirozené popsat strany protokolu a komunikační médium jako samostatné entity.^[1]

Komunikace hierarchického státního stroje

Hierarchické stavové automaty jsou konečné stavové automaty, jejichž stavy samy o sobě mohou být jinými stroji. Protože komunikující konečný stavový stroj je charakterizován souběžností, nejpozoruhodnější vlastností v a komunikující hierarchický stavový stroj je koexistence hierarchie a souběžnosti. To bylo považováno za velmi vhodné, protože to znamená silnější interakci uvnitř stroje.

Ukázalo se však, že koexistence hierarchie a souběžnosti skutečně stojí za zahrnutí jazyka, jazykovou ekvivalenci a veškerou univerzálnost.^[3]

Definice

Protokol

Pro libovolné kladné celé číslo ${ displaystyle N}$, a protokol ^[1]:3 s ${ displaystyle N}$ proces (procesy) je čtyřnásobný ${ displaystyle {(S_ {i}) _ {i = 1} ^ {N}, (o_ {i}) _ {i = 1} ^ {N}, (M_ {i, j}) _ {i, j = 1} ^ {N}, ({ mathtt {succ}}) _ {i = 1} ^ {N} }}$ s:

• ${ displaystyle (S_ {i}) _ {i = 1} ^ {N}}$posloupnost ${ displaystyle N}$ disjunktní konečné množiny. Každá sada se používá k představení procesu a každého prvku ${ displaystyle S_ {i}}$ představuje možný stav ${ displaystyle i}$-tý proces.
• ${ displaystyle (o_ {i}) _ {i = 1} ^ {N}}$ (s ${ displaystyle o_ {i} v S_ {i}}$), sekvence představující počáteční stav každého procesu.
• ${ displaystyle (M_ {i, j}) _ {i, j = 1} ^ {N}}$konečná posloupnost ${ displaystyle N ^ {2}}$ disjunktní konečné množiny tak, že každá množina ${ displaystyle M_ {i, j}}$ představuje možné zprávy, které lze odeslat z procesu ${ displaystyle i}$ zpracovat ${ displaystyle j}$. Li ${ displaystyle i = j}$, pak ${ displaystyle M_ {i, j}}$ je prázdný.
• ${ displaystyle ({ mathtt {succ}}) _ {i = 1} ^ {N}: S_ {i} times bigcup _ {j = 1} ^ {N} left (M_ {j, i} ^ {[+]} cup M_ {i, j} ^ {[-]} right) mapsto S_ {i}}$ je posloupnost přechodových funkcí. Každá funkce modeluje přechod, který lze provést vydáním nebo přijetím jakékoli zprávy. S ohledem na proces ${ displaystyle i}$, symbol ${ displaystyle [+]}$ se používá k zaznamenání zprávy, kterou lze přijmout, a ${ displaystyle [-]}$ zprávu, kterou lze odeslat.

Globální stát

A globální stav je pár ${ displaystyle langle S, C rangle}$ kde

• ${ displaystyle S = (s_ {1}, ..., s_ {N})}$ je uspořádaná sbírka států tak, že každý ${ displaystyle s_ {i}}$ představuje stav ${ displaystyle i}$-tý proces.
• ${ displaystyle C}$ je ${ displaystyle N krát N}$ matice tak, že každý ${ displaystyle c_ {i, j} v C}$ je subsekvence ${ displaystyle M_ {i, j}}$.

The počáteční globální stav je pár ${ displaystyle langle O, mathrm {E} rangle}$ kde

• ${ displaystyle O = (o_ {1}, ..., o_ {N})}$
• ${ displaystyle mathrm {E}}$ je definován jako ${ displaystyle N krát N}$ matice taková, že pro všechny ${ displaystyle i, j in {1, ..., N }}$, ${ displaystyle E_ {i, j}}$ rovná se prázdné slovo, ${ displaystyle epsilon}$.

Krok

Existují dva druhy kroků, kroky, ve kterých jsou zprávy přijímány, a kroky, ve kterých jsou zprávy odesílány.

Krok, ve kterém ${ displaystyle j}$ proces obdrží zprávu dříve zaslanou ${ displaystyle i}$-tý proces je dvojice formuláře${ displaystyle left langle (s_ {1}, dots, s_ {j}, dots, s_ {n}), left ({ begin {array} {lll} c_ {1,1} & tečky & c_ {1, n} tečky & tečky & tečky tečky & m_ {i, j} c_ {i, j} & dots tečky & tečky & tečky c_ { n, 1} & dots & c_ {n, n} end {array}} right) right rangle vdash left langle (s_ {1}, dots, s '_ {j}, dots , s_ {n}), left ({ begin {array} {lll} c_ {1,1} & dots & c_ {1, n} dots & dots & dots dots & c_ { i, j} & dots dots & dots & dots c_ {n, 1} & dots & c_ {n, n} end {array}} right) right rangle}$ když ${ displaystyle { mathtt {succ}} _ {i} (s_ {j}, + m_ {i, j}) = s '_ {j}}$, s ${ displaystyle m '_ {i, j} v M_ {i, j}}$. Podobně pár, ve kterém je zpráva odesílána ${ displaystyle i}$-tý proces do ${ displaystyle j}$-tý je pár formuláře ${ displaystyle left langle (s_ {1}, dots, s_ {i}, dots, s_ {n}), left ({ begin {array} {lll} c_ {1,1} & tečky & c_ {1, n} tečky & tečky & tečky tečky & c_ {i, j} & tečky tečky & tečky & tečky c_ {n, 1} & tečky & c_ {n, n} end {array}} right) right rangle vdash left langle (s_ {1}, dots, s '_ {i}, dots, s_ {n}) , left ({ begin {array} {lll} c_ {1,1} & dots & c_ {1, n} dots & dots & dots dots & m_ {i, j} c_ { i, j} & dots dots & dots & dots c_ {n, 1} & dots & c_ {n, n} end {array}} right) right rangle}$ když ${ displaystyle { mathtt {succ}} _ {i} (s_ {i}, - m_ {i, j}) = s '_ {i}}$

Běh

A běh je posloupnost globálních stavů taková, že krok spojuje stav s dalším a takový, že první stav je počáteční.

Říká se, že globální stát ${ displaystyle langle S, C rangle}$ je dosažitelný pokud existuje běh procházející tímto stavem.

Problémy

Zavedením samotného konceptu se prokázalo, že když dva stroje s konečným stavem komunikují pouze s jedním typem zpráv, lze rozhodnout a identifikovat omezenost, zablokování a nespecifikovaný stav příjmu, i když tomu tak není, když stroje komunikují se dvěma nebo více typů zpráv. Později se dále prokázalo, že když pouze jeden stroj s konečným stavem komunikuje s jediným typem zprávy, zatímco komunikace jeho partnera je neomezená, můžeme stále rozhodovat a identifikovat omezenost, zablokování a nespecifikovaný stav příjmu.^[2]

Dále bylo prokázáno, že když je vztah priority zpráv prázdný, o omezenosti, zablokování a nespecifikovaném stavu příjmu lze rozhodnout i za podmínky, že v komunikaci mezi stroji s konečným stavem existují dva nebo více typů zpráv.^[4]

Omezenost, zablokování a nespecifikovaný stav příjmu jsou rozhodnutelné v polynomiálním čase (což znamená, že konkrétní problém lze vyřešit v přijatelném, ne nekonečném čase), protože rozhodovací problémy, které se jich týkají, jsou nedeterministické logické prostory úplné.^[2]

Rozšíření

Některá zvažovaná rozšíření jsou:

• mít notifikaci, že některé státy nemusí obdržet žádnou zprávu,
• zprávy jsou přijímány v různých objednávkách, například FILO,
• některé zprávy se mohou ztratit,

Systém kanálů

A kanálový systém je v podstatě verze komunikujícího stroje s konečným stavem, ve kterém není stroj rozdělen na odlišný proces. Existuje tedy jediný stav stavu a neexistuje žádné omezení týkající se toho, který systém může číst / zapisovat na libovolném kanálu.

Formálně daný protokol ${ displaystyle langle (S_ {i}) _ {i = 1} ^ {n}, (o_ {i}) _ {i = 1} ^ {n}, (M_ {i, j}) _ {i , j = 1} ^ {n}, ({ mathtt {succ}}) _ {i} rangle}$, přidružený systém kanálů je ${ displaystyle langle prod (S_ {i}) _ {i = 1} ^ {n}, (o_ {i}) _ {i = 1} ^ {n}, bigcup _ {i, j = 1 } ^ {n} (M_ {i, j}), Delta rangle}$, kde ${ displaystyle Delta}$ je sada ${ displaystyle ((s_ {1}, tečky, s_ {j}, tečky, s_ {n}) ,? m_ {i, j}, (s_ {1}, tečky, { mathtt {succ} } _ {j} (s_ {j}, + m_ {i, j}), dots, s_ {n})}$ a ze dne ${ displaystyle ((s_ {1}, tečky, s_ {i}, tečky, s_ {n}) ,! m_ {i, j}, (s_ {1}, tečky, { mathtt {succ} } _ {i} (s_ {i}, - m_ {i, j}), dots, s_ {n})}$.

Reference