アクターモデルとプロセス計算

コンピュータサイエンスにおいて、アクターモデルとプロセス計算は、並行デジタル計算をモデル化するための密接に関連した2つのアプローチである。アクターモデルとプロセス計算の歴史を参照のこと。

両者のアプローチには多くの類似点がある一方で、いくつかの相違点もある（哲学的なものもあれば、技術的なものもある）。

アクターモデルは1つだけですが（設計、分析、検証、モデリングなどのための形式体系は多数存在します）、プロセス計算は多数存在し、さまざまな詳細レベルで多様な種類の並行システムについて推論するために開発されています（時間、確率的遷移、セキュリティ分析などの応用分野に特有の構成要素を組み込んだ計算も含まれます）。
アクターモデルは物理法則に触発されて生まれ、その基本公理、すなわち物理法則に依存している（アクターモデル理論を参照）。プロセス計算は元々代数学に触発されたものである（ミルナー 1993 ）。
プロセス計算におけるプロセスは匿名であり、名前付きチャネル（同期または非同期）を介してメッセージを送信するか、アンビエントを介してメッセージを送信することによって通信します（アンビエントはチャネルのような通信をモデル化するためにも使用できます（Cardelli and Gordon 1998 ））。一方、アクターモデルのアクターはアイデンティティを持ち、他のアクターのメーリングアドレスにメッセージを送信することによって通信します（このスタイルの通信は、チャネルのような通信をモデル化するためにも使用できます。下記を参照）。

アクターモデルとプロセス計算に関する出版物には、相互参照、謝辞、相互引用がかなり多く含まれています（アクターモデルとプロセス計算の歴史を参照）。

チャンネルの仕組み

チャネルを用いた間接通信（例：ジル・カーンとデビッド・マックイーン[1977]）は、並列計算および並行計算における通信において、意味論とパフォーマンスの両方に影響を与える重要な課題となっている。一部のプロセス計算は、直接通信ではなくチャネルを使用する点で、アクターモデルとは異なる。

同期チャネル

同期チャネルには、チャネルにメッセージを送信する送信者は、受信者がチャネルからメッセージを取り出すまで、次の処理に進むことができないという特性があります。

シンプルな同期チャネル

put同期チャネルは、送受信を行うアクターによってモデル化できますget。以下は、単純な同期チャネルにおけるアクターの動作です。

各put通信にはメッセージと、メッセージ受信時に確認応答が送信される宛先アドレスが含まれています。
各get 通信には、受信したメッセージが送信される宛先アドレスが存在する。
通信を受信するとget、アクターはFIFOput順で通信を選択し、指定されたアドレスにメッセージと確認応答を送信する。

プロセス計算における同期チャネル

しかし、単純な同期チャネルでは、通信逐次プロセス(CSP) [Hoare 1978 および 1985]のようなプロセス計算には不十分です。これは、ガード付き選択コマンド (ダイクストラにちなんで) ( CSP では代替putコマンドと呼ばれる) を使用するためです。ガード付き選択コマンドでは、複数のチャネルで複数のオファー (ガードと呼ばれる) を同時にgetメッセージに対して行うことができますが、ガード付き選択コマンドの各実行で選択できるガードは最大で 1 つだけです。選択できるガードは 1 つだけなので、ガード付き選択コマンドは一般的に、一種の2 相コミットプロトコル、またはガードでタイムアウトが許容される場合(Occam 3 [1992] のように) には3 相コミットプロトコルさえも必要とします。

CSPで記述された以下のプログラムを考えてみましょう[Hoare 1978]。

[X :: Z!stop() || Y :: guard: boolean; guard := true; *[guard  →  Z!go(); Z?guard] || Z :: n: 整数; n:= 0; *[X?stop()  →  Y!false; print!n; [] Y?go()  →  n := n+1; Y!true] ]

XClinger [1981] によると、このプログラムはグローバルな非決定性を示している。なぜなら、非決定性は、3 つのプロセス、Y、およびの間の信号のタイミングの不完全な指定から生じるからであるZ。の定義における繰り返しガード付きコマンドには、Z2 つの選択肢がある。

メッセージstopがから受け入れられたX場合、にはY値falseが送信され、にはprint値が送信されます。n
からメッセージgoが受け入れられるとY、nがインクリメントされ、Y値trueが送信されます。

がからのメッセージZを受け入れると、は終了します。を受け入れると、がfalseを送信し、がガードの値として入力されると、は終了します。との両方が終了すると、は入力を提供するアクティブなプロセスがなくなるため、終了します。stopXXstopYYXYZ

