(57)【要約】      （修正有）【課題】ボランティアサーバ、複数のボランティア含むコンピュータネットワークにおける、モバイルエージェントベースのピアツーピアグリッド演算の方法を提供する。【解決手段】ボランティアをその特性にしたがって複数のグループに分類する；ジョブを多数のタスクに分け、タスクモバイルエージェントとして実行する；スケジューリングモバイルエージェントをグループに割り当てる；各スケジューリングモバイルエージェントが、タスクモバイルエージェントをそのグループのメンバーに分配する；各ボランティアが、スケジューリングモバイルエージェントと共働してタスクモバイルエージェントを実行する；各タスクモバイルエージェントが、実行結果をスケジューリングモバイルエージェントに戻す；スケジューリングモバイルエージェントが結果を集計し、ボランティアサーバに戻す；ボランティアサーバが最終結果をクライアントに戻す各ステップを含む。【選択図】図１
2008071294.tif 000002
【特許請求の範囲】
【請求項１】
ボランティアサーバ、複数のボランティア、および前記ボランティアサーバにジョブを提出するクライアントを含むコンピュータネットワークにおける、モバイルエージェントベースのピアツーピアグリッド演算の方法であって：
ボランティアの特性を登録し、特性にしたがってそれらを複数のボランティアグループに分類するステップ；
提出されたジョブを多数のタスクに分けるステップであって、各タスクはタスクモバイルエージェントとして実行される、前記ステップ；
特性にしたがって、スケジューリングモバイルエージェントをボランティアグループに割り当てるステップ；
各スケジューリングモバイルエージェントが、タスクモバイルエージェントをそのボランティアグループのメンバーに分配するステップ；
各ボランティアが、スケジューリングモバイルエージェントと共働してタスクモバイルエージェントを実行するステップ；
各タスクモバイルエージェントが、実行結果をスケジューリングモバイルエージェントに戻すステップ；
スケジューリングモバイルエージェントが結果を集計し、集めた結果をボランティアサーバに戻すステップ；および
ボランティアサーバが最終結果をクライアントに戻すステップ
を含む、前記方法。
【請求項２】
ボランティアの特性が、ＣＰＵ、メモリ容量、ストレージ、ネットワーク容量を含む、請求項１に記載の方法。
【請求項３】
ボランティアの特性が、ボランティアが公開実行に参加するときに予定されたサービス時間であるボランティアサービスタイム、およびボランティアが正確に作動し、ボランティアサービスを遂行する確率であるボランティア可能性を含む、請求項１に記載の方法。
【請求項４】
ボランティアの特性が、ボランティアのロケーションをさらに含む、請求項３に記載の方法。
【請求項５】
ボランティアグループが以下により構築される、請求項４に記載の方法：
登録されたボランティアをそのロケーションに応じてホームボランティアまたはリージョンボランティアに分類することであって、ホームボランティアは、インターネットに接続されたものであり、リージョンボランティアは、ＬＡＮまたはイントラネットに接続されたものであること；
ホームボランティアおよびリージョンボランティアを、ボランティアサービスタイムおよびボランティア可能性によってＡ’クラス、Ｂ’クラス、Ｃ’クラス、Ｄ’クラスに分類することであって、クラスＡ’は、ボランティアサービスタイムが長く、かつボランティア可能性が高いボランティアの群であり、クラスＢ’は、ボランティアサービスタイムが短く、かつボランティア可能性が高いボランティアの群であり、クラスＣ’は、ボランティアサービスタイムが長く、かつボランティア可能性が低いボランティアの群であり、クラスＤ’は、ボランティアサービスタイムが短く、かつボランティア可能性が低いボランティアの群とすること。
【請求項６】
ボランティア可能性が、ＭＴＴＶＡＦ／（ＭＴＴＶＡＦ＋ＭＴＴＲ）によって計算され、ＭＴＴＶＡＦは、ボランティア自律性の障害までの平均時間を表し、ＭＴＴＲは、復帰するまでの平均時間を表す、請求項５に記載の方法。
【請求項７】
クラスＡ’とクラスＣ’のボランティアグループを組み合わせて、クラスＡ’Ｃ’のスケジューリンググループを構築し、タスクを前記Ａ’Ｃ’スケジューリンググループに分配させる、請求項５に記載の方法。
【請求項８】
クラスＡ’とクラスＤ’のボランティアグループを組み合わせて、Ａ’Ｄ’スケジューリンググループを構築するとともに、クラスＣ’とクラスＢ’のボランティアグループを組み合わせて、クラスＣ’Ｂ’のスケジューリンググループを構築し、タスクをまずＡ’Ｄ’スケジューリンググループに分配し、次いでＣ’Ｂ’スケジューリンググループに分配する、請求項５に記載の方法。
【請求項９】
Ａ’Ｄ’スケジューリンググループのスケジューリングモバイルエージェントが、下記の１）〜３）を実行する、請求項８に記載の方法：
１）ボランティア可能性に応じて、次にボランティアサービスタイムに応じて、Ａ’ボランティアグループを順位付ける；
２）タスクモバイルエージェントを、アレンジしたＡ’ボランティアグループのメンバーに分配する；
３）タスクモバイルエージェントに障害が発生した場合、障害が生じたタスクをＡ’ボランティアグループ内で選択される新しいボランティアに複製する。
【請求項１０】
Ｃ’Ｂ’スケジューリンググループのスケジューリングモバイルエージェントが、下記の１）〜３）を実行する、請求項８に記載の方法：
１）ボランティア可能性に応じて、次にボランティアサービスタイムに応じて、Ｃ’ボランティアグループおよびＢ’ボランティアグループを順位付ける；
２）タスクモバイルエージェントを、アレンジしたＣ’ボランティアグループのメンバーに分配する；
３）タスクモバイルエージェントに障害が発生した場合、障害が生じたタスクをＢ’ボランティアグループまたはＣ’ボランティアグループ内で選択される新しいボランティアに複製する。
【請求項１１】
タスクを、まずＡ’Ｄ’スケジューリンググループに分配し、次いでＣ’Ｂ’スケジューリンググループに分配する、請求項８に記載の方法。
【請求項１２】
ホームボランティアおよびリージョンボランティアを、Ａ’クラス、Ｂ’クラス、Ｃ’クラス、Ｄ’クラスに分類するステップが、下記のステップを含む、請求項５に記載の方法：
ホームボランティアおよびリージョンボランティアを、ボランティアタイムおよびボランティア可能性によってＡクラス、Ｂクラス、Ｃクラス、Ｄクラスに分類するステップであって、クラスＡは、ボランティアタイムが長く、かつボランティア可能性が高いボランティア群であり、クラスＢは、ボランティアタイムが短く、かつボランティア可能性が高いボランティア群であり、クラスＣは、ボランティアタイムが長く、かつボランティア可能性が低いボランティア群であり、クラスＤは、ボランティアタイムが短く、かつボランティア可能性が低いボランティア群である、前記ステップ；
ボランティアのボランティアサービスタイムが、予定されたタスクの演算時間と同じか、またはそれより長い場合において、ボランティアがクラスＡまたはＢに属する場合には、当該ボランティアをクラスＡ’に分類し、そうでなければ当該ボランティアをクラスＣ’に分類するステップ；および
ボランティアのボランティアサービスタイムが、予定されたタスクの演算時間より短い場合において、ボランティアがクラスＡまたはＢに属する場合には、当該ボランティアをクラスＢ’に分類し、そうでなければ当該ボランティアをクラスＤ’に分類するステップ。
【請求項１３】
クラスＡ’およびクラスＢ’のボランティアグループを組み合わせて、Ａ’Ｂ’スケジューリンググループを構築するとともに、クラスＣ’とクラスＤ’のボランティアグループを組み合わせて、クラスＣ’Ｄ’のスケジューリンググループを構築し、タスクを各スケジューリンググループに分配する、請求項５に記載の方法。
【請求項１４】
スケジューリングモバイルエージェントをボランティアグループに割り当てるステップが：
代理ボランティア候補として、ボランティアをクラスＡ’に指定すること；
前記代理ボランティア候補を、ボランティア可能性、ボランティアサービスタイム、ハードディスク容量およびネットワークバンド幅によって順位付けること；
必要な数の代理ボランティアを、順位付けされた代理ボランティア候補から順番に選択すること；および
各スケジューリングモバイルエージェントを選択された各代理ボランティアに転送すること。
【請求項１５】
各スケジューリングエージェントが、スケジューリンググループリスト、スケジューリング表およびタスク結果を含むスケジューリング情報を記憶する、請求項１４に記載の方法。
【請求項１６】
スケジューリングモバイルエージェントが、アライブメッセージをボランティアサーバに定期的に送るステップ；
アライブメッセージがスケジューリングモバイルエージェントから所定の時間なくなっている場合、ボランティアサーバが、新しい代理ボランティアを選択するステップ；および
ボランティアサーバが、スケジューリングモバイルエージェントおよびスケジューリング情報を前記新しい代理ボランティアに送るステップ
をさらに含む、請求項１５に記載の方法。
【請求項１７】
タスクモバイルエージェントが、アライブメッセージをスケジューリングモバイルエージェントに定期的に送るステップ；
アライブメッセージがタスクモバイルエージェントから所定の時間なくなっている場合、スケジューリングモバイルエージェントが、ボランティアを選択するステップ；および
スケジューリングモバイルエージェントが、タスクモバイルエージェントを新しいボランティアに送るステップ
をさらに含む、請求項１４に記載の方法。
【請求項１８】
予約したボランティアタイムの端にある場合、スケジューリングモバイルエージェントが、事前変動性障害メッセージをボランティアサーバに送るステップ；
ボランティアサーバが、代理ボランティア候補で応答するステップ；
スケジューリングモバイルエージェントが、前記代理ボランティア候補に移行するステップ
をさらに含む、請求項１４に記載の方法。
【請求項１９】
予約したボランティアタイムの端にある場合、タスクモバイルエージェントが、事前変動性障害メッセージをスケジューリングモバイルエージェントに送るステップ；
スケジューリングモバイルエージェントが、ボランティア候補で応答するステップ；および
タスクモバイルエージェントが、前記ボランティア候補に移行するステップ
をさらに含む、請求項１４に記載の方法。
【請求項２０】
タスクモバイルエージェントがボランティア変動性障害に悩まされる場合に、タスクモバイルエージェントが、タスク実行のチェックポイントを取り、変動性障害メッセージによってそのスケジューリングモバイルエージェントにボランティア変動性障害を通知するステップ；
所定時間の間に障害を起こしたボランティアからの再加入メッセージを受信しない場合に、スケジューリングモバイルエージェントが、再度スケジューリングを行うステップ
をさらに含む、請求項１４に記載の方法。
【請求項２１】
再度スケジューリングを行うステップが、スケジューリングモバイルエージェントが、最後にチェックポイントを行ったタスクモバイルエージェントを新しいボランティアに移行させるステップを含む、請求項２０に記載の方法。
【請求項２２】
タスクモバイルエージェントがボランティア干渉障害に悩まされる場合に、タスクモバイルエージェントが、タスク実行のチェックポイントを取るステップ；
所定時間の間に実行が再起動されない場合に、ボランティアが、干渉障害メッセージをそのスケジューリングモバイルエージェントに送るステップ；
スケジューリングモバイルエージェントが、ボランティア候補で応答するステップ；および
タスクモバイルエージェントが、ボランティア候補に移行するステップ
をさらに含む、請求項１４に記載の方法。
【請求項２３】
タスクモバイルエージェントが障害を起こした場合に、スケジューリングモバイルエージェントが、そのボランティアグループへの冗長の数を計算するステップ；
スケジューリングモバイルエージェントが、ボランティアグループの特性にしたがってボランティアを選択するステップ；および
スケジューリングモバイルエージェントが、タスクモバイルエージェントを選択されたボランティアに分配するステップ
をさらに含む、請求項１に記載の方法。
【請求項２４】
冗長ｒが、下記の式により計算される、請求項２３に記載の方法：
【数１】
2008071294.tif 000020
ここで、γは必要な信頼性であり、τ’はボランティア自律性障害に対する平均時間を意味し、Δはタスクの予定される演算時間である。
【請求項２５】
タスクモバイルエージェントを選択されたボランティアに分配するステップが、タスクモバイルエージェントをすべての選択されたボランティアに同時に分配し、同時にタスクモバイルエージェントを実行することを含む、請求項２３に記載の方法。
【請求項２６】
タスクモバイルエージェントを選択されたボランティアに分配するステップが、タスクモバイルエージェントを分配し、順番にそれを実行することを含む、請求項２３に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的にグリッド演算システムに関し、とくにピアツーピアグリッド演算においてモバイルエージェントを利用した適応グループスケジューリング方法に関する。
【背景技術】
【０００２】
グリッド演算システムは、仮想の機構をつくることによって、機関が所有する種々の演算ソースに対してアクセスを提供するプラットフォームである。一方、ピアツーピアグリッド演算システムは、インターネットの端（edge）の個人が所有する多数のアイドル状態のデスクトップコンピュータ（ボランティアという）をピアツーピア演算技術を利用して集約することによって、高スループットの演算を実現するプラットフォームである。ピアツーピアグリッド演算システムは、通常驚くほどの並列アプリケーションをサポートし、自身のデータと共に多くの同じ演算の事例からなる。これらのアプリケーションは、通常長時間にわたって高い処理能力が持続することが要求される科学的な問題に関する。
【０００３】
図１に示すように、ピアツーピアグリッド演算環境は、主にクライアント、ボランティアおよびボランティアサーバからなる。クライアントは並列ジョブの提出者である。ボランティアは、アイドル時に演算リソースを提供するリソース提供者である。ボランティアサーバは、提出されたジョブおよびボランティアを制御するセントラルマネージャである。クライアントは、並列ジョブをボランティアサーバに提出する。ジョブは、自身に特定の入力データを有するサブジョブに分けられる。
【０００４】
サブジョブは、タスクと呼ばれる。タスクは、並列コードおよびデータからなる。ボランティアサーバは、スケジューリング機構を用いてタスクをボランティアに配分する。各ボランティアは、ボランティアサーバから継続してデータを要求しながら、アイドル時にタスクを実行する。続いて各ボランティアがタスクを終了したときには、タスクの結果をボランティアサーバに戻す。最後に、ボランティアサーバは、ジョブの最終結果をクライアントに戻す。
【０００５】
ピアツーピアグリッド演算は、インターネットの端にあるデスクトップコンピュータ（すなわちボランティア）に基づくので、異種の能力、障害、変動性（すなわち一時的な存在）
信頼の欠如によって複雑化する。ボランティアは、種々の能力（すなわちＣＰＵ、メモリ、ネットワークバンド幅および待ち時間（latency））を有し、リンク障害およびクラッシュ障害の危険にさらされている。とくに、これらは、リソースを提供することに対して何ら見返りを受けない自発的な参加者である。結果として、これらは、一切の制限なく、自由にこの実行に参加でき、かつ離脱することができる。したがって、これらは、種々のボランティアタイム（すなわちリソース提供の時間）を有しており、また、公開実行（すなわちボランティアとしてのタスクの実行）は、予期せぬ離脱によって適宜中止しうる。さらに、ボランティアは、公開実行に完全に専念している訳ではないから、公開実行は、私的実行（すなわち個人ユーザとしての私的なジョブの実行）によって、一時的に停止される。
【０００６】
これらの不安定な状況は、ボランティア自律性の障害とみなされる。タスク実行の遅延または妨げを引き起こし、実行の部分的または全体的なロスとなる状況を含むからである。ボランティアは、実行の挙動にしたがって、ボランティア自律性障害の発生率が異なる。さらに、演算に不正に手を加え、改悪された結果を戻す悪質なボランティアもいる。これら性質の異なる特徴によって、ボランティアサーバによるタスクのスケジューリング、および配分されたタスクおよびボランティアの管理が困難になる。
【０００７】
ピアツーピアグリッド演算環境における演算の信頼性およびパフォーマンスを改善するために、スケジューリング機構は、異種の特性およびボランティアの変動性に起因するこれらの性質の異なる特徴に適応しなければならない。これを実現するために、ボランティアを類似の特性（とくに、ボランティア自律性障害）を有するグループに分類し、次いで種々のスケジューリング機構、耐故障および複製アルゴリズムを各グループに動的に適用するためのスケジューリング機構が要求される。
【０００８】
しかしながら、既存のピアツーピアグリッド演算システムは、グループ毎に基づくスケジューリング機構を提供しない。それに加えて、ボランティアサーバのみが集中的な手法でスケジューリング機構を実行する。結果として、既存の機構は、演算およびボランティアサーバのオーバーヘッドが高くなることに悩まされ、パフォーマンスの低下が生じる。
【発明の開示】
【０００９】
発明の概要
本発明では、スケジューリング機構を動的なピアツーピアグリッド演算環境に適応させるためにモバイルエージェント技術が利用される。
【００１０】
モバイルエージェントは、種々のタスクをユーザのために実行しながら、１つのノードから別のノードへ移行（migrate）するソフトウェアプログラムである。モバイルエージェントは、下記の利点を含む。
１）モバイルエージェントは、必要なサービスおよびデータを含むモバイルエージェントをリモートノードに送出することによって、ネットワーク負荷および待ち時間を減少させることができる。そして、サービスまたはデータは、リモートノードにおいて局所的に実行される。
２）モバイルエージェントは、頻発する断続的な切断を解決することができる。一旦モバイルエージェントが指定ノードに送出されると、ユーザとの直接接続をもはや必要としない。したがって、ユーザを代表するモバイルエージェントは、ユーザ（すなわちモバイルデバイス）がネットワークから切断されうる場合であっても、非同期的かつ自律的に動作する。
【００１１】
３）モバイルエージェントは、可動性実体（mobility entity）にいくつかのサービスまたはプロトコルを包含するので、動的なサービスのカスタム化およびソフトウェア開発が可能になる。
４）モバイルエージェントは、コンピュータであり、かつ輸送独立であって、現在の実行環境にしたがって自律的に反応するので、異種環境および動的変化に適応することができる。
【００１２】
ピアツーピアグリッド演算環境において、モバイルエージェントを利用することには、いくつかの利点がある。
１）種々のスケジューリング機構が、ボランティアの特性にしたがって一度に実行されうる。たとえば、これらのスケジューリング機構は、モバイルエージェント（すなわちスケジューリングモバイルエージェント）として実行されうる。ボランティアがボランティアグループに分類された後、特定のボランティアグループに対して最も適切なスケジューリングモバイルエージェントが、その特性にしたがってボランティアグループに割り当てられる。しかしながら、既存のピアツーピア演算システムは、種々のスケジューリング機構を適用することができない。これは、ボランティアサーバによって集約的な方法で実行されるのは、１つのみのスケジューリング機構であるからである。
【００１３】
２）モバイルエージェントは、スケジューリング、耐故障（fault tolerance）および複製アルゴリズムを非集約的方法で実行することによって、ボランティアサーバのオーバーヘッドを減少させることができる。スケジューリングモバイルエージェントは、ボランティアグループに分配される。そして、これらは、各ボランティアグループでボランティアサーバの直接制御なく、自律的にスケジューリング、耐故障および複製アルゴリズムを行う。
３）モバイルエージェントは、動的ピアツーピアグリッド演算環境に適応することができる。ピアツーピアグリッド演算環境において、ボランティアは、いつでも参加し、離脱することができる。さらにこれらは、能力（すなわちＣＰＵ、ストレージまたはネットワークバンド幅）、ロケーション、利用可能性、信頼性などの異種の特性によって特徴付けられる。これらの環境特性は、時間とともに変化する。モバイルエージェントは、この変化に対処しながら非同期かつ自律的に実行することができる。また、ボランティア自律性障害に対しては、モバイルエージェント自身が提供する移行機能性および複製機能性を利用して耐えることができる。
【００１４】
発明の詳細な説明
１．  システムモデル
１．１．  既存のピアツーピアグリッド演算モデル
図２に示すように、ピアツーピアグリッド演算の実行モデルは、次の６つの段階からなる：登録、ジョブ提出、タスク割当て、タスク実行、タスク結果返還、ジョブ結果返還段階。
・登録段階：ボランティアが、自身の情報をボランティアサーバに登録する。
・ジョブ提出段階：クライアントが、ジョブをボランティアサーバに委託する。
・タスク割当て段階：ボランティアサーバが、スケジューリング機構を利用して登録されたボランティアにタスクを分配する。
・タスク実行段階：ボランティアが各タスクを実行する。
・タスク結果返還段階：各ボランティアが、タスクの結果をボランティアサーバに戻す。
・ジョブ結果返還段階：ボランティアサーバが、ジョブの最終結果をクライアントに戻す。
【００１５】
図２において、ボランティアＶｉ（０≦ｉ≦ｎ）は、ボランティア情報Ωｉ（すなわち演算リソース特性）をボランティアサーバに登録し、タスクの実行に参加する。クライアントがジョブΓをボランティアサーバに委託すると、ボランティアサーバは、タスクΓｍをボランティアに割り当てる。ボランティアＶｉは、タスクΓｍを実行し、タスクΓｍの実行の結果Ｒｍをボランティアサーバに戻す。ボランティアサーバは、委託されたジョブΓの最終結果Ｒをクライアントに戻す。
【００１６】
１．２．  モバイルエージェントベースのピアツーピアグリッド演算モデル
モバイルエージェントは、種々のタスクをユーザのために実行しながら１つのノードから別のノードに移行するソフトウェアプログラムである。モバイルエージェントは、種々のボランティア特性と共に動的環境変化に適応することができる。さらに、モバイルエージェントは分散的に実行されるので、ボランティアサーバのオーバーヘッドを減少することができる。したがって、本発明者らは、モバイルエージェントがピアツーピアグリッド演算に適用される全体的な実行モデルを提案する。
【００１７】
モバイルエージェントベースのピアツーピアグリッド演算は、既存のピアツーピアグリッド演算と同様に作用する。しかしながら、いくつかの段階の動作は異なる（図３参照）。登録段階において、ボランティアは、ＣＰＵ、メモリ、ＯＳタイプなどの基礎特性と共にボランティアタイム、ボランティアサービスタイム、ボランティア可能性、ボランティア自律性障害、ボランティア信頼性などの追加特性を登録する。とくに、これらの追加特性は、動的演算および実行に関するので、これらは基礎特性よりも重要である。
【００１８】
ジョブ提出段階において、提出されたジョブを多数のタスクに分割する。タスクは、モバイルエージェント（すなわちタスクモバイルエージェント：Ｔ−ＭＡ）として実行される。
タスク割当て段階において、ボランティアサーバは全体のスケジューリング機構をもはや実行しない。その代わりに、スケジューリングモバイルエージェント（Ｓ−ＭＡ）によるスケジューリング手続きの実行を補助する。最初に、ボランティアサーバは、ロケーション、ボランティア自律性障害、ボランティアサービスタイムおよびボランティア可能性などの特性にしたがって、ボランティアグループを分類し、構築する。次に、スケジューリングモバイルエージェントをその特性にしたがってボランティアグループに分配する。最後に、スケジューリングモバイルエージェントが、タスクモバイルエージェントをボランティアグループのメンバーに分配する。
【００１９】
タスク実行段階において、別のボランティアに移行しながら、または障害発生時に自身を複製しながら、スケジューリングモバイルエージェントと協働してタスクモバイルエージェントを実行する。
タスク結果返還段階において、タスクモバイルエージェントは、各結果をそのスケジューリングモバイエルエージェントに戻す。すべてのタスクモバイルエージェントが、結果を戻すと、スケジューリングモバイルエージェントが結果を集め、収集した結果をボランティアサーバに戻す。誤った結果に対応するために、ボランティアサーバと協働して、多数決および無作為抽出検査（spot checking）が行われる。
ジョブ結果返還段階において、すべての結果をスケジューリングモバイルエージェントから受け取ったら、ボランティアサーバが、最終結果をクライアントに戻す。
【００２０】
簡潔に要約すると、既存の実行モデルと新規のモデルとの主な相違点は次のとおりである。１）新規のモバイルエージェントベースのピアツーピアグリッド演算モデルは、スケジューリングとタスクモバイルエージェントを利用する。２）ボランティア自律性障害、ボランティアサービスタイム、可能性および信頼性などのボランティアの動的特性にしたがって構築されたボランティアグループを利用する。３）種々のスケジューリング、耐故障および複製アルゴリズムを非集約的方法で同時に実行する。
【００２１】
１．３．  障害モデル
ピアツーピアグリッド演算環境において、ボランティアは、インターネットを介して接続されており、クラッシュ障害およびリンク障害の危険にさらされている。さらに、ピアツーピアグリッド演算は、自発的な参加に基づくものなので、ボランティアの自律性が尊重される。換言すると、ボランティアは、任意に公開実行の途中で離脱することができ、また、私的実行のためにいつでも公開実行を中断することが許される。ピアツーピアグリッド演算環境において、ボランティア自律性の障害は、クラッシュ障害およびリンク障害よりもかなり頻繁に生じる。よって、ボランティア自律性障害については、従来の障害と区別するとともに特別に対処すべきである。さらに、ボランティアの自律性障害には、種々の発生率およびタイプがある。ボランティア自律性障害の異なる発生率およびタイプは、直接影響を与えるので、よりよいパフォーマンスを達成し、信頼できる演算を保証するために、スケジューリング機構は、それらを考慮しなければならない。この目的のために、まずボランティア自律性障害を概念的に定義する。
【００２２】
ボランティア自律性障害を定義するために、表１の表記が用いられる。まず、ボランティアの参加および離脱のパターンをカテゴリー化する。パターンは、予定参加（ＥＪ）、予定離脱（ＥＬ）、予定外参加（ＵＪ）、予定外離脱（ＵＬ）にカテゴリー化される。
【００２３】
【表１】
2008071294.tif 000003
【００２４】
【数１】
2008071294.tif 000004
ＵＪは、前予定外参加ＵＪｂ、中予定外参加ＵＪｍ、後予定外参加ＵＪａにカテゴリー化される。さらに、予定外離脱ＵＬは、前予定外離脱ＵＬｂ、中予定外離脱ＵＬｍ、後予定外離脱ＵＬａにカテゴリー化される。
【００２５】
【数２】
2008071294.tif 000005
ボランティア自律性障害（Λ）は、ボランティア変動制障害（Φ）、ボランティア干渉障害（Ψ）に分類される。
【数３】
2008071294.tif 000006
【００２６】
定義１（ボランティア変動制障害）ボランティア変動制障害Φは、タスクΓｉの公開実行ξｉを自由に離脱することによって生じる公開実行の失敗である。
【数４】
2008071294.tif 000007
ボランティア変動性障害は、次のようにカテゴリー化される：予定外前Φｂ、予定外中Φｍ、予定Φ、予定外後Φａ。
【数５】
2008071294.tif 000008
【００２７】
定義２（ボランティア干渉障害）ボランティア干渉障害Ψは、個別ジョブΠｉの指摘実行πｉによって生じる公開実行ξｉの一時的な停止である。
【数６】
2008071294.tif 000009
【００２８】
ボランティア干渉障害Ψは、予定Ψｅｉと予定外Ψｕｉにカテゴリー化される。Ψｅｉは、私的実行が公開実行と定期的に干渉するとき（たとえば予約されたウィルスチェック）に起こるが、Ψｕｉは、キーボードまたはマウスの動作から始まる私的実行が公開実行と定期的に干渉するとき（たとえば一時的なｅメールのチェックなど）に起こる。ΦとΨにおいてはオペレーティングシステムが生きているのに対し、クラッシュ障害においてはシャットダウンしている点で、ΦおよびΨは、クラッシュ障害と異なる。Φは、Φがボランティアの意志によって起こる点でクラッシュ障害と異なる。Ψは、Ψにおいてはピアツーピアグリッド演算システムが生きているのに対し、Φにおいてはそれが動作していない点でΦと異なる。
【００２９】
Φは、公開実行の完了に関する。たとえば、離脱イベントは、公開実行の途中で任意に発生し、この実行は中止される（または停止される）。結果として、実行は完了されていない。すなわち、Φは、実行の完了を妨げる。他方、Ψは、公開実行の連続性に関する。たとえば、個人ユーザが公開実行の間に頻繁に私的実行を行う場合、公開実行は一時的に停止される。その結果、公開実行は、連続的に処理できなくなる。すなわち、Ψは公開実行の連続性を阻害する。
【００３０】
２．モバイルエージェントベースの適応グループスケジューリング機構（Mobile Agent based Adaptive Group Scheduling Mechanism）
ＭＡＡＧＳＭは、ボランティアグループを基礎とするスケジューリング機構を提供する。これは、異なるスケジューリング、耐故障および複製アルゴリズムを各ボランティアグループに適用させることによって、モバイルエージェントを利用する。このセクションでは、まずボランティアグループをボランティアの特性にしたがってどのように構築するかを説明する。そして、モバイルエージェントによって、スケジューリング、耐故障および複製アルゴリズムをボランティアグループにどのように適用するかを紹介する。最後に、障害時にボランティアグループをどのように管理するかを説明する。
【００３１】
２．１  ボランティアグループを構築する
ボランティアグループは、ボランティア自律性障害、ボランティア可能性、ボランティアサービスタイムなどについて類似の特性を有するボランティアの群である。スケジューリング手続きにおいてボランティアの特性に適した異なるスケジューリング機構を適用するために、ボランティアをまず同種のグループに形成する必要がある。最初に、ボランティアをそれらの特性にしたがって分類する。それから、ボランティアグループを分類し、構築する。
【００３２】
２．１．１．  ボランティアを分類する
ボランティアが分類される際には、ＣＰＵ、メモリ、ストレージおよびネットワーク容量が重要な要因となる。しかしながら、もっとも重要な要因は、演算の完了および連続性の意味で、ロケーション、ボランティアタイム、ボランティア自律性障害、ボランティア可能性およびボランティア信頼性であり、結果の信用性は、信頼性とともに変動性に起因する（図４参照）ボランティアタイムおよびボランティア可能性に強い関連性がある。ピアツーピアグリッド演算環境において、デスクトップコンピュータの能力は、非常に似かよっている一方で、ボランティアサービスタイム、可能性、および信頼性は、かなり上下する。この仕様では、ボランティアを分類するときに、ボランティアサービスタイム、ボランティア自律性障害、およびボランティア可能性に焦点をあてる。本発明は、誤った結果を検出し、また、それに耐えるための結果の承認に関連する信頼性は考慮しない。
ボランティアタイムおよびボランティア可能性は次のように定義する。
【００３３】
定義３（ボランティアタイム）ボランティアタイム（Ｙ）は、ボランティアがリソースを寄付するために一時停止する時間である。
【数７】
2008071294.tif 000010
ここで、予約されたボランティアタイム（ＹＲ）は、ボランティアが演算リソースを提供するときの予約された時間を意味する。ボランティアは、ＹＲの間はほとんど公開実行を行い、まれに私的実行を行う。しかし、利己的ボランティアタイムＹＳ（selfish volunteering time）は、予定されないボランティアタイムを意味する。したがって、ボランティアは、通常私的実行をＹＳの間に行い、時折公開実行を行う。
【００３４】
定義４（ボランティア可能性）ボランティア可能性αｖは、ボランティアがボランティアタイムＹの間に正しく作動し、ボランティアサービスを提示することができる可能性である。
【数８】
2008071294.tif 000011
ここで、ＭＴＴＶＡＦは、「ボランティア自律性障害までの平均時間」を意味し、ＭＴＴＲは、「再参加までの平均時間」を意味する。ＭＴＴＶＡＦは、ボランティア自律性障害が起こる前の平均された時間を意味し、ＭＴＴＲは、ボランティア自律性障害の平均持続期間を意味する。分配システムにおける従来の利用可能性が主にクラッシュ障害に関連するのに対し、αｖは、ボランティア自律性障害の度合いを反映している。
【００３５】
ＭＴＴＶＡＦおよびＭＴＴＲは、ボランティアがΦおよびΨを検出したときに動的に再計算される。ここで、ＭＶＴは、「平均ボランティアタイム」を意味する。記号
【数９】
2008071294.tif 000012
は、２つのイベントの組み合わせを意味する。記号
【数１０】
2008071294.tif 000013
は、時間間隔の結合を意味する。パラメータμは、負担定数（weight constant）である。ボランティアがタスクを実行するとき、μは、最初に１に設定される。μは、ΦおよびΨが起きたときは常に増大する。μは、ボランティアがタスクを終えたときに再び１に設定される。
【００３６】
【数１１】
2008071294.tif 000014
【００３７】
ケース１およびケース２は、ボランティア変動制障害および予定外参加の場合に、どのようにボランティア可能性を計算するかについて記載する。ケース３は、ボランティア干渉障害が起きたときに、どのようにボランティア可能性を計算するかについて記載する。パラメータμは、ボランティア可能性においてボランティア自律性障害の割合を反映させるために使用する。たとえば、ボランティア自律性障害が繰り返し頻繁に起こる場合、ボランティア可能性は、急激に低下する。さらに、平均ボランティアタイムがボランティア可能性に影響する。たとえば、平均ボランティアタイムが短い場合、ボランティア可能性は、ボランティア自律性障害によって強い影響を受ける。ケース１において、予定外ボランティアタイムが提供されるので、ボランティア可能性が増大する。逆に、ケース２およびケース３において、ボランティア可能性は、ボランティア自律性障害のために実際に減少する。
【００３８】
ボランティアは、ロケーションに応じてリージョンボランティアまたはホームボランティアにカテゴリー化される。ホームボランティアは、ホームでのリソース寄付者である。リージョンボランティアは、大学、機関などを含む組織と一般的に関連したリソース寄付者の群である。リージョンボランティアは、ＬＡＮまたはイントラネットで接続されており、一方ホームボランティアは、インターネットで接続されている。
ボランティアは、Ｙおよびαｖにしたがって４つのクラスにカテゴリー化される（図５参照）。クラスＡは、長いＹおよび高いαｖを有するボランティア群である。クラスＢは、短いＹおよび高いαｖを有するボランティア群である。クラスＣは、長いＹおよび低いαｖを有するボランティア群である。クラスＤは、短いＹおよび低いαｖを有するボランティア群である。
【００３９】
２．１．２  ボランティアグループを分類して作成する
ボランティアサーバは、ロケーション、ボランティア可能性およびボランティアサービスタイムなどのボランティアの特性にしたがって、ボランティアグループメンバーとしてボランティアを選択する。ボランティアサービスタイムは、次のように定義される。
【００４０】
定義５（ボランティアサービスタイム）ボランティアサービスタイム（Θ）は、ボランティアがＹの間に公開実行に参加するときの予定されたサービスタイムである。
【数１２】
2008071294.tif 000015
スケジューリングの手続きにおいて、Θは、Ｙよりもより適切である。なぜなら、Θは、ボランティア自律性障害Λの存在下で、ボランティアが実際に各タスクを実行したときの時間を意味するからである。したがって、ボランティアグループは、Ｙにしたがってではなく、Θにしたがって構築する。
ボランティアグループをロケーションに基づいて構築する場合、リージョンボランティアは同じグループに属し、ホームボランティアは、メンバー間の通信コストを減らすために同じグループに形成される。
ボランティアをグループ化するときに、αｖおよびΘを考慮した場合、ボランティアグループを４つのクラス（図６参照）にカテゴリー化する。ここで、Δは、予定されたタスクの演算時間である。
【００４１】
ボランティアは、Ａ’、Ｂ’、Ｃ’およびＤ’ボランティアグループの４つのクラスに分類される。ボランティアが高いαｖを有し、かつΘ≧Δの場合、それらはクラスＡ’に含まれる。ボランティアが高いαｖを有し、かつΘ＜Δの場合、それらはクラスＢ’に含まれる。ボランティアが低いαｖを有し、かつΘ≧Δの場合、それらはクラスＣ’に含まれる。ボランティアが低いαｖを有し、かつΘ＜Δの場合、それらはクラスＤ’に含まれる。
【００４２】
ボランティアグループは、ボランティアグループ構築のアルゴリズム（図７参照）を利用して構築する。
１）登録されたボランティアを、ロケーションに応じてホームボランティアまたはリージョンボランティアに分類する。
２）ホームボランティアおよびリージョンボランティアを、それぞれボランティアタイムおよびボランティア可能性によってＡ、Ｂ、Ｃ、Ｄクラスに分類する。
３）ボランティアサービスタイムおよびボランティア可能性にしたがって、ボランティアグループを構築する。
【００４３】
ボランティアグループは、次の特性を有する。Ａ’ボランティアグループは、確実にタスクを実行するために十分に高いΘおよび高いαｖを有する。これは、スケジューリングモバイルエージェントをホストする代理ボランティアとして使われる。Ｂ’ボランティアグループは、高いαｖを有するが、低いΘを有する。これは、演算時間が欠如しているため、タスクを完了することができない。Ｃ’ボランティアグループは、高いΘを有するが、低いαｖを有する。これは、タスクを実行するために十分な時間を有する。しかしながら、ボランティア自律性障害は、実行中に頻繁に発生する。したがって、これは、確実にタスクを実行するためには、故障耐性が必要になる。Ｄ’ボランティアグループは、低いΘおよび低いαｖを有する。これは、タスクを実行するための時間が不十分である。さらに、ボランティア自律性障害は、実行の間に頻繁に起こる。ボランティアグループの中では、Ａ’およびＣ’ボランティアグループが十分に時間があるので、主にタスクを実行する。
【００４４】
タスクが実行中に移行する場合、Ａ’およびＣ’ボランティアグループが障害に悩まされるときに、Ｂ’ボランティアグループを移行場所として用いることができる。そうでなければ、Ｂ’ボランティアグループは、ボランティアサービスタイムが短すぎてタスクを完了できないので、タスクを分配するのに適切でない。この場合、これは、テストするため、つまりその特性を計るためにタスクを実行する。Ｄ’ボランティアグループは、低いボランティア可能性と時間の欠如を原因として、管理コストが上昇する。また、Ｄ’ボランティアグループテストのためだけにタスクを実行する。チェックポイントが利用された場合、Ｂ’およびＤ’ボランティアグループは、時間を重視しないアプリケーションを実行するために使用することができる。
【００４５】
２．１．３  ボランティアグループを維持する
ボランティアグループは、３つのモード：タスクベースモード、時間ベースモードおよびカウントベースモードに維持する。タスクベースモードにおいて、タスクが完了すると常にボランティアグループが構築される。タイムベースモードは、計画するタスクが残っている場合、ボランティアグループを通常の間隔で構築する。カウントベースモードは、参加ボランティアの数が既定の数ｋ以上のときにボランティアグループを構築する。このｋは、ボランティアグループの大きさまたは冗長数に依存する。ボランティアグループの大きさは、主に維持コスト（すなわちタスクモバイルエージェントのスケジューリングおよび管理コスト、耐故障、複製など）に関連する。ボランティアグループは、スケジューリングエージェントがさらにタスクをメンバーに分配することができなくなるまで保持される。たとえば、すべてのメンバーがタスクを実行するために十分な時間がある場合、ボランティアグループを解散させる。ボランティアグループのメンバーは、ボランティアが落ちた場合（サブセクション４．３で詳述する）、他のものによって部分的に置き換えられる。
【００４６】
２．２  スケジューリングモバイルエージェントをスケジューリンググループに割り当てる
ボランティアグループを構築した後、ボランティアサーバがスケジューリングモバイルエージェント（Ｓ−ＭＡ）をボランティアグループに割り当てる。しかしながら、確実にタスクを終えるのに完全ではないボランティアグループがあるから、スケジューリング手続きにおいてＳ−ＭＡを直接ボランティアグループに割り当てることは実用的ではない。したがって、ボランティアグループを互いにそれぞれ組み合わせることによって、新しいスケジューリンググループを構築することが必要である（表２参照）。
【００４７】
【表２】
2008071294.tif 000016
【００４８】
表２において、最初の２つの組合せは最後の１つよりも適切である。なぜなら、最後の組合せではタスクが主にＡ’Ｃ’スケジューリンググループに分配されるのに対し、最初の２つの組合せではタスクが各グループに分配されるからである。さらに、最後の組合せにおいて、たとえタスクがＢ’Ｄ’スケジューリンググループに割り当てられるとしても
時間が不十分なためにタスクは完了されない。最初の２つの組合せを比較すると、最初の組合せは２番目の組合せよりも適切である。なぜなら、２番目の組合せにおいて、Ｃ’ボランティアグループは、Ｄ’ボランティアグループを補償しないのに対し、最初の組合せのＢ’ボランティアグループは、利用可能性についてＣ’ボランティアグループを補償することができるからである（Ａ’Ｄ’またはＡ’Ｂ’スケジューリンググループにおいて、Ａ’ボランティアグループは高い利用可能性と十分なΘを備えるので、Ａ’ボランティアグループがＤ’およびＢ’ボランティアグループを補償する）。したがって、本発明ではスケジューリング手続きにおける最初の組合せに焦点をあてる。
【００４９】
Ｓ−ＭＡは、代理ボランティアで実行する。代理ボランティアは、アルゴリズム（図８参照）を用いて選択する。代理ボランティアは、ボランティア可能性およびボランティアサービスタイムによって、また、ハードディスク容量およびネットワークバンド幅によって、順位付ける。そして、スケジューリンググループ用の代理ボランティアを順番に選択する。次に、各Ｓ−ＭＡが選択された代理ボランティアに送られる。
【００５０】
２．３．  タスクモバイルエージェントをグループメンバーに分配する
Ｓ−ＭＡをスケジューリンググループに割り当てた後、各Ｓ−ＭＡが、並列コードおよびデータからなるタスクモバイルエージェント（Ｔ−ＭＡ）をスケジューリンググループのメンバーに分配する。Ｓ−ＭＡは、既存のピアツーピアグリッド演算システムと異なり、ボランティアグループのタイプにしたがって、異なるスケジューリング、耐故障および複製アルゴリズムを実行する。
Ａ’Ｄ’スケジューリンググループのＳ−ＭＡは、次のスケジューリングを実行する。１）αｖによって、そしてΘによって、Ａ’ボランティアグループを順位付けする。２）Ｔ−ＭＡをアレンジしたＡ’ボランティアグループのメンバーに分配する。３）Ｔ−ＭＡが落ちた場合、複製アルゴリズムによって、落ちたタスクをＡ’ボランティアグループで選択された新しいボランティアに複製するか、またはタスク移行が許された場合に、Ａ’またはＢ’ボランティアグループで選択されたボランティアにそのタスクを移行する。
【００５１】
Ｃ’Ｂ’スケジューリンググループのＳ−ＭＡは、次のことを実行する。１）αｖによって、そしてΘによって、Ｃ’およびＢ’ボランティアグループを順位付けする。２）Ｔ−ＭＡをアレンジしたＣ’ボランティアグループのメンバーに分配する。３）Ｔ−ＭＡが落ちた場合、複製アルゴリズムによって、落ちたタスクをＣ’ボランティアグループで選択された新しいボランティアに複製するか、またはＢ’またはＣ’ボランティアグループで選択されたボランティアにそのタスクを移行する。
【００５２】
タスクは、まずＡ’Ｄ’スケジューリンググループに、それからＣ’Ｂ’スケジューリンググループに分配される。さらに、タスクは、まず高いαｖおよび長いΘを有するボランティアにまず分配される。スケジューリングアルゴリズムにおいて、チェックポイントを利用する場合、タスクをＢ’およびＤ’ボランティアグループには割り当てない。なぜならこれらは、確実にタスクを完了するために十分な時間を有していないからである。この場合、Ｂ’およびＤ’ボランティアグループは、テスト用のタスクを実行する。つまり、これらの特性を計る。たとえば、Ａ’およびＣ’ボランティアグループで実行されるタスクは、Ｄ’およびＢ’ボランティアグループにそれぞれ分配される。しかしながら、Ｂ’ボランティアグループは、タスク移行が認められる場合には、主なボランティアグループ（すなわちＡ’またはＣ’）を補助するために使用することもできる。たとえば、Ｃ’Ｂ’スケジューリンググループにおいて、Ｂ’ボランティアグループは、ボランティア可能性についてＣ’ボランティアグループを補償するために使用することができる。Ｃ’ボランティアグループ内のボランティアがボランティア自律性障害に悩まされていると仮定する。Ｂ’ボランティアグループのボランティアのボランティアタイムが落ちたボランティアにおけるボランティア自律性障害の持続期間を暗示する場合、一時停止したタスクをＢ’ボランティアグループの新しいボランティアに移行することができる。
【００５３】
複製を利用する場合、Ｓ−ＭＡは、冗長数を計算し、複製者（replica）（すなわち、複製された演算を実行するボランティア）を選択する。そして、Ｓ−ＭＡはＴ−ＭＡを選択された複製者に分配する。障害がある場合、Ｓ−ＭＡは、落ちたＴ−ＭＡを新しいボランティアに複製するか、または移行する。複製および耐故障アルゴリズムについては、サブセクション４．４および４．５にそれぞれ詳述する。
【００５４】
２．４  適応複製アルゴリズムを適用する
複製は、分配システムにおいて信頼性およびパフォーマンスを向上させるためのよく知られた技術である。ピアツーピアグリッド演算環境において、複製は主に信頼性、つまり故障耐性のために、または結果の承認のため、つまり誤った結果を検出し許容するために利用する。本発明は、確実なボランティア自律性障害に対する複製に焦点をあてたものである。適応複製アルゴリズムは、自動的に冗長数を調整し、各ボランティアグループの特性にしたがって適切な複製者を選択する。
【００５５】
２．４．１  冗長数の計算の仕方
複製を用いる場合、各Ｓ−ＭＡがそのボランティアグループの冗長数を計算する。それは、冗長数を計算するときに、ボランティア自律性障害、ボランティア可能性およびボランティアサービスタイムを同時に利用する。
【００５６】
ピアツーピアグリッド演算環境において、ボランティア自律性障害は、クラッシュ障害、リンク障害よりも頻繁に発生する。さらに、ボランティアは、ボランティア自律性障害について種々の割合および形式を有する。したがって、冗長数は、複製のオーバーヘッドを低減するために、類似の割合および形式の自律性障害を有するボランティアグループに基づいて計算されなければならない。しかしながら、既存の複製アルゴリズムは、複製アルゴリズムに基づいたボランティアグループを考慮していない。適応複製アルゴリズムは、ボランティア自律性障害、ボランティア可能性、ボランティアサービスタイムを下記のように利用している。
【００５７】
信頼性のための冗長数ｒは、下記の式１で計算する。この式では、システム寿命を指数関数的に指数分布させるようにしている。ここで、τはボランティアのＭＴＴＶＡＦを表し、τ’はボランティアグループのＭＴＴＶＡＦを表す。
【数１３】
2008071294.tif 000017
パラメータγは、信頼性閾値である。
【数１４】
2008071294.tif 000018
ここで、ｎは、ボランティアグループ内のボランティアの総数である。Ｖｎτは、ボランティアＶｎのτを意味する。
【００５８】
式１において、式ｅ−Δ／τ’は、各ボランティアグループの信頼性を表し、タスクをΔ内に完了する確率を意味する。（ボランティアの寿命が指数分布する場合、ボランティアＲ（ｔ）の信頼性は、Ｒ（ｔ）＝ｅ−λ’ｔである。パラメータλ’は、ボランティア自律性障害の割合を表す。時間間隔Δにおいてタスクを完了する確率を計算すると、１／λ’＝τ’なのでｅ−Δ／τ’が得られる）これは、ボランティア自律性障害を反映している。（１−ｅ−Δ／τ’）ｒは、すべての複製者が複製されたタスクを完了し損ねる確率を意味する。
必要とされる信頼性γが提供されると、ｒの値が式１より計算される。各ボランティアグループは異なるｒを有する。たとえば、Ａ’およびＣ’ボランティアグループは、Ｂ’ボランティアグループよりも小さいｒを有する。
【００５９】
２．４．２  Ｔ−ＭＡの複製者への分配の仕方
タスクを複製者に分配する方法は、２つの手法にカテゴリー化される：並列分配および順列分配（図９参照）である。
図９において、複製者はＶ０、Ｖ１およびＶ２（つまりｒ＝３）からなる。並列分配では、図９（ａ）において、タスクＴｍはすべてのメンバーに同時に分配され、そして同時に実行される。逆に、図９（ｂ）において、タスクＴｍは分配されて順番に実行される。
【００６０】
Ａ’ボランティアグループの場合、順列分配が並列分配よりも適切である。なぜなら順列分配の方がより多くのタスクを完了できるからである。たとえば、図９（ｂ）において、Ｖ０がタスクＴｍを完了した場合、Ｖ１およびＶ２においてそれを実行する必要がなくなる。Ａ’ボランティアグループは、ボランティア確率が高いので、障害（とくにボランティア自律性障害）を起こさずに確実にタスクを実行する確率が高い。しかしながら、Ａ’ボランティアグループは、図９（ａ）において並列分配を実行する場合、他のタスクを実行可能であるにもかかわらず、ボランティアが同じタスクを実行するという意味において、複製のオーバーヘッドを示す。Ａ’ボランティアグループと対照的に、Ｃ’ボランティアグループの場合には、順列分配が並列分配よりも適切である。なぜならＣ’ボランティアグループは、低いαｖに起因するボランティア自律性障害によって頻繁に悩まされるからである。
【００６１】
２．５．  障害に対処する
ボランティア自律性障害は、タスク実行の遅れおよび妨害をもたらす。ピアツーピアグリッド演算環境において、これらは、クラッシュ障害およびリンク障害よりも頻繁に起こる。さらに、ボランティアは、ボランティア自律性障害について種々の発生率および形式を有する。ピアツーピアグリッドシステムは、スケジューリング手続きにおいて、発生率と形式にしたがって種々の耐故障アルゴリズムを行う必要がある。これを達成するために、ボランティア自律性障害を従来の障害と区別しながら、各ボランティアグループの特性にしたがって異なる耐故障アルゴリズムを適用する。スケジューリングモバイルエージェントおよびタスクモバイルエージェントが、障害発生時にいかに働くかについてこのサブセクションで説明する。
【００６２】
ボランティア自律性障害Φは、ボランティア自律性障害Φおよびボランティア干渉障害Ψが起きてもオペレーティングシステムが生きている点で、クラッシュ障害が起きるとシャットダウンするクラッシュ障害とは異なる。Φは、Φがボランティアの要求によって発生する点でクラッシュ障害と異なる。Φの場合には動作していないが、Ψは、Ψが起きてもピアツーピアグリッド演算システムが生きている点でΦと異なる。
ボランティアサーバは、タイムアウトを利用してＳ−ＭＡのクラッシュ障害を検出する。同様に、Ｓ−ＭＡは、Ｔ−ＭＡのクラッシュ障害を検出する。これを達成するために、Ｓ−ＭＡがアライブメッセージをボランティアサーバに送る。同様に、Ｔ−ＭＡがアライブメッセージをＳ−ＭＡに送る。管理オーバーヘッドを減らすために、Ｄ’ボランティアグループのＴ−ＭＡは、アライブメッセージを送らない。ボランティアは、オペレーティングシステムがシャットダウンしていないので、自身でボランティア自律性障害を検出することができる。Ｔ−ＭＡまたはＳ−ＭＡがボランティア自律性障害を検出すると、Ｓ−ＭＡまたはボラティアサーバにそれぞれ通知する。
【００６３】
２．５．１  Ｓ−ＭＡの障害
Ｓ−ＭＡが自律性障害に悩まされることはほとんどない。なぜなら、Ａ’ボランティアグループの中から選択された代理ボランティアで実行されるからである。Ｓ−ＭＡは、スケジューリンググループのリスト、スケジューリング表およびタスク結果などの情報を安定的なストレージに記憶する。Ｓ−ＭＡが落ちた場合、情報が新しいボランティアに送られる。図１０は、Ｓ−ＭＡの耐故障アルゴリズムを示す。
ボランティアサーバがＳ−ＭＡのクラッシュ障害を検出した場合、図８に示す代理ボランティアセクションのアルゴリズムによって、新しい代理ボランティアが選択される。次に、Ｓ−ＭＡおよびスケジューリング情報が新しく選択された代理ボランティアに送られる。Ｓ−ＭＡがボランティア自律性障害に悩まされる場合、変動性障害（VolatilityFailure）メッセージをボランティアサーバに送る。Ｓ−ＭＡがボランティアタイムの間に再び参加した場合、再参加（Rejoin）メッセージをそのボランティアサーバに送る。ボランティアサーバが、変動性障害メッセージを受け取った後の間隔内に再参加メッセージを受け取らない場合、Ｓ−ＭＡを新しい代理ボランティアに送る。
【００６４】
Ｓ−ＭＡが予約されたボランティアタイムの端にある場合、事前変動性障害（InAdvanceVolatilityFailure）メッセージをボランティアサーバに送る。この場合、ボランティアサーバは、代理ボランティア候補で応答する。Ｓ−ＭＡは、代理ボランティア候補に移行する。
ボランティア干渉障害の場合、Ｓ−ＭＡは、ピアツーピアグリッドシステムが生きているという意味においてスケジューリング手続きを実行することができるので、何ら行動を起こさない。
【００６５】
２．５．２  Ｔ−ＭＡの障害
Ｔ−ＭＡは比較的低い利用可能性を有するので、Ｓ−ＭＡよりも頻繁にボランティア自律性障害に悩まされる。チェックポイントを利用する場合、Ｔ−ＭＡは、実行状態についてＭＴＴＶＡＦの割合でチェックポイントを行う。図１１、図１２および図１３は、Ｔ−ＭＡの耐故障アルゴリズムを示す。
Ｓ−ＭＡは、Ｔ−ＭＡのクラッシュ障害を検出すると、新しいボランティアを選択する。チェックポイントを利用する場合、Ｓ−ＭＡが最近チェックポイントを行ったＴ−ＭＡ’をそれに送る。そうでなければ、Ｓ−ＭＡがＴ−ＭＡを新しいものに再分配する。各Ｓ−ＭＡは、冗長数ｒのうちにＴ−ＭＡを再分配する。
Ｔ−ＭＡが予約されたボランティアタイムの端にある場合、事前変動性障害メッセージをそのＳ−ＭＡに送る。ボランティア候補を受け取った後、ボランティア候補に移行するか、または複製される。
【００６６】
Ｔ−ＭＡがボランティア自律性障害Φに悩まされる場合、タスク実行のチェックポイントを取り、変動性障害メッセージによってΦのＳ−ＭＡを通知する。次に、Ｓ−ＭＡが既定の時間間隔の間に、落ちたボランティアから何らの再参加メッセージも受け取らなかった場合、Ｔ−ＭＡを再構築する。チェックポイントおよび移行が行われると、Ｓ−ＭＡがＴ−ＭＡ’を新しいボランティアに移行させる。そうでなければ、Ｓ−ＭＡが冗長数ｒによってＴ−ＭＡを複製する。
Ｔ−ＭＡがボランティア干渉障害Ψに悩まされる場合、実行のチェックポイントを取る。そして、間隔の間に実行が再起動しない場合、ボランティアは干渉障害（InterferenceFailure）メッセージをそのＳ−ＭＡに送る。ボランティア候補を受け取った後、Ｔ−ＭＡはボランティア候補を移行させるか、または複製する。
【００６７】
管理オーバーヘッドを低減するために、このアルゴリズムにおいて、実行中に障害が発生した場合におけるＤ’ボランティアグループのための耐故障機構がない。Ｄ’ボランティアグループは、たとえばボランティア自律性障害、ボランティア可能性、ボランティアサービスタイムを計算する目的で、テスト用のタスクを実行する。
【００６８】
３．  実行と評価
３．１．  実行
「Ｋｏｒｅａ＠Ｈｏｍｅ」および「ＯＤＤＵＧＩ」モバイルエージェントシステムに基づいて、本発明の適応スケジューリング機構を実行した。Ｋｏｒｅａ＠Ｈｏｍｅプロジェクトは、インターネット４上に分布する多数のＰＣの大量の演算能力を役立てることを試みている。さらに、本発明の発明者によって開発されたＯＤＤＵＧＩは、信頼できる、確実な耐故障のモバイルエージェントの実行をサポートするモバイルエージェントシステムである。図１４は、Ｋｏｒｅａ＠Ｈｏｍｅにおける実行のスクリーンショットを表す。
【００６９】
現在Ｋｏｒｅａ＠Ｈｏｍｅは、６，７４４のボランティアを有し、平均してこれらの５２４がアクティブ状態にある。１ヶ月にわたって（つまり２００５年７月）パフォーマンス測定を行った。図１５（ａ）および（ｂ）は、１日毎のパフォーマンス（最高４１２．４３Ｇｆｌｏｐｓ、平均３５２．４６Ｇｆｌｏｐｓ）および１時間毎のパフォーマンス（最高３５６．５３Ｇｆｌｏｐｓ、平均２６５．０９Ｇｆｌｏｐｓ）をそれぞれ示す。Ｋｏｒｅａ＠Ｈｏｍｅにおいて、ボランティアは、グローバル危機管理（global risk management）、新薬候補発見（new drug candidate discovery）および気候予測（climate prediction）の３種のアプリケーションの１つに参加する事ができる。ボランティアのＣＰＵタイプはいくらか異なるが、多くは類似のＣＰＵパフォーマンスを示す。たとえば、インテルのＰｅｎｔｉｕｍ（登録商標）４が全体の約５５％を占め、Ｐｅｎｔｉｕｍ（登録商標）３が約１２％、Ｃｅｌｅｒｏｎが約６％を表すなどである。
【００７０】
３．２．評価
本出願人らのＭＡＡＧＳＭを既存のスケジューリング機構で評価する。この評価は、スケジューリング手続きにおいてボランティアグループが考慮されたかに応じて、パフォーマンスの改善がどれくらい達成されたかに焦点をあてる。この目的のために、異なるボランティアサービスタイムΘおよびボランティア可能性αｖを有するボランティアグループを意図的にセットアップした。
【００７１】
本出願人らの適応スケジューリング機構をイーガースケジューリング（eager scheduling）と比較する。イーガースケジューリングでは、ボランティアは、その現在のタスクを終了するとすぐにボランティアサーバーに新しいタスクを要求する。その結果、ボランティアが熱心に（eager）に働くほど、多くのタスクが実行される。グリッド演算環境では、たとえばＭＣＴ、ＭＥＴ、ＳＡ、ＫＰＢ、ｍｉｎ−ｍｉｎ、ｍａｘ−ｍｉｎおよびＳｕｆｆｅｒａｇｅヒューリスティクス（sufferage heuristics）など多数のスケジューリングヒューリスティクス（scheduling heuristics）がある。本出願人らは、既存のスケジューリングヒューリスティクスの中でもイーガースケジューリングに適応する。なぜならグリッド演算における他のヒューリスティクスよりも直接的で単純だからである。とくに、イーガースケジューリングは、グリッド演算のヒューリスティクスよりも動的な環境により適応するので、主に動的ピアツーピアグリッド演算環境において用いられる。
【００７２】
ＭＡＡＧＳＭを評価するためにシミュレーションを利用する。このシミュレーションは、Ｋｏｒｅａ＠Ｈｏｍｅにおいて本物のボランティアで行った。このアプリケーションは、新薬候補発見である。このアプリケーションでのタスクは、専用のＰｅｎｔｉｕｍ（登録商標）１．４ＧＨｚで１６分間の実行時間を使う。表３は、異なるボランティアグループ、ボランティアサービスタイム、ボランティア可能性でのシミュレーション環境を表す。表３のそれぞれのケースのために３，２００のボランティアが１時間のシミュレーションに参加した。ケース１において、Ａ’ボランティアグループは、他のグループよりも多くのボランティアを有する。ケース２は、他のグループと比べると、より多くのボランティアがＡ’およびＣ’ボランティアグループに属することを示している。ケース３では、Ａ’およびＢ’ボランティアグループが他のグループよりも多くのボランティアを有している。ケース４では、Ｄ’ボランティアグループが他のグループよりも多くのボランティアを有している。表３を分析すると、ケース１は、他のケースよりもボランティア可能性およびボランティアサービスタイムが大きいことが観察できる。ケース４は、他のケースよりもボランティア可能性およびボランティアサービスタイムが小さい。このシミュレーション環境を基礎として、各ケース毎にこのシミュレーションを１０回行った。
【００７３】
表３に示すように、２００のボランティアが種々のボランティア自律性障害、ボランティア可能性およびボランティアサービスタイムを有する。本出願らは、ＭＴＴＶＡＦの範囲を１／０．２〜１／０．００２分、ＭＴＴＲの範囲を３〜１０分と仮定した。このシミュレーションは、完了したタスクの数および冗長数をパフォーマンスの尺度（metric）として用いた。さらに、複製が適用されたかどうかに応じて完了したタスクを計測した。スケジューリンググループ（つまりＡ’Ｄ’およびＣ’Ｂ’）を基礎とする２つのパフォーマンス尺度を計測した。
【００７４】
【表３】
2008071294.tif 000019
【００７５】
図１７は、完了したタスクの平均数を表す。図１７において、ＥＳおよびＡＳは、既存のイーガースケジューリングおよびＭＡＡＧＳＭをそれぞれ表す。さらに、ＡＳ（Ａ’Ｄ’）およびＡＳ（Ｃ’Ｂ’）は、ＭＡＡＧＳＭの各スケジューリンググループを表す（ＡＳ（Ａ’Ｄ’）とＡＳ（Ｃ’Ｂ’）は、ＡＳに等しいことに留意されたい）。図１７が示すように、ＭＡＡＧＳＭは、は、既存のイーガースケジューリング方法よりも多くのタスクを完了する。得られた結果は、下記のファクターを示唆している。第１に、Ａ’ボランティアグループは、より良いパフォーマンスを得るために重要な役割を果たしている。Ａ’ボランティアグループの中のメンバー数が徐々に減少すると（つまりケース１からケース４）、完了するタスクの数が減少する。
【００７６】
第２に、Ａ’およびＣ’ボランティアグループのメンバーの数は、Ｂ’およびＤ’ボランティアグループのそれよりもより重要である。たとえば、ケース１およびケース２は、ケース３およびケース４よりも多くのタスクを完了する。第３に、ボランティア可能性は、パフォーマンスの改善と強く関連している。たとえば、最も高いボランティア可能性を有するケース１は、他のケースよりも多くのタスクを完了した。他方、ボランティア可能性が最も低いケース４が完了するタスクは、他のケースのそれよりも少ない。最後に、Ａ’ボランティアグループのメンバーの数が減少し、Ｂ’およびＤ’ボランティアグループのメンバーの数が増加すると、ＭＡＡＧＳＭとイーガースケジューリングの違いが大きくなる。
【００７７】
Ａ’、Ｂ’、Ｃ’またはＤ’ボランティアグループ内の失敗したタスクまたは一時停止したタスクが質の悪いボランティアに代替的に再分配されるという意味において、この結果は、イーガースケジューリングでは予期されたものである。他方、ＭＡＡＧＳＭはグループ毎を基礎にスケジューリングを実行するので、望ましくない状況は起きない。たとえば、Ｃ’ボランティアグループ内の失敗したタスクまたは一時停止したタスクは、Ｂ’およびＤ’ボランティアグループに再分配されない。ケース１における違いは、Ａ’ボランティアグループのメンバーが他のグループよりも多いので、他のケースより小さい。換言すると、望ましくない状況がケース１ではほとんど発生しない。
【００７８】
図１８は、ケース２においてボランティア自律性障害に耐えるために複製を利用するときの完了したタスクの平均数を表す。図１８において、ｘ軸上のティック値（tick value）１．０は、実際には０．９９を表す（式１を参照）。この図から、信頼性閾値が増大すると、完了するタスクの数は減少する。得られた結果は、高い信頼性を保つためにより多くのタスクが複製されるべきだということを示している。
【００７９】
図１９は、ケース２の冗長数ｒを表す。ＭＡＡＧＳＭは、スケジューリングモバイルエージェントが複製アルゴリズムを各ボランティアグループに適用するので、イーガースケジューリングよりも小さいｒを有する。すなわち、ボランティアグループのボランティア自律性障害に応じて冗長数を適切に調節する。さらに、Ａ’ボランティアグループは、Ｃ’ボランティアグループよりも高いボランティア可能性およびボランティアサービスタイムを有しているので、Ａ’Ｄ’スケジューリンググループは、Ｃ’Ｂ’スケジューリンググループよりも小さいｒを有している。Ｃ’ボランティアグループはＡ’ボランティアグループよりも頻繁にボランティア自律性障害に悩まされているので、前者は後者よりも大きいｒを有する。したがって、Ａ’ボランティアグループの場合では、小さいｒで信頼性閾値を満足する。Ｃ’ボランティアグループの場合では、信頼性閾値を充足するために大きいｒが必要になる。結果として、Ａ’ボランティアグループは、複製オーバーヘッドを低減できるので、より多くのタスクを実行することができる。最後に、信頼性がより要求されるのにしたがって、冗長数が増大する。
【００８０】
図２０は、複製の事例での完了タスクの平均数を表す。図２０では、０．８の値を信頼性閾値として使用した。図１７と比較すると、ＭＡＡＧＳＭとイーガースケジューリングの違いが大きい。ＭＡＡＧＳＭでは、Ａ’ボランティアグループは、比較的小さいｒを有するので、より多くのタスクを完了することができる。他方、イーガースケジューリングは、同種のグループを考慮していないので、下記の望ましくない状態が繰り返し発生する。この場合、失敗したタスクは新しいボランティアに分配すべきである。
【００８１】
イーガースケジューリングでは、ボランティアグループを考慮せずに新しいボランティアが選択される。新しく選択されたボランティアがＢ’またはＤ’ボランティアグループに属する場合、ボランティア自律性障害の割合が高いので、それもまた失敗するであろう。質の悪いボランティアが連続して選択される場合は、質の高いボランティアが選ばれるまで、タスクが連続して他のボランティアに再分配される。このような望ましくない状態は、多くのボランティアがＢ’、Ｃ’またはＤ’ボランティアグループに属する場合、頻繁に繰り返し起こる。したがって、クラス３およびクラス４におけるＭＡＡＧＳＭとイーガースケジューリングの違いは、クラス１およびクラス２におけるそれよりも大きい。
【００８２】
図２１は、すべてのケースの冗長数ｒを表している。Ａ’ボランティアグループのメンバーの数が増加すると、ＭＡＡＧＳＭとイーガースケジューリングの違いも大きくなる。たとえば、ケース１は最も大きいＡ’ボランティアグループを有し、したがって、ＭＡＡＧＳＭの冗長数ｒは、イーガースケジューリングのそれと似かよっている。ケース２は、
多くのＡ’およびＣ’ボランティアグループのメンバーを有しているので、ＭＡＡＧＳＭとイーガースケジューリングの隔たりは、ケース１に示されるものよりも大きい。類似の結果がケース３およびケース４で示される。イーガースケジューリングと比較して、ＭＡＡＧＳＭは、ＭＡＡＧＳＭが冗長数をボランティアグループに基づいて計算するのでイーガースケジューリングとは対照的に、小さいｒを有する。ＭＡＡＧＳＭにおいて、ボランティア自律性障害の割合が高いボランティアグループは、ｒが大きいことが必要で、その逆もまた同様である。結果として、ＭＡＡＧＳＭは、イーガースケジューリングよりも多くのタスクを完了する。Ａ’ボランティアグループは、図２１に示すように、イーガースケジューリングよりも小さい冗長数を有するので、より多くのタスクを完了することができる。
【図面の簡単な説明】
【００８３】
【図１】ピアツーピアグリッド演算環境を示す図である。
【図２】既存のピアツーピアグリッド演算モデルを示す図である。
【図３】ピアツーピアグリッド演算モデルに基づくモバイルエージェントを示す図である。
【図４】ボランティアの分類基準を示す図である。
【図５】ボランティアの分類を示す図である。
【００８４】
【図６】ボランティアグループの分類を示す図である。
【図７】ボランティアグループ構築のアルゴリズムを示す図である。
【図８】代理ボランティア選択のアルゴリズムを示す図である。
【図９】並列分配および順列分配の概念を示す図である。
【図１０】Ｓ−ＭＡの障害の存在下における耐故障アルゴリズムを示す図である。
【００８５】
【図１１】Ｔ−ＭＡの障害の存在下における耐故障アルゴリズムを示す図である。
【図１２】Ｔ−ＭＡの障害の存在下における耐故障アルゴリズムを示す図である。
【図１３】Ｔ−ＭＡの障害の存在下における耐故障アルゴリズムを示す図である。
【図１４】Ｋｏｒｅａ＠Ｈｏｍｅのスクリーンショットを示す図である。
【図１５】（ａ）１日毎および（ｂ）１時間毎のパフォーマンスをトレースしたパフォーマンストレース図である。
【図１６】Ｋｏｒｅａ＠ＨｏｍｅにおけるＣＰＵタイプのボランティアを示す図である。
【００８６】
【図１７】完了したタスクの平均数を示すグラフである。
【図１８】事例２の複製の事例で完了したタスクの平均数を示すグラフである。
【図１９】事例２における平均冗長数を示すグラフである。
【図２０】複製の事例（信頼性閾値＝０．８）で完了したタスクの平均数を示すグラフである。
【図２１】各事例における平均冗長数を示す図である。
【図１】
2008071294.tif 000021
【図２】
2008071294.tif 000022
【図３】
2008071294.tif 000023
【図４】
2008071294.tif 000024
【図５】
2008071294.tif 000025
【図６】
2008071294.tif 000026
【図７】
2008071294.tif 000027
【図８】
2008071294.tif 000028
【図９】
2008071294.tif 000029
【図１０】
2008071294.tif 000030
【図１１】
2008071294.tif 000031
【図１２】
2008071294.tif 000032
【図１３】
2008071294.tif 000033
【図１４】
2008071294.tif 000034
【図１５】
2008071294.tif 000035
【図１６】
2008071294.tif 000036
【図１７】
2008071294.tif 000037
【図１８】
2008071294.tif 000038
【図１９】
2008071294.tif 000039
【図２０】
2008071294.tif 000040
【図２１】
2008071294.tif 000041
【外国語明細書】
2008071294.tif 000042
2008071294.tif 000043
2008071294.tif 000044
2008071294.tif 000045
2008071294.tif 000046
2008071294.tif 000047
2008071294.tif 000048
2008071294.tif 000049
2008071294.tif 000050
2008071294.tif 000051
2008071294.tif 000052
2008071294.tif 000053
2008071294.tif 000054
2008071294.tif 000055
2008071294.tif 000056
2008071294.tif 000057
2008071294.tif 000058
2008071294.tif 000059
2008071294.tif 000060
2008071294.tif 000061
2008071294.tif 000062
2008071294.tif 000063
2008071294.tif 000064
2008071294.tif 000065
2008071294.tif 000066
2008071294.tif 000067
2008071294.tif 000068
2008071294.tif 000069
2008071294.tif 000070
2008071294.tif 000071
2008071294.tif 000072
2008071294.tif 000073
2008071294.tif 000074
2008071294.tif 000075
2008071294.tif 000076
2008071294.tif 000077
2008071294.tif 000078
2008071294.tif 000079
2008071294.tif 000080
2008071294.tif 000081
2008071294.tif 000082
2008071294.tif 000083
2008071294.tif 000084
【図１】
2008071294.tif 000085
【図２】
2008071294.tif 000086
【図３】
2008071294.tif 000087
【図４】
2008071294.tif 000088
【図５】
2008071294.tif 000089
【図６】
2008071294.tif 000090
【図７】
2008071294.tif 000091
【図８】
2008071294.tif 000092
【図９】
2008071294.tif 000093
【図１０】
2008071294.tif 000094
【図１１】
2008071294.tif 000095
【図１２】
2008071294.tif 000096
【図１３】
2008071294.tif 000097
【図１４】
2008071294.tif 000098
【図１５】
2008071294.tif 000099
【図１６】
2008071294.tif 000100
【図１７】
2008071294.tif 000101
【図１８】
2008071294.tif 000102
【図１９】
2008071294.tif 000103
【図２０】
2008071294.tif 000104
【図２１】
2008071294.tif 000105