Communicating finite-state machine

For an arbitrary positive integer ${\displaystyle N}$, a protocol [1]^: 3 with ${\displaystyle N}$ process(es) is a quadruple ${\displaystyle \{(S_{i})_{i=1}^{N},\ (o_{i})_{i=1}^{N},\ (M_{i,j})_{i,j=1}^{N},\ ({\mathtt {succ}})_{i=1}^{N}\}}$ with:

• ${\displaystyle (S_{i})_{i=1}^{N}}$, a sequence of ${\displaystyle N}$ disjoint finite sets. Each set is used to represent a process, and each element of ${\displaystyle S_{i}}$ represents a possible state of the ${\displaystyle i}$-th process.
• ${\displaystyle (o_{i})_{i=1}^{N}}$ (with ${\displaystyle o_{i}\in S_{i}}$), a sequence representing the initial state of each process.
• ${\displaystyle (M_{i,j})_{i,j=1}^{N}}$, a finite sequence of ${\displaystyle N^{2}}$ disjoint finite sets such that each set ${\displaystyle M_{i,j}}$ represents the possible messages which may be sent from process ${\displaystyle i}$ to process ${\displaystyle j}$. If ${\displaystyle i=j}$, then ${\displaystyle M_{i,j}}$ is empty.
• ${\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}}$ is a sequence of transition functions. Each function modelizes the transition which can be taken by emitting or receiving any message. With respect to process ${\displaystyle i}$, the symbol ${\displaystyle [+]}$ is used to note a message that can be received and ${\displaystyle [-]}$ a message that can be sent.

A global state is a pair ${\displaystyle \langle S,C\rangle }$ where

• ${\displaystyle S=(s_{1},...,s_{N})}$ is an ordered collection of states such that each ${\displaystyle s_{i}}$ represents a state of the ${\displaystyle i}$-th process.
• ${\displaystyle C}$ is an ${\displaystyle N\times N}$ matrix such that each ${\displaystyle c_{i,j}\in C}$ is a subsequence of ${\displaystyle M_{i,j}}$.

The initial global state is a pair ${\displaystyle \langle O,\mathrm {E} \rangle }$ where

• ${\displaystyle O=(o_{1},...,o_{N})}$
• ${\displaystyle \mathrm {E} }$ is defined to be an ${\displaystyle N\times N}$ matrix such that for all ${\displaystyle i,j\in \{1,...,N\}}$, ${\displaystyle E_{i,j}}$ equals the empty word, ${\displaystyle \epsilon }$.

There are two kinds of steps, steps in which message are received and steps in which messages are sent.

A step in which the ${\displaystyle j}$ process receive a message previously sent by the ${\displaystyle i}$-th process is a pair of the form ${\displaystyle \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 &m_{i,j}c_{i,j}&\dots \\\dots &\dots &\dots \\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 }$ when ${\displaystyle {\mathtt {succ}}_{i}(s_{j},+m_{i,j})=s'_{j}}$, with ${\displaystyle m'_{i,j}\in M_{i,j}}$. Similarly, a pair in which a message is sent by the ${\displaystyle i}$-th process to the ${\displaystyle j}$-th one is a pair of the form ${\displaystyle \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 &c_{i,j}&\dots \\\dots &\dots &\dots \\c_{n,1}&\dots &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 }$ when ${\displaystyle {\mathtt {succ}}_{i}(s_{i},-m_{i,j})=s'_{i}}$

A run is a sequence of global states such that a step relate a state to the next one, and such that the first state is initial.

It is said that a global state ${\displaystyle \langle S,C\rangle }$ is reachable if there exists a run passing through this state.

It has been proved with the introduction of the concept itself that when two finite state machines communicate with only one type of messages, boundedness, deadlocks, and unspecified reception state can be decided and identified while such is not the case when the machines communicate with two or more types of messages. Later, it has been further proved that when only one finite state machine communicates with single type of message while the communication of its partner is unconstrained, we can still decide and identify boundedness, deadlocks, and unspecified reception state.[2]

It has been further proved that when the message priority relation is empty, boundedness, deadlocks and unspecified reception state can be decided even under the condition in which there are two or more types of messages in the communication between finite state machines.[4]

Boundedness, deadlocks, and unspecified reception state are all decidable in polynomial time (which means that a particular problem can be solved in tractable, not infinite, amount of time) since the decision problems regarding them are nondeterministic logspace complete.[2]

A channel system is essentially a version of communicating finite-state machine in which the machine is not divided into distinct process. Thus, there is a single state of state, and there is no restriction relating which system can read/write on any channel.

Formally, given a protocol ${\displaystyle \langle (S_{i})_{i=1}^{n},(o_{i})_{i=1}^{n},(M_{i,j})_{i,j=1}^{n},({\mathtt {succ}})_{i}\rangle }$, its associated channel system is ${\displaystyle \langle \prod (S_{i})_{i=1}^{n},(o_{i})_{i=1}^{n},\bigcup _{i,j=1}^{n}(M_{i,j}),\Delta \rangle }$, where ${\displaystyle \Delta }$ is the set of ${\displaystyle ((s_{1},\dots ,s_{j},\dots ,s_{n}),?m_{i,j},(s_{1},\dots ,{\mathtt {succ}}_{j}(s_{j},+m_{i,j}),\dots ,s_{n})}$ and of ${\displaystyle ((s_{1},\dots ,s_{i},\dots ,s_{n}),!m_{i,j},(s_{1},\dots ,{\mathtt {succ}}_{i}(s_{i},-m_{i,j}),\dots ,s_{n})}$.