Communicating finite-state machine とは

コンピュータサイエンスでは、通信有限状態マシンは、あるアルファベットのチャンネルに「受信」および「送信」オペレーションが付いた有限状態マシンです。それらはBrandとZafiropuloによって導入され、ペトリネットのような並行プロセスのモデルとして使用できます。通信有限状態マシンは、有界性、デッドロック、および不特定の受信を含む主要なプロトコル設計エラーを検出することを可能にするので、通信プロトコルをモデル化するために頻繁に使用される。
有限状態機械を通信することの利点は、それらがそのような特性を検出するだけのレベルを超えて、通信プロトコルにおける多くの特性を決定することを可能にすることである。この利点は、人間の援助または一般性の制限の必要性を排除する。
2つの有限状態機械が1つのタイプのメッセージのみと通信するときに、有界性、デッドロック、および不特定の受信状態を決定し識別することができるという概念自体の導入によって証明されているまたはそれ以上の種類のメッセージ。後で、1つの有限状態マシンだけが単一のタイプのメッセージと通信している間に、そのパートナーの通信が制約されていない場合でも、有界性、デッドロックおよび不特定の受信状態を決定し特定することができることがさらに証明されている。
さらに、有限状態機械間の通信に2種類以上のメッセージが存在する状況においても、メッセージ優先度関係が空の場合に有界性、デッドロック、不特定受信状態を判定できることが証明されている。
有界性、デッドロック、および不特定の受信状態はすべて多項式時間で決定可能である(特定の問題は無限大の時間ではなく、扱いやすい形で解決できることを意味する)。
有限状態機械を伝えることは、伝播遅延が無視できない(一度に複数のメッセージが通過するようになる)状況、プロトコル当事者と通信媒体を別々のエンティティとして記述するのが自然な状況。