上記のプログラムでは、からX、ZからY、ZおよびZからへの同期チャネルがありますY。

委員会調整問題との類推

Knabe [1992]によると、ChandyとMisra [1988]はこれを委員会調整問題に類似したものとして特徴づけた。

大学の教授は様々な委員会に所属しています。教授は時折、所属する委員会の会議に出席することを決め、出席できるまで待機します。会議は全員出席した場合にのみ開始できます。課題は、委員会のメンバー全員が待機している場合、少なくとも1人はいずれかの会議に出席できるようにすることです。

この問題の核心は、2つ以上の委員会が同じ教授を共有している可能性があるという点にある。その教授が都合がつくようになったとしても、彼女は1つの委員会しか担当できず、他の委員会は待機を余儀なくされる。

シンプルな分散プロトコル

このセクションでは、同期プロセス計算におけるチャネルのためのシンプルな分散プロトコルを紹介します。このプロトコルにはいくつかの問題点があり、それらについては後述のセクションで説明します。

ガード付き選択コマンドの動作は以下のとおりです。

このコマンドは、各ガードにメッセージを送信しますprepare。
準備完了という最初の応答を警備員の1人から受け取ると、その警備員にメッセージを送信しprepare to commit、他のすべての警備員にもメッセージを送信しますabort。
- ガードから「実行可能」というメッセージを受け取るとprepared to commit、ガードにcommitメッセージを送信します。ただし、ガードが実行できないという例外をスローした場合prepare to commit、ガード付き選択コマンドはプロセス全体を最初からやり直します。
全ての警備員が「できない」と回答した場合prepare、警備対象のコマンドは何も実行しない。

警備員の行動は以下のとおりです。

メッセージがprepare受信されると、ガードはprepare通信を申し出ている各チャネルにメッセージを送信します。ガードが通信できないブール値を持っている場合、prepareまたはチャネルのいずれかが通信できないと応答した場合、ガードは他のチャネルにメッセージをprepare送信し、通信できないと応答します。 abortprepare
- メッセージがprepare to commit受信されると、ガードはprepare to commit各チャネルにメッセージを送信します。いずれかのチャネルが「できません」と応答した場合prepare to commit、ガードは他のチャネルにメッセージを送信しabort、その後「できません」という例外をスローしますprepare to commit。
- メッセージがcommit受信されると、ガードはcommit各チャネルにメッセージを送信します。
- メッセージがabort受信されると、ガードはabort各チャネルにメッセージを送信します。

チャネルの動作は以下のとおりです。

通信を受信したら、通信が保留中prepare to putの場合は準備完了と応答し、通信が受信されている場合は、できないという例外をスローします。prepare to getterminateprepare to put
通信を受信したら、通信が保留中prepare to getの場合は準備完了と応答し、通信が受信されている場合は、できないという例外をスローします。 prepare to putterminateprepare to get
- 通信を受信したら、通信が保留中prepare to commit to putの場合は準備完了と応答し、通信が受信されている場合は、できないという例外をスローします。prepare to commit to getterminateprepare to commit to put
- 通信を受信したら、通信が保留中prepare to commit to getの場合は準備完了と応答し、通信が受信されている場合は、できないという例外をスローします。 prepare to commit to putterminateprepare to commit to get
  - 通信を受信した場合commit put、以下のいずれかが受信されたかどうかに応じて、次の処理が行われます。
    - commit get通信を受信したら、まだ実行していない場合は、準備を実行し、クリーンアップしますput。get
    - 連絡を受けたらabort get、準備を中止してください。
  - 通信を受信した場合commit get、以下のいずれかが受信されたかどうかに応じて、次の処理が行われます。
    - commit put通信を受信したら、まだ実行していない場合は、準備を実行し、クリーンアップしますget。put
    - 連絡を受けたらabort put、準備を中止してください。
  - 連絡を受けたらabort put、準備を中止してください。
  - 連絡を受けたらabort get、準備を中止してください。

複数のチャネルから取得する際の飢餓状態

ここでも、CSPで記述されたプログラム（上記「プロセス計算における同期チャネル」で説明済み）を考えてみましょう。

[X :: Z!stop() || Y :: guard: boolean; guard := true; *[guard  →  Z!go(); Z?guard] || Z :: n: 整数; n:= 0; *[X?stop()  →  Y!false; print!n; [] Y?go()  →  n := n+1; Y!true] ]

