並行性モデルとプロセス計算

並行性モデルとプロセス計算は、独立したプロセスがどのように実行、通信、同期するかを形式的に記述します。

Definition

プロセス計算とは、並行システムを通信プロセスとして記述するための形式的な代数であり、並列合成、通信、選択のための演算子と、2つのプロセスが同じ振る舞いをする時期を決定する等価性を備えています。

Scope

このトピックでは、並行計算の代数モデルについて扱います。具体的には、HoareのCSPとMilnerのCCS、通信トポロジーが変化するモバイルプロセス向けのπ-計算、および非同期メッセージパッシングのアクターモデルです。また、通信と同期のプリミティブ、双模倣性などの振る舞い等価性、共有メモリとメッセージパッシングの並行性の対比についても論じます。

Core questions

• 並行通信プロセスはどのように代数的に記述できますか？
• 2つの並行プロセスはいつ振る舞い的に等価になりますか？
• メッセージパッシングは共有メモリ並行性とどのように比較されますか？
• π-計算のように、動的な通信構造はどのようにモデル化されますか？

Key theories

Communicating Sequential Processes (CSP)

HoareのCSPは、共有通信イベントで同期するプロセスを通じて並行性をモデル化し、メッセージパッシング言語の基礎とプロセスリファインメントの理論を提供します。

CCSと双模倣性

MilnerのCommunicating Systemsの計算は、プロセスが交換可能である時期について推論するための、振る舞い等価性である双模倣性の正確な概念を持つプロセスの代数を提供します。

π-計算

Milner、Parrow、およびWalkerは、プロセス計算を移動性に拡張し、通信チャネル自体をメッセージとして渡すことを可能にすることで、接続構造が動的に進化するようにしました。

Clinical relevance

プロセス計算とアクターモデルは、メッセージパッシングに基づいて構築された並行および分散言語とフレームワークの設計を支え、プロトコルを特定し検証するための形式的なツールを提供します。双模倣性とリファインメントは、正しい並行動作のための正確な基準を与えます。

History

並行性理論は、HoareのCSPとMilnerのCCSによって1970年代後半に成熟しましたが、Hewittのアクターモデル（1973年）は非同期メッセージパッシングの代替案を提供しました。1992年のπ-計算はプロセスの移動性を捉えました。これらの計算は、メッセージパッシング言語と並行性ライブラリに影響を与え、プロトコル検証の基礎であり続けています。

Debates

共有メモリ対メッセージパッシング

基本的な設計上の問題は、並行性を同期を伴う共有可変状態を中心に組織化すべきか、それともメッセージを交換する分離されたプロセスを中心に組織化すべきかであり、プロセス計算とアクターモデルは後者を支持しています。

Key figures

• C. A. R. Hoare
• Robin Milner
• Carl Hewitt
• Joachim Parrow
• David Walker

Seminal works

• hoare1978
• milner1989
• milner1992
• hewitt1973

Frequently asked questions

双模倣性とは何ですか？

双模倣性とは、各プロセスが他方の観測可能なステップを無期限に一致させることができる場合に成立するプロセス間の等価性であり、2つの並行プロセスが同じ振る舞いを示すという考えを形式化するものです。

π-計算は以前の計算に何を追加しましたか？

π-計算は、通信チャネルをメッセージとして送信できるようにすることで移動性をモデル化するため、誰が誰と話せるかのトポロジーが実行中に変化し、動的で再構成可能なシステムを捉えることができます。