アクターモデル

アクターモデルとは

アクターモデルは、1973年にカール・ヒューイットらによって発表された並行計算の数学的モデルです。このモデルでは、並行デジタル計算の基本的な要素として「アクター」という概念を導入しています。アクターモデルは、並行性の理論的な理解のためのフレームワークとしてだけでなく、並行システムを実際に実装する際の理論的な基盤としても活用されてきました。

歴史

アクターモデルは、従来の計算モデルとは異なり、物理法則に発想の原点を持っています。また、LISP、Simula、ケーパビリティシステム、パケット通信、初期のSmalltalkなどからも影響を受けています。アクターモデルは、当時予測されていた「数百から数千のマイクロプロセッサで構成され、それぞれがローカルメモリを持ち、高性能な通信ネットワークで接続された並列コンピュータ」の登場を見据えて開発されました。その後、Webサービスやメニーコアアーキテクチャを活用した超並列性にも適用範囲を広げています。

ヒューイットの1973年の論文発表後、アイリーン・グライフがアクターモデルの操作的意味論を開発しました。さらに2年後、ヘンリー・ベイカーとヒューイットはアクターシステムの公理的な法則群を発表しました。1981年には、ウィリアム・クリンガーが Power Domains に基づいたアクターモデルの表示的意味論を発表。1985年、ガル・アガがクリンガーの意味論を基に、遷移ベースの意味論モデルを構築し、アクターモデルの理論が完成しました。

ソフトウェアとしての実装は、MITのメッセージパッシングセマンティクスグループで行われました。また、カリフォルニア工科大学のチャック・セイツとMITのビル・ダリーが率いるチームは、アクターモデルに基づくメッセージパッシングを利用したコンピュータアーキテクチャを構築しました。日本においては、米澤明憲らの研究が広く知られています。

基本概念

アクターモデルの基本となる哲学は「すべてのものはアクターである」という考え方です。これはオブジェクト指向プログラミングにおける「すべてのものはオブジェクトである」という考え方に似ていますが、オブジェクト指向ソフトウェアが基本的に逐次実行なのに対し、アクターモデルは本質的に並行性を持つ点が大きく異なります。

アクターは、並行的に受信するメッセージに応じて以下のような振る舞いをする計算実体です。

他のアクターに有限個のメッセージを送信する。
有限個の新しいアクターを生成する。
次に受信するメッセージに対する動作を指定する。

これらの振る舞いは逐次的に実行されるのではなく、並行的に実行されます。アクター間の通信は非同期に行われるため、メッセージの送信側はメッセージが受信されるのを待つことなく、次の計算に進むことができます。メッセージを送信する相手のアクターは、アドレス（アクターの「メールアドレス」とも呼ばれる）によって指定されます。アクターが他のアクターのアドレスを知る方法は以下の通りです。

受信したメッセージにアドレスが含まれている。
そのアクターが既に対象のアドレスを知っている。
生成したアクターである。

アクターモデルは、アクター自体およびアクター間の計算における本質的な並行性を特徴としており、メッセージ内にアクターのアドレスを含め、相互のやり取りは到着順が保証されない非同期メッセージパッシングのみで行われます。

形式体系

アクターモデルを理解するための形式体系は、長年にわたって開発されてきました。主なものとしては、以下のようなものがあります。

アクターシステムの法則
遷移意味論

また、アクターモデルのメッセージパッシング機能を完全には形式化していないものの、関連する形式体系として以下のようなものがあります。

いくつかのアクター代数系

応用

アクターモデルは、様々な並行システムのモデリングや理解のためのフレームワークとして利用できます。例えば、TTCN（Testing and Test Control Notation）は、アクターモデルに一定程度基づいており、テスト部品をアクターとして扱うことができます。各テスト部品は他のテスト部品やテストシステムとメッセージを送受信し、通信相手をアドレスで識別します。各テスト部品は並行的に動作し、他のテスト部品を動的に生成することも可能です。

アクターモデル以前

アクターモデルは、以下の計算モデルを基盤として構築されました。

ラムダ計算：計算可能性を議論する際に用いられる計算モデルです。
Simula：最初のオブジェクト指向言語ですが、真の並行性はありません。コルーチンを使用しています。
Smalltalk：アラン・ケイはヒューイットのPlannerに影響を受けてSmalltalk-71を考案しましたが、Simula、Lisp、Logoの要素とメッセージパッシングのアイデアを組み合わせたSmalltalk-72を開発しました。ヒューイットはSmalltalk-72のデモを見てメッセージパッシング方式に興味を持ちましたが、その複雑さを問題視し、より単純化された並行計算モデルの必要性を感じました。
ペトリネット：アクターモデル以前に広く使用されていた並行計算モデルですが、制御フローはモデル化できるものの、データフローをモデル化できないという弱点がありました。また、ヒューイットは動作の同時性を問題視し、ペトリネットのようなモデルでは現実の並行システムにはそぐわないと考えました。

メッセージパッシング意味論

アクターモデルはメッセージパッシングの意味論でもあります。

無制限の非決定性に関する議論

初期の並行プログラムは割り込みハンドラでした。外部からの情報を受け取るためにコンピュータが割り込まれ、割り込みハンドラが情報を取り込み、逐次的に処理します。この並行プログラムは、バッファを介して同期的に通信する逐次プログラムを並列に並べたものでした。共有メモリを伴う並列性は、並行性制御という問題を生み、相互排他問題を解決するために、セマフォやモニタが開発されました。