Knabe [1992] で指摘されているように、上記のプロトコル (単純な分散プロトコル)の問題点は、プロセスが (飢餓と呼ばれる現象)からのメッセージZを受け入れない可能性があり、その結果、上記のプログラムが何も出力しない可能性があることです。stopX

対照的に、アクターX、Y、Z、およびprintから構成される単純なアクターシステムを考えてみましょう。

アクターXは、以下の動作で作成されます。
- メッセージ"start"が受信された場合は、Zにメッセージを送信する。"stop"
アクターYは、以下の動作で作成されます。
- メッセージ"start"が受信された場合は、Zにメッセージを送信する。"go"
- メッセージがtrueと受信された場合、Zにメッセージを送信する"go"
- メッセージがfalseの場合は、何もしない。
アクターZnは、初期カウントが0である以下の動作で作成されます。
- メッセージ"start"が受信された場合は、何もする必要はありません。
- メッセージ"stop"が受信された場合は、Yにメッセージfalseを送信し、メッセージをカウントして出力nします。
- メッセージ"go"が受信された場合は、Yにメッセージtrueを送信し、受信した次のメッセージをカウントとして処理しnますn+1。

アクター意味論の法則により、上記のアクターシステムは、アクターX、Y、Zそれぞれに"start"メッセージが送信され、結果として無限に大きくなる可能性のある数値が出力されると、必ず停止します。

CSPプログラムとアクターシステムの違いは、アクターZが複数のチャネルからガード付き選択コマンドを使用してメッセージを受け取るのではなく、到着順にメッセージを処理する点にある。アクターシステムの法則により、stopメッセージの到着は保証される。

複数のチャネルから取得する際のライブロック

CSPで記述された以下のプログラムを考えてみましょう[Hoare 1978]。

[Bidder1 :: b: bid; *[Bids1?b  →  process1!b; [] Bids2?b  →  process1!b;] || 入札者2 :: b: 入札; *[Bids1?b  →  process2!b; [] Bids2?b  →  process2!b;] ]

Knabe [1992] で指摘されているように、上記のプロトコル (単純な分散プロトコル)の問題点は、プロセスがまたはBidder2からの入札を決して受け入れない可能性があること (ライブロックと呼ばれる現象) であり、結果としてには何も送信されない可能性があります。メッセージの受け入れを試みるたびに、またはによって提示された入札がによって奪われるため、は阻止されます。これは、がおよびよりもはるかに高速にアクセスできることが判明したためです。したがって、が入札を受け入れ、処理し、が入札を受け入れることを約束する前に別の入札を受け入れることができます。Bid1Bid2process2Bidder2Bids1Bids2Bidder1Bidder1Bidder2Bids1Bids2Bidder1Bidder2

効率

Knabe [1992] で指摘されているように、上記のプロトコル (単純な分散プロトコル) の問題点は、同期チャネルを介してメッセージを送信するためのハンドシェイクを実行するために送信しなければならない通信の数が多いことです。実際、前のセクション ( Livelock ) で示したように、通信の数は無制限になる可能性があります。

問題点の概要

上記の各節では、プロセス計算に同期チャネルを使用することに関連する以下の3つの問題点について説明しました。

飢餓状態。同期チャネルを使用すると、プロセスがガード付き選択コマンドで複数のチャネルからメッセージを取得しようとしたときに、飢餓状態が発生する可能性があります。
ライブロック。同期チャネルを使用すると、ガード付き選択コマンドで複数のチャネルからメッセージを取得しようとした際に、プロセスがライブロックに陥る可能性があります。
効率性。 同期チャネルを使用すると、ガード付き選択コマンドで複数のチャネルからメッセージを取得するために、多数の通信が必要になる場合があります。

上記すべてにおいて、複数のチャネルからメッセージを取得するためにガード付き選択コマンドを使用することから問題が生じていることは注目に値する。

非同期チャネル

非同期チャネルには、チャネルにメッセージを送信する送信者が、受信者がチャネルからメッセージを取り出すのを待つ必要がないという特性があります。

シンプルな非同期チャネル

put非同期チャネルは、送受信を行うアクターによってモデル化できますget。以下は、単純な非同期チャネルにおけるアクターの動作です。

各put通信にはメッセージと、受信確認が即座に送信される宛先アドレスが含まれています（get通信がメッセージを受信するのを待つことなく）。
各get 通信には、受信したメッセージが送信される宛先アドレスが存在する。

