Loading article…
並行計算における不確定性とは、並行計算における不確定性の影響に関するものです。計算は、ネットワーク化とマルチコアコンピュータアーキテクチャの出現による並行性の飛躍的な増加により、不確定性がますます重要になっている分野です。これらのコンピュータシステムは、不確定性を生み出すアービタを使用します。
パトリック・ヘイズ[1973]は、「計算と演繹のプロセスの間に通常なされる明確な区別は誤解を招く」と主張した。ロバート・コワルスキーは、計算は演繹に包含されるというテーゼを展開し、1988年のプロローグの初期の歴史に関する論文で、ヘイズに帰属させた「計算は制御された演繹である」という言葉を賛同して引用した。コワルスキーとヘイズとは対照的に、カール・ヒューイットは、論理演繹はオープンシステムで並行計算を実行することができないと主張した。
Hewitt [1985] や Agha [1991] などの論文では、並行処理の数学的モデルでは特定の並行計算が次のように決定されないと主張している。アクターモデルでは、複数のメッセージが同時に送信されるアクターの到着順序で次にどのメッセージが来るかを決定するために、仲裁（多くの場合、概念的な仲裁者の形式）が用いられる。これにより、到着順序に不確定性が生じる。到着順序は不確定であるため、数学的論理だけでは事前の情報から推論することはできない。したがって、数学的論理ではオープンシステムにおける並行計算を実装することはできない。
著者らは、数学的論理学は一般的な並行処理を実装することはできないが、逐次計算やラムダ計算を含むいくつかの種類の並列計算など、並行計算の特殊なケースを実装できると主張している。
ヒューイットによれば、アクターシステムに関して具体的に言えば、通常、アクターへのメッセージの到着順序がどのように決定されるかの詳細を観察することはできません。そうしようとすると結果に影響を及ぼし、不確定性を他の場所に押しやってしまう可能性さえあります。例えば、電子回路やアービターにおけるメタステーブル状態を参照してください。アクター計算のアービトレーションプロセスの内部を観察する代わりに、結果を待ちます。アービターにおける不確定性は、アクターにおける不確定性を生み出します。結果を待つ理由は、不確定性のために他に選択肢がないからです。
数学的論理の限界に関する公表された主張の根拠を明確にしておくことが重要です。それは、アクターを一般的に数学的論理で実装できないというだけではありませんでした。公表された主張は、アクターモデルの物理的基盤の不確定性のために、いかなる種類の演繹的数学的論理もその限界を回避できないというものでした。これは後に、研究者たちが（論理プログラミングにいくらか基づいている） Prologをメッセージパッシングを用いた並行計算に拡張しようとした際に重要になりました（下記のセクションを参照）。
アクターの数学理論はこれについて何と言っているのでしょうか？閉鎖系とは、外部と通信しないシステムと定義されます。アクターモデル理論は、表現定理[Hewitt 2007]を用いて、閉鎖アクターシステムのすべての可能な計算を次のように特徴付ける手段を提供します。
- 閉じたシステムSによって表される数学的表記は、 ⊥ Sと呼ばれる初期挙動から、挙動近似関数進行Sを使用して、 Sの表記 (意味) を次のように構築することによって、より良い近似を構築することによって得られます。
このようにして、 Sの挙動は、その起こりうるすべての挙動（無制限の非決定性を含むものも含む）に関して数学的に特徴づけることができる。
つまり、数学的論理学は、閉じたアクターシステムのあらゆる可能な計算を（実装するのではなく）特徴づけることができる。
オープンアクターシステムSとは、外部アクターのアドレスを計算の途中でSに渡すことができ、 Sがこれらの外部アクターと通信できるシステムのことです。これらの外部アクターは、Sから提供されたアドレスを使用して、S内部のアクターと通信できます。到着順序を推論できないという制約があるため、外部から送信されるメッセージが何であるかを知っていても、Sの応答を推論することはできません。並行システムの他のモデル（例えば、プロセス計算）を使用してオープンシステムを実装する場合、これらのシステムも到着時間の順序に依存する動作を持つ可能性があり、論理推論によって実装することはできません。
キース・クラーク、エルヴェ・ガレール、スティーブ・グレゴリー、ヴィジャイ・サラスワット、ウディ・シャピロ、上田和則らは、共有変数とメッセージ用のデータ構造ストリームの統合を利用した、 Prologに似た並行メッセージパッシングシステムのファミリーを開発した。この種のシステムは、日本の第5世代プロジェクト（ICOT）の基盤として使用された。
Carl HewittとGul Agha[1991]は、これらのPrologのような並行システムは演繹的でも論理的でもないと主張した。アクターモデルと同様に、Prologのような並行システムはメッセージパッシングに基づいており、結果として同じ不確定性に陥る。
ヒューイットは、PrologとPrologに類似した並行システムから基本的な教訓が得られると主張した。それは、並行計算の普遍的なモデルは、基本的な通信メカニズムに必須のオーバーヘッドが存在することによって制限されるというものだ。これは、データ構造ストリームからのメッセージの統合と抽出を用いたパターン指向呼び出しを基本プリミティブとして含めることに反対する論拠となる。しかし、シャピロによるPrologに類似した並行プログラミング言語の調査と比較すれば、含めるべき論拠が見つかるだろう。
アービトレーションは、並行計算のアクターモデルにおける不確定性の基礎となるものです（ 「アクターモデルの歴史」および「アクターモデル理論」を参照）。また、プロセス計算などの他の並行システムモデルにおいても重要な役割を果たすことがあります。