初期の計算モデルは、状態によって計算ステップを表現し、ある状態から別の状態への遷移を繰り返す状態遷移的手法が用いられました。この手法は、非決定性を含む有限状態機械などのオートマタ理論に発展しましたが、エドガー・ダイクストラは、逐次命令列の実行に無制限の時間がかかる可能性があるとしても、状態定義が適切であれば有限の状態数で停止するとしました。ヒューイットは、ダイクストラのモデルでは提供できないサービスの保証をアクターモデルで提供すると主張しました。

ヒューイットが言う無制限の非決定性は、並行性の特徴であり、共有リソースの衝突の仲裁の結果として、サービスの遅延が無制限に発生することを意味します。アクターモデルでは、ウィル・クリンガーが領域理論を使った数学的モデルで無制限の非決定性を導入しました。アクターモデルには、グローバルな状態という概念はありません。

直接通信と非同期性

アクターモデルでは、メッセージをバッファに蓄える必要はありません。これは、従来の並行計算モデルとは明確に異なる点であり、当初は誤解されがちでした。アクターモデルでのメッセージは、IPパケットのように単に送信され、受信側との同期的なハンドシェイクは不要です。

アドレスを伴うアクター生成は可変なトポロジーを可能にする

アクターモデルでは、メッセージにアドレスが含まれることが自然な発展として起こりました。ヒューイットは、パケット通信に影響を受け、形式が固定されていない通信を使う新たな並行計算モデルを提案しました。メッセージには、空でも、新しいアドレスを含めることもできます。また、メッセージを受け取った側からの応答が必要な場合は、継続またはスタックフレームとも呼ばれる「再開」用のアクターのアドレスをメッセージに含めて送信します。これにより、アクター間の関係は可変なトポロジーを形成することが可能になります。

本来的な並行性

逐次的なプロセスの合成に基づく従来の手法とは異なり、アクターモデルは並行的なモデルとして開発されました。アクターモデルでの逐次性は、アクターモデル理論で説明されるように並行計算の特殊ケースです。

メッセージ受信の順番は不同

アクターモデルでは、送信された順番にメッセージが受信されるべきだという要求はありません。メッセージの順序付けが必要な場合は、キューの役割をするアクターを導入することで実現できます。アクターXがアクターYにメッセージM1を送信し、その後メッセージM2を送信した場合、M1がM2より先にYに到着するとは限りません。これは、パケット通信システムのように、パケットが送信順に受信されることを保証しないことによって最適化を可能にしていることに対応しています。例えば、アクターはメッセージ処理をパイプライン化することができ、あるメッセージの処理が完了する前に次のメッセージの処理を開始できます。

局所性

アクターモデルの重要な特徴の1つは局所性です。局所性とは、メッセージを処理する際に、アクターがメッセージを送信できる相手はアドレスを知っているものに限られることを意味します。また、複数の場所を同時に変更することがないことも局所性とされます。

合成性

合成性とは、アクターシステム群からより大きなシステムを構成できることを意味します。これはモジュール性の観点から重要であり、ガル・アガらの研究で展開されました。

振る舞い

「振る舞い」を導入することで、アクターのメッセージ処理を数学的な関数として記述できるようになりました。振る舞いは、並行性における共有を数学的にモデル化するための機構を提供します。

数理論理学との関係

アクターモデルの開発と数理論理学の関係は興味深いものです。開発の動機として、Planner言語の開発で生じた制御構造問題を扱い理解すること、および「計算は推論に含まれる」という主張に対するモデルの能力を理解するという目的がありました。しかし、ヒューイットとアガは、計算ステップが前のステップからの推論ではないという意味で、アクターモデルは演繹的ではないと指摘しました。

マイグレーション

マイグレーションとは、アクターが位置を変更できることを意味します。例えば、米澤明憲は学位論文で郵便局をアクターモデルでモデル化しました。このモデルでは、客をアクターとし、郵便局内で位置を変えながら処理をしていく様子を表現しました。マイグレートするアクターは、位置アクターを導入することでモデル化できますが、このモデル化については議論が続いています。

アクターモデルの重要性

ハードウェアは、マルチコアマイクロプロセッサのような局所的な並行性や、コンピュータネットワークなどの非局所的な並行性を採用し始めており、その並行性は指数関数的に増大しています。カール・ヒューイットによれば、アクターモデルは、コンピュータ（および通信）アーキテクチャ、並行プログラミング言語、Webサービスに関する以下の問題に直面しています。

スケーラビリティ：局所的および非局所的な並行性をスケールアップする。
透過性：局所的な並行性と非局所的な並行性の間を埋める。この点については議論が続いており、並行プログラミング言語とWebサービスを明確に分けて扱うべきとする研究者もいますが、技術の進歩による並行性の移行の際に透過性の問題として現れてきます。
非一貫性：巨大な情報システムは、一貫性を失いがちです。これは巨大システムの仕様書にも当てはまります。

アクターモデルの考え方は、マルチエージェントシステムにも見られます。エージェントシステムは、アクターモデルに何らかの制限を加えたものであり、自発的で自律的であることが求められる点が異なります。

関連項目

データフロー
アクターモデル理論、アクターモデルの実装
マルチエージェントシステム
ニューラルネットワーク
Scientific Community Metaphor
Erlang

もう一度検索