プロセス計算における非同期チャネル

Join-calculusプログラミング言語（1996年発表）は、ローカルおよび分散並行計算を実装しました。非同期チャネルと、プロシージャ呼び出しに使用される一種の同期チャネルを組み込んでいます。AghaのAπアクター計算（AghaとThati 2004 ）は、非同期π計算の型付きバージョンに基づいています。

代数

代数的手法の使用はプロセス計算において先駆的に行われた。その後、アクターシステムに関する代数的推論を提供することを目的としたいくつかの異なるプロセス計算が（Gaspari and Zavattaro 1997 ）、（Gaspari and Zavattaro 1999 ）、（Agha and Thati 2004 ）で開発された。

指示的意味論

ウィル・クリンガーは（アイリーン・グライフ[1975]、ゴードン・プロトキン[1976]、ヘンリー・ベイカー[1978]、マイケル・スミス[1978]、フランセズ、ホア、レーマン、デ・ローバー[1979]の研究に基づいて）、 1981年の博士論文でドメイン理論を用いてアクターモデルの最初の満足のいく数学的表示理論を発表した。彼の意味論は、アクターモデルの無制限の非決定性を、 CSP [ホア 1978]および並行プロセス[ミルンとミルナー 1979]の制限された非決定性と対比させた（表示意味論を参照）。ロスコー[2005]は、ホア[1985]のCommunicating Sequential Processesのその後のバージョンに対して、無制限の非決定性を持つ表示意味論を開発した。さらに最近では、カール・ヒューイット[2006b]が時間図に基づいてアクターの表示的意味論を開発した。

ウーゴ・モンタナリとキャロリン・タルコット[1998]は、アクターとプロセス計算を調和させようとする試みに貢献した。

参考文献

Carl Hewitt、Peter Bishop、Richard Steiger。「人工知能のための普遍的なモジュール型アクター形式」 IJCAI 1973。
ロビン・ミルナー。「プロセス：計算エージェントの数学的モデル」、 1973年論理学コロキウム。
Irene Greif および Carl Hewitt。 「PLANNER-73 のアクター意味論」 ACM プログラミング言語原理シンポジウム会議録。1975 年 1 月。
アイリーン・グライフ。 「通信する並列プロセスのセマンティクス」 MIT EECS 博士論文。1975年8月。
ゴードン・プロトキン。 「パワードメイン構成」 SIAM Journal on Computing、1976年9月。
Carl Hewitt および Henry Baker、「アクターと連続関数」、 IFIP プログラミング概念の形式的記述に関するワーキングカンファレンスの議事録。1977 年 8 月 1 日～5 日。
ジル・カーン、デビッド・マックイーン。「コルーチンと並列プロセスのネットワーク」 IFIP、1977年
米澤亜紀「メッセージパッシング意味論に基づく並列プログラムの仕様記述と検証技術」 MIT EECS 博士論文。1977年12月。
マイケル・スミス。 「電力領域」、 Journal of Computer and System Sciences、1978年。
ジョージ・ミルン、ロビン・ミルナー。 「並行プロセスとその構文」 JACM、1979年4月。
CAR Hoare。 「Communicating Sequential Processes」は、 Wayback Machineに2021年2月1日にアーカイブされました。CACM。1978年8月。
Nissim Francez、CAR Hoare、Daniel Lehmann、Willem de Roever。 「非決定性、並行性、および通信の意味論」 Journal of Computer and System Sciences、1979年12月。
Mathew Hennessy と Robin Milner。「非決定性と並行性の観察について」 LNCS 85。1980 年。
ウィル・クリンガー。 「行為者意味論の基礎」 MIT数学博士論文。1981年6月。
Mathew Hennessy.同期プロセスの用語モデル、エジンバラ大学コンピュータサイエンス学科。CSR-77-81。1981年。
J.A. Bergstra および J.W. Klop。「同期通信のためのプロセス代数」 Information and Control、1984 年。
ルカ・カルデッリ。 「ランデブー通信の実装モデル」 並行性に関するセミナー。コンピュータサイエンス講義ノート197。シュプリンガー・フェルラーク。1985年
Robert van Glabbeek。 「プロセス代数における有界非決定性と近似誘導原理」 STACS 1987 の理論的コンピュータ科学シンポジウム。
K. マニ・チャンディ、ジャヤデヴ・ミスラ著『並列プログラム設計：基礎』アディソン・ウェスリー、1988年。
Robin Milner、Joachim Parrow、David Walker。 「モバイルプロセスの計算」。エジンバラ大学コンピュータサイエンス学科。レポートECS-LFCS-89-85およびECS-LFCS-89-86。1989年6月。それぞれ1990年9月および1990年10月に改訂。
ロビン・ミルナー。 「多項式π計算：チュートリアル」 エジンバラ大学。LFCSレポート ECS-LFCS-91-180。1991年。
本田耕平さんと所マリオさん。 非同期通信のためのオブジェクト計算 ECOOP 91。
José Meseguer。「並行性の統一モデルとしての条件付き書き換え論理」、『並行性と構成性に関する第2回ワークショップ選集』、1992年。
フレデリック・クナーベ。「選択を伴うチャネルベース通信のための分散プロトコル」 PARLE 1992。
ジェフ・バレット著。Occam 3 リファレンスマニュアルINMOS。1992年。
Benjamin Pierce、Didier Rémy、David Turner。 「π計算に基づく型付き高階プログラミング言語」 型理論とそのコンピュータシステムへの応用に関するワークショップ。京都大学。1993年7月。
ミルナー、ロビン（1993年1月）「相互作用の要素：チューリング賞受賞講演」Communications of the ACM、36、CACM：78–89、doi：10.1145/151233.151240。
R. Amadio および S. Prasad。 「場所と障害」 ソフトウェア技術と理論計算機科学の基礎に関する会議。1994 年。
セドリック・フルネとジョルジュ・ゴンティエ。 「反射的化学抽象機械と結合計算」POPL 1996。
セドリック・フルネ、ジョルジュ・ゴンティエ、ジャン＝ジャック・レヴィ、リュック・マランジェ、ディディエ・レミ。モバイルエージェントの微積分 CONCUR 1996。
関口達郎さんと米澤明憲さん。 コードモビリティ FMOODS を使用した微積分 1997。
ガスパリ、マウロ。ジャンルイジのザヴァッタロ (1997 年 5 月)、アクターの代数(技術レポート)、ボローニャ大学
Cardelli, Luca; Gordon, Andrew D. (1998)、「モバイル環境」、ソフトウェア科学と計算構造の基礎、Lecture Notes in Computer Science、第1378巻、140–155ページ、doi : 10.1007/BFb0053547、ISBN 978-3-540-64300-5
ウーゴ・モンタナリ、キャロリン・タルコット。 「アクターとパイエージェントは共存できるか？」 理論計算機科学電子ノート。1998年。
ロビン・ミルナー著『通信とモバイルシステム：π計算』ケンブリッジ大学出版局、1999年。
ガスパリ、マウロ。 Zavattaro、Gianluigi (1999)、「An Algebra of Actors」、Formal Methods for Open Object-Based Distributed Systems、pp. 3–18、doi : 10.1007/978-0-387-35562-7_2、ISBN 978-1-4757-5266-3
ダヴィデ・サンジョルジ、デイヴィッド・ウォーカー著『円周率計算：移動過程の理論』 ケンブリッジ大学出版局、2001年。
P. Thati、R. Ziaei、G. Agha。「局所性と名前一致なしの非同期計算のためのmayテストの理論」『代数的方法論とソフトウェア技術』Springer Verlag、2002年9月、LNCS 2422。
Agha, Gul; Thati, Prasanna (2004)、「アクターの代数理論とその単純なオブジェクトベース言語への応用」、From Object-Orientation to Formal Methods (PDF)、Lecture Notes in Computer Science、vol. 2635、pp. 26–57、doi : 10.1007/978-3-540-39993-3_4、ISBN 978-3-540-21366-62004年4月20日にオリジナル（PDF）からアーカイブされ、 2005年12月15日に取得されました。
JCM Baeten、T. Basten、MA Reniers。『通信プロセスの代数』ケンブリッジ大学出版局、2005年。
He Jifeng、CAR Hoare。「並行性理論の連携」国連大学国際ソフトウェア技術研究所（UNU-IIST）レポートNo.328、2005年7月。
ルカ・アチェト、アンドリュー・D・ゴードン（編）。代数的プロセス計算：最初の25年間とプロセス代数の未来。イタリア、フォルリ、ベルティノーロ、2005年8月1日～5日。
Roscoe, AW (2005)『並行性の理論と実践』 Prentice Hall、ISBN 978-0-13-674409-2
Carl Hewitt (2006b)コミットメントとは何か？物理的、組織的、社会的 COIN@AAMAS. 2006.