(57)【要約】【課題】  環境の動的変化に対応しつつタスク分散処理を行う。【解決手段】  環境の動的変化を検出し、動的変化が検出されたときには、当該動的変化によって不要となる情報を削除し、また、既に蓄積されている動的変化以外の原因で削除された情報の中から当該動的変化によって復元すべき情報を復元し、これらの削除または復元を繰り返すことより、動的変化に対応しつつタスク分散処理を実行する。【選択図】  図１
2006338289.tif 000002
【特許請求の範囲】
【請求項１】
複数のタスクを２以上の情報処理装置に分散させて実行するタスク分散処理装置であって、
所定のタスク分散決定方法に基づきタスク分散処理を実行するタスク分散決定方法実行部と、
このタスク分散決定方法実行部により所定の環境下において不要として削除された情報を格納する削除情報蓄積部と、
前記所定の環境の動的変化を検出する動的変化検出部と、
当該動的変化の状況を他のホストへ送信あるいは他のホストの動的変化の状況を受信する動的変化通信部と、
前記動的変化検出部および前記動的変化通信部により得られた前記所定の環境の動的変化の情報に基づき前記タスク分散決定方法実行部内に存在する情報のうち当該動的変化により新たに不要となる情報と前記削除情報蓄積部内に格納された情報のうち当該動的変化により新たに復元させる情報とを判断する動的変化対応処理部と
を備え、
前記タスク分散決定方法実行部は、前記動的変化対応処理部の判断に基づき前記動的変化に伴い新たに不要となる情報を削除して前記削除情報蓄積部に格納し、前記動的変化に伴い新たに必要となる情報を前記削除情報蓄積部から復元させる手段を備えた
ことを特徴とするタスク分散処理装置。
【請求項２】
コンピュータ装置にインストールすることにより、そのコンピュータ装置に、複数のタスクを２以上の情報処理装置に分散させて実行するタスク分散処理装置に相応する機能を実現させるプログラムであって、
前記コンピュータ装置に、
所定のタスク分散決定方法に基づきタスク分散処理を実行するタスク分散決定方法実行機能と、
このタスク分散決定方法実行機能により所定の環境下において不要として削除された情報を格納する削除情報蓄積機能と、
前記所定の環境の動的変化を検出する動的変化検出機能と、
当該動的変化の状況を他のホストへ送信あるいは他のホストの動的変化の状況を受信する動的変化通信機能と、
前記動的変化検出機能および前記動的変化通信機能により得られた前記所定の環境の動的変化の情報に基づき前記タスク分散決定方法実行機能内に存在する情報のうち当該動的変化により新たに不要となる情報と前記削除情報蓄積機能内に格納された情報のうち当該動的変化により新たに復元させる情報とを判断する動的変化対応処理機能と
を実現させ、
前記タスク分散決定方法実行機能として、前記動的変化対応処理機能の判断に基づき前記動的変化に伴い新たに不要となる情報を削除して前記削除情報蓄積部に格納し、前記動的変化に伴い新たに必要となる情報を前記削除情報蓄積機能から復元させる機能を実現させる
ことを特徴とするプログラム。
【請求項３】
複数のタスクを２以上の情報処理装置に分散させて実行するタスク分散処理装置に適用される情報処理方法であって、
前記タスク分散処理装置は、
所定のタスク分散決定方法に基づきタスク分散処理を実行するタスク分散決定方法実行ステップと、
このタスク分散決定方法実行ステップにより所定の環境下において不要として削除された情報を格納する削除情報蓄積ステップと、
前記所定の環境の動的変化を検出する動的変化検出ステップと、
当該動的変化の状況を他のホストへ送信あるいは他のホストの動的変化の状況を受信する動的変化通信ステップと、
前記動的変化検出ステップおよび前記動的変化通信ステップにより得られた前記所定の環境の動的変化の情報に基づき前記タスク分散決定方法実行ステップに用いる情報のうち当該動的変化により新たに不要となる情報と前記削除情報蓄積ステップにより格納された情報のうち当該動的変化により新たに復元させる情報とを判断する動的変化対応処理ステップと
を実行し、
前記所定の環境の動的変化が検出された後の前記タスク分散決定方法実行ステップの実行に先立って、前記動的変化対応処理ステップの判断に基づき前記動的変化に伴い新たに不要となる情報を削除し、前記動的変化に伴い新たに必要となる情報を復元させるステップを実行する
ことを特徴とする情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット等の分散システムにおけるタスク割当および資源割
当に関する。なお、並列システムは分散システムの一種であるため、本発明は並列システムでも分散システムでも使えるが、それぞれのシステムにおいては用語が異なるため、以下では並列システムにおけるプロセッサ、ＣＵＰ、分散システムにおけるホスト、エージェント、プロセス、計算機、サーバ、情報処理装置等の用語を一括してホストと呼ぶ。
【０００２】
なお、厳密にはホストとプロセスまたはエージェントは異なるが、本発明の範囲では区別の必要がないためホストと呼んで差し支えない。また、タスクとしてエージェントやプロセスやプロセスを扱うことがあるため、上記エージェントおよびプロセスはホストとして扱われる場合とタスクとして扱われる場合とがある。
【背景技術】
【０００３】
タスク割当および負荷分散手法は従来から数多く存在し、その実施方法も集中的な手法から分散的な手法までさまざまである。ここでは、非同期完全分散環境において、大域的に最適な負荷分散を実現する負荷分散を考えるが、従来は、このような非同期完全分散環境で分散的に最適解を求める手法は存在しない。なお、ここでの最適解とは、負荷量最大のサーバの負荷量を最小化することであり、別の意味での最適化ならば従来法に存在する。
【０００４】
従来の分散環境における動的なタスク割当、いわゆる負荷分散は基本的に、マルチキャストを利用して他サーバの負荷量を収集し、各サーバが他のサーバと一対一で交渉してタスクを移動させることにより、局所的に負荷を均衡化させ、それを各サーバが自律的に繰り返すことで大域的な負荷の均衡化を実現しようというものである（例えば、非特許文献１参照）。
【０００５】
このような手法は基本的に近似解法のひとつである局所探索法の分散版とみなせる。つまり、一対一交渉である限りは最適解が求まる保証はない。この交渉を一対一でなく、局所探索法の、λ−ｏｐｔ近傍（例えば、非特許文献２参照）と同様に全サーバの協調にまで拡張できれば最適解に収束するが、従来の分散手法にはそのような協調を行う手法は存在しない。
【０００６】
一方、局所的な均衡化でなく、最初から大域的な均衡化を目指す手法も存在する。それが、特許文献１、特許文献２、特許文献３において述べられている。これらは大域的な最適化を目指した動的かつ分散的な手法であるが、基本的に新たに到着したタスクの割当先を決める手法であり、現在割当済のタスクも移動対象にしての最適化はできないし、最適化の指標も違う。
【０００７】
これらとは別に、負荷分散を対象としていないものの、負荷分散を最適化問題として捉えて整数計画法で解くことが考えられる。整数計画法を解く分散手法としては、分枝限定法を分散環境で実行するように拡張した手法が二つ存在する。同期型分枝限定法（例えば、非特許文献３参照）と分散分枝限定法（例えば、非特許文献４参照）がそれである。
【０００８】
同期型分枝限定法は逐次の分枝限定法を分散環境でシミュレートしているだけである。そのため、分散処理の並列性や耐故障性といった利点が失われてしまう。
【０００９】
一方、分散分枝限定法は、全情報を単一サーバに集約して分枝限定法を開始し、分枝が生じたら別のサーバに分枝先の処理（部分問題）を移す、という方法で分散処理を実現している。これにより処理の並列性は保証できるが、大域的な処理は単一サーバが管理することになるので、耐故障性や動的な変化への対応の可能性が低くなる。負荷分散のように元々分散している情報に関する最適化問題には向かない手法である。
【００１０】
なお、集中的環境の場合には、通信遅延の影響や情報の局所性の問題が生じないため、数理計画法に基づいた厳密解法や近似解法を採用することができる。しかし、実際の分散システムでは通信遅延の影響や情報の局所性の問題が無視できないため、集中的環境で扱える問題は小規模な問題などに限られてしまう。
【００１１】
【非特許文献１】Ｂ．Ａ．Ｓｈｉｒａｚｉ、Ａ．Ｒ．Ｈｕｒｓｏｎ、ａｎｄ  Ｋ．Ｍ．Ｋａｖｉ  ｅｄｓ．、Ｓｃｈｅｄｕｌｉｎｇ  ａｎｄ  Ｌｏａｄ  Ｂａｌａｎｃｉｎｇ  ｉｎ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ  Ｐｒｅｓｓ、１９９５
【非特許文献２】柳浦睦憲、茨木俊秀、組合せ最適化−メタ戦略を中心として−、朝倉書店、２００１
【非特許文献３】平山勝敏、横尾真、分散不完全制約充足問題、人工知能学会論文誌、Ｖｏｌ．  １４、Ｎｏ．４、ｐｐ．６３６−６４５、１９９９
【非特許文献４】Ｊａｒｏｓｌａｖ  Ｂ´Ｓｔ．ａｎｋｏｖ´ａｒｔａ、Ｏｌｇａ．ｅｐ´ａ、  ａｎｄ  Ｍｉｃｈａｌ  Ｐ．ｅｃｈｏｕ．ｃｅｋ、“Ｄｉｓｔｒｉｂｕｔｅｄ  Ｂｒａｎｃｈ  ａｎｄ  Ｂｏｕｎｄ  Ａｌｇｏｒｉｔｈｍ  ｉｎ  Ｃｏａｌｉｔｉｏｎ  Ｐｌａｎｎｉｎｇ、”  Ｌｅｃｔｕｒｅ  Ｎｏｔｅ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、  Ｖｏｌ．  ２３２２  （ＭＡＳＡ２００１）、  ｐｐ．  １５９−１６８、  ２００２
【特許文献１】特開２００２−１５７２３４号公報
【特許文献２】特開２００２−３１２３３７号公報
【特許文献３】特開２００３−５０７１０号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
従来の分散環境での分枝限定法にはそれぞれ先に述べたような欠点がある。本発明では、より分散環境に適し、かつ、最適解が求められる手法を構築する。具体的には、非同期完全分散環境において、情報を単一サーバに集約したり全体の制御を単一サーバが担ったりせずに、最適解（最大負荷量の最小化）を求める。さらに、逐次環境における分枝限定法と同様に、実行途中で止めた場合にその時点で得られているものがひとつの近似解とでき、また、逆に他の近似解法で得られた近似解を利用することもできる手法にする。さらに、動的な変化（例えば、タスクやホストの故障または消滅または撤去またはタスクの生成またはホストの新規接続）に対応することもできる手法にする。
【００１３】
本発明が対象とする問題を下記のように定義する。ネットワークＧ＝（Ｈ，Ｌ）を考える。ここで、ＨはネットワークＧ上のｎ個のホストの集合で、Ｌはそれらホストを結ぶ通信リンクの集合である。また、ｍ個のタスクに対応するｍ次元ベクトルｘ＝（ｘ1  ｘ2  …  ｘm）Tを考え、この各要素がタスクとしてＧ上のホストに分散している。ｘj＝ｉはｈiがタスクｊを保持していることを表している。つまり、１≦ｘi≦ｎとなる。このタスクの配置ｘの初期状態としてｘ0を定義する。このような状況の下で、下記のような最適化問題を考える。
【００１４】
【数１】
2006338289.tif 000003
【００１５】
【数２】
2006338289.tif 000004
上記の典型的な問題が負荷分散である。このとき、ｆi（ｘ）はｈiのＣＰＵコストを、ｇi（ｘ）はタスク間の通信コストを、ｋi（ｘ0，ｘ）はタスクのｈiへの移動コストを表す。もし、∀i，ｇi（ｘ）＝ｋi（ｘ0，ｘ）＝０であれはこの問題はＣＰＵコストのみを考慮した問題となり、基本的なｍｕｌｔｉｐｒｏ-ｃｅｓｓｏｒ  ｓｃｈｅｄｕｌｉｎｇと同等になる。なお、ｙ0i＝ｙi（ｘ0，ｘ0）とする。
【００１６】
この問題においては下記の制約が存在する。
【００１７】
１．初期状態でｈiが持つ情報：
（ａ）隣接するホスト集合Ｈi。
（ｂ）ｈiに初期状態で存在するタスクτj（ｘj＝ｉ）とそれ固有の情報（ｗj，ｂj，∀r，ｃjr）。
（ｃ）ｈiに初期状態で存在するタスクτjが通信する相手とそれが存在するホスト。
（ｄ）各ホストへのルーティングテーブル。
【００１８】
ただし、あるホストが与えられたときに、そこへのルーティングの際に最初に訪れるｈiの隣接ホストが分かればよい。具体的には、ｈiへ至るルーティングとしてｒi（ｈj）を与え、ｒi（ｈj）はｈiのいずれかの隣接ホストを返す関数、つまり、∀ｈj，ｒi（ｈj）∈Ｈiとなる。このルーティングテーブルはホスト間で整合している必要がある。現在動的な環境を考えているので、このルーティングテーブルの更新が必要になる。
【００１９】
しかし、本手法とルーティングを独立に扱えるようにするために、ここでは詳細なルーティングテーブルの更新法は規定しない。仮定として、初期状態では隣接ホストへのルーティングのみ可能でその後ホストの存在を知った時点でルーティングテーブルも構築されるとする。同様に、Ｑ（ｑjr）も初期状態では隣接ホストとの間の通信リンクの値しか知らないが、ルーティングテーブルの構築と同時に知ることができると仮定する。
【００２０】
２．各ホストが直接通信できる相手は隣接ホストに限られる。
【００２１】
３．各ホストは（隣接ホストでない）通信先ホストが与えられればそこへのルーティング（対応する隣接ホスト）とそこへの単位量当たりの通信コスト（Ｑ）は得られるが、システム中に存在するホスト数やタスク数に関する情報は得られない。同時に、現在そのホストが持つホストやタスクの情報がシステムのすべての情報かどうかも知ることはできない。
【００２２】
４．各ホストは他のホスト固有の情報（ｐj）を知ることはできない。
【００２３】
また、本発明で扱う分散システムは非同期システムである。非同期システムでは、各通信リンクがＦＩＦＯ（先入先出）で通信遅延が有限であるという仮定の下で各プロセス（ホスト）が独立に送受信処理を行う。また、同一プロセス（ホスト）上では二つのイベント（故障、タスク生成、メッセージ受信など）が同時には起こらないことを仮定する。
【００２４】
すなわち、本発明は、非同期完全分散環境において全情報を単一サーバに集約させず、かつ、システムを制御する唯一の存在もない状況において、最適解を求めることが可能となり、動的変化にも対応することができる情報処理システムを提供することを目的とする。
【課題を解決するための手段】
【００２５】
本願出願人は、非同期完全分散環境において、最適な負荷分散を実現する非同期分散分枝限定法を既に提案している（特願２００４−３８０８２０号、本願出願時に未公開、以下では先願と呼ぶ）。しかし、当該先願では、非同期分散分枝限定法においては、動的な変化（タスクやホストの故障または消滅または撤去またはタスクの生成またはホストの新規接続）には完全には対応できていない。また、近似解を適用して初期状態が変化した場合の扱いもできていない。
【００２６】
そこで、本発明では動的な変化に対応した非同期完全分散環境上の最適化手法を構築する。動的な変化（近似解を適用する場合も含む）に対応するということ以外は非同期分散分枝限定法と同じ性質を実現できる手法にする。
【００２７】
また、本発明は、先願の改良である。そのため、タスク分散決定方法についてはブラックボックス的な扱いとし、その中身は従来の発明に従う。ただし、タスク分散決定方法が内部で格納している詳細なデータは外部にある本発明の方法により操作できる。
【００２８】
すなわち、本発明は、２以上の情報処理装置（本明細書ではホストと呼ぶことにした）を有し、複数のタスクを前記２以上のホストに分散させて実行するタスク分散処理装置であって、所定のタスク分散決定方法に基づきタスク分散処理を実行するタスク分散決定方法実行部と、このタスク分散決定方法実行部により所定の環境下において不要として削除された情報を格納する削除情報蓄積部と、前記所定の環境の動的変化（タスクの生成または消滅または自身のホストの故障またはネットワークへの新規接続など）を検索する動的変化検索部と、当該動的変化の状況を他のホストへ送信あるいは他のホストの動的変化の状況を受信する動的変化通信部と、前記動的変化検出部および前記動的変化通信部により得られた前記所定の環境の動的変化の情報に基づき前記タスク分散決定方法実行部内に存在する情報のうち当該動的変化により新たに不要となる情報と前記削除情報蓄積部内に格納された情報のうち当該動的変化により新たに復元させる情報とを判断する動的変化対応処理部とを備え、前記タスク分散決定方法実行部は、前記動的変化対応処理部の判断に基づき前記動的変化に伴い新たに不要となる情報を削除して前記削除情報蓄積部に格納し、前記動的変化に伴い新たに必要となる情報を前記削除情報蓄積部から復元させる手段を備え、動的な変化が起こった後でもタスク分散決定方法を停止させることなくそのまま実行できるように前記タスク分散決定方法実行部の内部状態を変更させることを特徴とする。
【００２９】
また、本発明をプログラムとして実現することもできる。この場合には、本発明は、コンピュータ装置にインストールすることにより、そのコンピュータ装置に、複数のタスクを２以上のホストに分散させて実行するタスク分散処理装置に相応する機能を実現させるプログラムであって、前記コンピュータ装置に、所定のタスク分散決定方法に基づきタスク分散処理を実行するタスク分散決定方法実行機能と、このタスク分散決定方法実行機能により所定の環境下において不要として削除された情報を格納する削除情報蓄積機能と、前記所定の環境の動的変化を検出する動的変化検出機能と、当該動的変化の状況を他のホストへ送信あるいは他のホストの動的変化の状況を受信する動的変化通信機能と、前記動的変化検出機能および前記動的変化通信機能により得られた前記所定の環境の動的変化の情報に基づき前記タスク分散決定方法実行機能内に存在する情報のうち当該動的変化により新たに不要となる情報と前記削除情報蓄積機能内に格納された情報のうち当該動的変化により新たに復元させる情報とを判断する動的変化対応処理機能とを実現させ、前記タスク分散決定方法実行機能として、前記動的変化対応処理機能の判断に基づき前記動的変化に伴い新たに不要となる情報を削除して前記削除情報蓄積部に格納し、前記動的変化に伴い新たに必要となる情報を前記削除情報蓄積機能から復元させる機能を実現させることを特徴とする。
【００３０】
また、本発明を情報処理方法として実現することもできる。この場合には、本発明は、複数のタスクを２以上のホストに分散させて実行するタスク分散処理装置に適用される情報処理方法であって、前記タスク分散処理装置は、所定のタスク分散決定方法に基づきタスク分散処理を実行するタスク分散決定方法実行ステップと、このタスク分散決定方法実行ステップにより所定の環境下において不要として削除された情報を格納する削除情報蓄積ステップと、前記所定の環境の動的変化を検出する動的変化検出ステップと、当該動的変化の状況を他のホストへ送信あるいは他のホストの動的変化の状況を受信する動的変化通信ステップと、前記動的変化検出ステップおよび前記動的変化通信ステップにより得られた前記所定の環境の動的変化の情報に基づき前記タスク分散決定方法実行ステップに用いる情報のうち当該動的変化により新たに不要となる情報と前記削除情報蓄積ステップにより格納された情報のうち当該動的変化により新たに復元させる情報とを判断する動的変化対応処理ステップとを実行し、前記所定の環境の動的変化が検出された後の前記タスク分散決定方法実行ステップの実行に先立って、前記動的変化対応処理ステップの判断に基づき前記動的変化に伴い新たに不要となる情報を削除し、前記動的変化に伴い新たに必要となる情報を復元させるステップを実行することを特徴とする。
【発明の効果】
【００３１】
本発明により、非同期完全分散環境において全情報を単一ホストに集約せず、かつ、システムを制御する唯一の存在もない状況において、ホストやタスクの故障または追加生成があった場合、あるいは、近似解を適用して初期状態が変化した場合であっても、その変化した状態に対応して、停止することなく最適解を求めることが可能となる。これはどの従来法でも実現できていない。また、この性質により、大規模システムにより適した動作を行うことができる。
【発明を実施するための最良の形態】
【００３２】
本発明実施例のタスク分散処理装置を図１を参照して説明する。図１は本実施例のタスク分散処理装置のブロック構成図である。
【００３３】
本実施例は、複数のタスクを２以上のホストに分散させて実行するタスク分散処理装置であって、図１に示すように、所定のタスク分散決定方法に基づきタスク分散処理を実行するタスク分散決定方法実行部５と、このタスク分散決定方法実行部５により所定の環境下において不要として削除された情報を格納する削除情報蓄積部４と、前記所定の環境の動的変化を検出する動的変化検出部２と、当該動的変化の状況を他のホストへ送信あるいは他のホストの動的変化の状況を受信する動的変化通信部１と、動的変化検出部２および動的変化通信部１により得られた前記所定の環境の動的変化の情報に基づきタスク分散決定方法実行部５内の記憶領域６に存在する情報のうち当該動的変化により新たに不要となる情報と削除情報蓄積部４内に格納された情報のうち当該動的変化により新たに復元させる情報とを判断する動的変化対応処理部３とを備え、タスク分散決定方法実行部５は、動的変化対応処理部３の判断に基づき前記動的変化に伴い新たに不要となる情報を記憶領域６から削除して削除情報蓄積部４に格納し、前記動的変化に伴い新たに必要となる情報を削除情報蓄積部４から記憶領域６に復元させる手段を備えたことを特徴とする。
【００３４】
また、本実施例のプログラムを用いることにより、汎用のコンピュータ装置によって、本実施例のタスク分散処理装置を実現することができる。すなわち、本実施例は、コンピュータ装置にインストールすることにより、そのコンピュータ装置に、複数のタスクを２以上のホストに分散させて実行するタスク分散処理装置に相応する機能を実現させるプログラムであって、前記コンピュータ装置に、所定のタスク分散決定方法に基づきタスク分散処理を実行するタスク分散決定方法実行機能と、このタスク分散決定方法実行機能により所定の環境下において不要として削除された情報を格納する削除情報蓄積機能と、前記所定の環境の動的変化を検出する動的変化検出機能と、当該動的変化の状況を他のホストへ送信あるいは他のホストの動的変化の状況を受信する動的変化通信機能と、前記動的変化検出機能および前記動的変化通信機能により得られた前記所定の環境の動的変化の情報に基づき前記タスク分散決定方法実行機能内に存在する情報のうち当該動的変化により新たに不要となる情報と前記削除情報蓄積機能内に格納された情報のうち当該動的変化により新たに復元させる情報とを判断する動的変化対応処理機能とを実現させ、前記タスク分散決定方法実行機能として、前記動的変化対応処理機能の判断に基づき前記動的変化に伴い新たに不要となる情報を削除して前記削除情報蓄積部に格納し、前記動的変化に伴い新たに必要となる情報を前記削除情報蓄積機能から復元させる機能を実現させることを特徴とする。
【００３５】
本実施例のプログラムは記録媒体に記録されることにより、前記コンピュータ装置は、この記録媒体を用いて本実施例のプログラムをインストールすることができる。あるいは、本実施例のプログラムを保持するサーバからネットワークを介して直接前記コンピュータ装置に本実施例のプログラムをインストールすることもできる。
【００３６】
これにより、汎用のコンピュータ装置を用いて、本実施例のタスク分散処理装置を実現することができる。
【００３７】
本実施例の情報処理方法を図２を参照して説明する。図２は本実施例の情報処理方法の処理手順を示すフローチャートである。
【００３８】
本実施例は、複数のタスクを２以上のホストに分散させて実行する図１に示すタスク分散処理装置に適用される情報処理方法であって、図１に示すタスク分散処理装置は、図２に示すように、所定のタスク分散決定方法に基づきタスク分散処理を実行するタスク分散決定方法実行ステップ（Ｓ１：タスク割当処理（削除情報監視・記録））と、このタスク分散決定方法実行ステップにより所定の環境下において不要として削除された情報を格納する削除情報蓄積ステップ（Ｓ１に内包されている削除情報監視・記録）と、前記所定の環境の動的変化を検出する動的変化検出ステップ（Ｓ２：動的変化監視、Ｓ３：動的変化検出）と、当該動的変化の状況を他のホストへ送信あるいは他のホストの動的変化の状況を受信する動的変化通信ステップ（Ｓ２：動的変化監視、Ｓ３：動的変化検出）と、前記動的変化検出ステップおよび前記動的変化通信ステップにより得られた前記所定の環境の動的変化の情報に基づき前記タスク分散決定方法実行ステップに用いる情報のうち当該動的変化により新たに不要となる情報と前記削除情報蓄積ステップにより格納された情報のうち当該動的変化により新たに復元させる情報とを判断する動的変化対応処理ステップ（Ｓ４：動的変化により削除される状態の検索、Ｓ５：削除する状態の有無判断、Ｓ７：削除情報中で復元される状態の検索、Ｓ８：復元する状態の有無判断）とを実行し、前記所定の環境の動的変化が検出された後の前記タスク分散決定方法実行ステップ  （Ｓ１：タスク割当処理）の実行に先立って、前記動的変化対応処理ステップ（Ｓ４：動的変化により削除される状態の検索、Ｓ７：削除情報中で復元される状態の検索）の判断に基づき前記動的変化に伴い新たに不要となる情報を削除し（Ｓ６：状態の削除）、前記動的変化に伴い新たに必要となる情報を復元させる（Ｓ９：状態の復元）ステップを実行することを特徴とする。
【００３９】
以下では、本実施例をさらに詳細に説明する。
（故障や動的変化のモデルの規定）
【００４０】
本実施例の詳細な説明に先立って、故障や動的変化のモデルを規定する。故障・動的変化としては次の四つの場合を考える。
１．ホストの追加
２．ホストの故障または削除
３．タスク（変数）の追加または生成
４．タスク（変数）の故障または消滅
それぞれの場合においてモデル上での実際の動作を下記のように定義する。
【００４１】
１．ホストの追加：
新たなホストｈｎ＋１をネットワークＧに追加する。これに伴い、ｈｎ＋１と他のホストをつなぐ通信リンクも追加される。このホストが追加されたとき、その存在は通信リンクがつながった隣接ホストで確認できる。
【００４２】
２．ホストの故障または削除：
ホストｈiをネットワークＧから削除する。同時に、ｈiにつながっている通信リンクもＧから削除される。さらに、このホスト上にあったタスク（変数）もシステムから削除される。なお、それらタスクが他のホストへの移動中にホストが故障する（削除される）ことはないと仮定する。
【００４３】
実際には故障の検出も問題だが、ここでは故障・削除ホストは機能停止前に故障・削除を知らせるメッセージを送信可能であると仮定する。具体的なメッセージの内容はアルゴリズムで規定できる。実際には、何かしらの方法で隣接するホストが故障を検出して、そのホストで故障ホストから同メッセージを受け取ったものとして動作するのが現実的かと思われる。
【００４４】
３．タスク（変数）の追加または生成：
ホストｈiにτｍ＋１タスクが追加される。これにより、新たに相互作用を及ぼすタスクが規定され、他のタスクの通信負荷量も変化を及ぼすことがある。ただし、この通信相手の認識はアルゴリズムでは行わず、プラットフォーム側で対応し、アルゴリズムからは自動的に相互に認識されているように見える。
【００４５】
４．タスク（変数）の故障または消滅：
ホストｈi上にあったタスクτjが削除される。同時に相互作用のあったタスクとの通信負荷量を０にすることで、相互作用を解消する。現実には、このタスクτjが削除されることで、他の相互作用のあるタスクの実行ができなくなることもあり得るが、ここではそこまで踏み込まない。なお、そのような場合には連鎖的にタスクを削除すればモデル上での実現は可能である。
【００４６】
なお、簡単のために、一旦故障したり削除されたりしたホストや変数は、その後復帰する場合には識別子が変わるものとする。つまり、一度使用された識別子はシステム中では２度と使われないことを仮定する。また、近似解を適用することで初期配置が変わり、かつ、割当コストを消費した場合には、一旦それらタスク（変数）を削除し、割当（移動）完了後に再度そのタスクを新しい識別子で追加する。
（実施例の詳細な説明）
【００４７】
ここでは、図１に示したタスク分散処理装置の挙動の具体的な一形態としてのアルゴリズムである動的分散分枝限定方法を示す。なお、先願に関係する部分、つまり、非同期分散分枝限定方法も含んだ状態で記述する。
（アルゴリズム）
【００４８】
本アルゴリズムは分枝限定法と基本としてはいるものの、通常の分枝限定法のような単一の分枝木にもとづいた解の探索を行うのではなく、各ホストごとに異なる分枝木に基づいて並列に解の探索を行う。具体的には、分枝は初期状態と隣接ホストから送られてきた情報に基づいて起こる。また、各状態（各変数の値を固定したもの：解の候補（タスク割当）のひとつ、または、隣接ホストへの移動を含むもの）における目的関数値（負荷量）の計算は、各ホストごとに自身の値を計算し、そのなかの最大値を取る必要がある。つまり、目的関数値の計算にもホスト間の協調が必要になる。ここまでは従来の非同期分散分枝限定法と同じである。本アルゴリズムでは、さらに、故障や動的な変化の対応も必要になる。
【００４９】
本アルゴリズムは、逐次環境における分枝限定方法と同様に、基本機能は大きく分けて三つから成り立つ。
【００５０】
１．暫定解の更新：ＯｐｔＦｌｏｏｄＭａｘアルゴリズムを、最大値を最小値に変え、終了判定を除いた状態で利用して実現する。
【００５１】
２．分枝操作：二つあるいはそれ以上の状態の組合せにより実現し、すべての可能な組合せを試す。そして、新たに生成された状態にタスクの移動が含まれていればその移動先へその状態を通知する。さらにすべての状態を列挙するために特別な処理（後述）も必要に応じて行う。また、目的関数値の協調計算処理もこの操作の一部となる。
【００５２】
３．限定操作：ある状態が現在の暫定解よりも良い解を導き出すことがないと判明した場合には、その状態を限定（削除）する。そして、必要があればその事実を関係する隣接ホストへ通知する。
【００５３】
これらのうち、分枝操作だけでも最適解を求めることは可能である。つまり、すべての状態の列挙だけを行い、それをし尽くした段階で最小の目的関数値を与える状態を選択すれば最適解は求まる。他の二つの機能は効率化のための工夫であり、暫定解の更新は他の近似解法の結果の反映にも使われる。
【００５４】
この三つの基本機能は非同期分散分枝限定法と同じであるが、動的分散分枝限定法では、さらに動的な変化に対応するための機能も加わる。
【００５５】
詳細なアルゴリズムを下記に示す。ただし、上記のようにアルゴリズムから一部だけを取り出しても動作することに注意のこと。なお、近似解を適用して、変数を実際に移動させた場合には、変数の削除と追加がほぼ同時に起こったものとして扱うことで対応できる。また、“［］”で囲まれた文章は処理内容でなく、その処理の説明文である。
【００５６】
局所変数の定義：
ｄi：ｈiの次数（隣接ホスト数）。故障または動的変化には自動対応と仮定。
【００５７】
Ｖ＝｛ｖ１，ｖ２，…，ｖｌi｝：ｘの部分集合で、初期状態において∀j，ｖi＝ｉとなっている変数集合であり、∀j，∃ｒ，ｖj＝ｘrである。故障または動的変化には自動対応と仮定。
【００５８】
Ｈi：隣接ホスト集合。故障または動的変化には自動対応と仮定。
【００５９】
Ｓ：状態とその状態における目的関数値とｂｏｏｌｅａｎ変数の組の集合。初期状態では｛｝（｛｝は空集合を表す）。ｂｏｏｌｅａｎ変数はその状態における目的関数値が大域的に定まっている（ｔｒｕｅ）か否（ｆａｌｓｅ）かを示す。
【００６０】
Ｓ′：状態とその状態における目的関数値とｂｏｏｌｅａｎ変数の組の集合、ただし、その状態自身は既に限定されているが、他の状態と組合わせることでより良い解を構成する可能性があるもの。初期状態では｛｝。
Ｉ：Ｖに含まれる変数の移動の集合。初期状態では｛｝。
Ｓｂ：終端となった状態とその状態における目的関数値とｂｏｏｌｅａｎ変数の組の集合、動的な変化によって再び解候補に復帰する可能性を持つ。
ｙ：暫定値。初期状態では∞。
ｈａ：暫定値ｙを与えるホスト。初期状態ではｈ0［存在しないホスト］。
ｘ＊：暫定解。初期状態では｛｝。
【００６１】
Ｙ0＝｛（ｙj，ｈj）｜ｈj：ｈjが知っているホスト｝：他のホストの目的関数値とそのホスト番号の組の集合である。初期状態では自身と隣接ホストのみを知っており、その値はε（値が未設定）である。また、ｙjが取り得る値は、目的関数値を表す整数値、値が未設定を意味するε、実行不可能を意味する∞、故障を意味する−∞がある。ｙj＝−∞はこの組がＹ0から削除されたことと等価である。
【００６２】
なお、Ｓ，Ｓ′，Ｉ，Ｓｂの要素の扱いはそのなかの要素を代表にして扱う。つまり、「状態ｓをＳに追加する」と述べた場合には、実際には状態ｓ，ｓの目的関数値、ｂｏｏｌｅａｎ変数を一組としてＳに追加される。
【００６３】
局所関数の定義：
ｙ（ｓ）：状態ｓのｈiにおける目的関数値［問題定義におけるｙi（ｘ0，ｘ）と同等］。
ｙＳ（ｓ）：値が未固定の変数を含む状態ｓのｈiにおける目的関数値の下限。
Ｒ（ｓ）：ｓによって目的関数値が変化し得るホストの集合。Ｒ（ｘ0）＝｛｝。ただし、これは局所関数であるが、局所的な状態だけから計算することが不可能な場合があるため、その場合の値は隣接ホストから送られてきた情報を基に構成することになる。
【００６４】
Ｒ（ｘj）：ｘjを初期配置から変える［移動させる］ことで目的関数が変化し得るホストの集合。ｘjを初期状態で持つホストでのみ計算可能であり、その他のホストはｍｉｇｒａｔｅメッセージに添付された値によってのみ知り得る。実際には単なるホスト集合でなく、初期配置ホスト、通信相手の変数集合とその初期状態での配置ホストも知ることができる。Ｒ（ｓ）はＲ（ｘj），ｘj∈ｓの情報を統合して作られる。
Ｆ（Ｈ）：あるホスト集合Ｈを入力とし、その各ホストへのルーティングに含まれる隣接ホスト集合を出力する関数。
【００６５】
なお、Ｒ（ｓ），Ｒ（ｘj）は局所的な関数であるが、動的な変化が起こった直後以外はホスト間で異なる値（集合）を持つことはないため、計算方法以外、つまりその値自体は大域的な関数と大きな違いはない。
起動直後またはホスト／変数の追加または生成直後の処理：
【００６６】
１．自身の目的関数値ｙ′＝ｙi（ｘ0，ｘ0）を計算し、それが実行可能であればｉｎｉｔ（ｙ′，ｉ）を全隣接ホストに送信する。もし制約をみたさないため実行不可能であればｉｎｉｔ（∞，ｉ）を全隣接ホストに送信する。
【００６７】
２．∀ｖ∈Ｖに対し、可能な移動を列挙（生成）し、Ｉに加える。（｜Ｉ｜＝｜Ｈi｜ｌi）変数追加時は追加された変数に対してのみ行う。
【００６８】
３．初期状態ｘ0が実行可能であれば、ｘ0とその目的関数値を組にしてＳに加える。
【００６９】
４．新たに生成されたｓI∈Ｉとなる各状態ｓIに対し、移動するタスク（変数）をｘjとし、メッセージｍｉｇｒａｔｅ（ｘj，Ｒ（ｘj），ｘ0，｛｝）をｘjが移動する先のホストへ送信する。
【００７０】
５．変数追加時には新たにｓI∈Ｉとなる各状態とＳ，Ｓ′中の状態との統合を行い、それによってできた状態が限定操作で終端とならなければ、必要に応じてｍｉｇｒａｔｅメッセージを移動先ホストへ送信する。
【００７１】
６．変数追加時に、それによって目的関数値が変化する状態があれば、すべての変数が固定されているときにはｌｏｃａｌ＿ｍａｘメッセージ、移動を含む場合にはｍｉｇｒａｔｅメッセージを適宜送り、再計算する［いずれの場合でもその状態における自身の目的関数値が存在の値よりも大きくなる場合か、新しい変数の相互コストが影響する状態に限られる］。
【００７２】
他ホスト上に新しい変数が生成され、自ホスト上にある状態中の変数と新たに通信することになった場合の処理：
目標関数値が増大する場合には改めてｌｏｃａｌ＿ｍａｘあるいはｍｉｇｒａｔｅメッセージを送信する［これらは大きな値が優先権を持つため、今までの計算値の区別は不要。ただし、Ｒ（ｓ）は変化し得る（ホストが増える可能性あり）］。
【００７３】
隣接ホストｈiが増えたときの処理：
新たに追加された隣接ホストは自動的に集合Ｈiに追加される。この追加が確認できたら、ｈjへＹ0のうち有効な要素をｉｎｉｔメッセージにより送信する［これは実際にはＹ0の要素の送信であるが、メッセージ自体はその要素を設定することになった受信したｉｎｉｔメッセージと同じになり、ｈjにとっては元のｉｎｉｔメッセージを受け取るのと等価となる。Ｙ0の有効な要素数と同じ数のｉｎｉｔメッセージが送信される］。そして、Ｙ0に（ε，ｈj）を追加し、ＳかＳ′に含まれる状態ｘ0のｂｏｏｌｅａｎ変数をｆａｌｓｅにする。
【００７４】
タスク（変数ｘj）の故障または削除時の処理：
【００７５】
１．ｄｅｌｅｔｅ（｛ｘj｝）を全隣接ホストへ送信する。
【００７６】
２．ｘ0が実行可能であればｙ′＝ｙi（ｘ0，ｘ0）を再計算しその値がｘj削除前から変化していればｉｎｉｔ（ｙ′，ｉ）を全隣接ホストへ送信し、Ｙ0に含まれる自身の値も更新する。
【００７７】
３．ｘj削除前にｘ0が実行可能だったが、ｘj削除によりｘ0が実行不可能になった場合にはｉｎｉｔ（∞，ｉ）を全隣接ホストに送信し、Ｙ0に含まれる自身の値も更新する。
【００７８】
４．上記によりａ0が変化する場合には、ｉ＝ａ0でｙi（ｘ0，ｘ0）が減少することで他のホストが新たにｈa0となる場合と、ｉ≠ａ0でｙi（ｘ0，ｘ0）が増加してｙa0（ｘ0，ｘ0）を越えてしまうことでｈiが新たにｈa0となる場合の二通りがあるが、このうち前者の場合には、Ｓ，Ｓ′中の状態ｓのうち、Ｒ（ｓ）に新しいｈa0を含まない状態をｌｏｃａｌ＿ｉｍｐｒｏｖｅによってｈa0へ送信する。
【００７９】
５．Ｉ，Ｓ，Ｓ′，Ｓｂに含まれる状態のうち、ｘjを含む状態をすべて削除する。
【００８０】
６．Ｉ，Ｓ，Ｓ′，Ｓｂに残った状態のうち、ｘjとの相互コストがあった状態ｓに対し、ｂｏｏｌｅａｎ変数をｆａｌｓｅに変更し、ｈｘ0jがｘj以外の変数によってＲ（ｓ）に入らないのであればＲ（ｓ）からｈｘjを削除した［ｘjのみに関係するのか他とも関係するのかが不明なら削除できない］上で、Ｘd＝｛ｘj｝としてｌｏｃａｌ＿ｍａｘメッセージ、ｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージを用いて大域的な目的関数値を再計算する。具体的には、この時点ではｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），ｙ（ｓ），ｉ，｛ｘj｝）をＲ（ｓ）に含まれるホストへのルーティングに含まれる隣接ホストへ送信する。
【００８１】
７．Ｉ，Ｓ，Ｓ′，Ｓｂに残った状態のなかにｈiと無関係の状態があり、その目的関数値がｙ0iによって与えられている場合には、その目的関数値を更新する。その結果、暫定解がその状態に変わることもあり得るので、その場合には暫定解更新処理を行う。
【００８２】
８．暫定解ｘ*にｘjが含まれている場合には、ｘ*がＳから削除されてしまうので暫定値ｙが上昇する可能性がある。このとき、Ｓ中にｂｏｏｌｅａｎ変数がｔｒｕｅとなっている状態が他にあれば、それを暫定解に置き換える［Ｓ中にあるということはその目的関数値はｙに等しいはずなので置き換えだけで十分］。もしＳ中になければ、Ｓ′，Ｓb中でｂｏｏｌｅａｎ変数がｔｒｕｅとなっている状態のうち、最小の目的関数値を与える状態を暫定解に設定して暫定値も更新すると同時にその状態をＳへ移動させ、Ｓ′，Ｓbに含まれる状態のうち、ｙ以下の目的関数値を与える状態をＳへ移動させ、さらにＳｂに含まれる状態ｓのうち、ｙS（ｓ）がｙ以下の状態をＳ′へ移動させる。もし、Ｓ′，Ｓb中にｂｏｏｌｅａｎ変数がｔｒｕｅとなっている状態がひとつもなければｙ：＝∞，ｘ*：＝｛｝とし、Ｓ′，Ｓb中に含まれる状態すべてをＳへ移動させる。この結果、終端されていた状態が復活するので、更なる分枝が可能であれば分枝して必要に応じてｍｉｇｒａｔｅ，ｌｏｃａｌ＿ｍａｘメッセージを送信する。
【００８３】
９．これらの処理により暫定値が変化した場合には、ｕｐｄａｔｅ（ｙ，ｘ*，Ｒ（ｘ*），ｉ）メッセージを全隣接ホストへ送信する［ｄｅｌｅｔｅメッセージが先に送られているので、暫定値が上昇する更新であっても問題ない］。
【００８４】
１０．変数削除前はｉ＝ａ0で、変数削除語にａ0が変化した場合には、上記処理がすべて完了した後のＳ，Ｓ′中の状態ｓのうち、Ｒ（ｓ）に新しいｈa0を含まない状態をｌｏｃａｌ＿ｉｍｐｒｏｖｅによってｈa0へ送信する。
【００８５】
ホストｈiの故障または削除時の処理：
【００８６】
１．ｉｎｉｔ（-∞，ｉ）を全隣接ホストに送信する。
【００８７】
２．ｘ0においてｈiにある変数集合Ｖに対し、ｄｅｌｅｔｅ（Ｖ）を全隣接ホストへ送信する。
【００８８】
メッセージ受信により起動される処理：
【００８９】
１．隣接ホストｈ′からｉｎｉｔ（ｙ′，ａ′）を受信したとき：
（ｙ′，ｈａ′）∈Ｙ0ならばなにもしない。そうでなければ下記を実行する：まず（＊，ｈａ′）∈Ｙ0（”＊”は任意の値）ならば（＊，ｈａ′）をＹ0から削除する。そして（ｙ′，ｈａ′）をＹ0に追加し、受信メッセージをそのままｈ′以外の隣接ホストへ送信する。この操作により、（ε，＊）∈Ｙ0がなくなれば、ｙにＹ0中の要素（ｙ′，ｈａ′）のうちｙ′の最大値とｙの今までの値のうち小さい方を代入し、ｙ′の最大値をＳかＳ′に含まれる状態ｘ0の目的関数値とし、状態ｘ0のｂｏｏｌｅａｎ変数をｔｒｕｅにする。
【００９０】
ｙ′＝-∞はｈａ′が故障したことを意味するため、ｈａ′への割当のある状態［つまり、値がａ′となる変数を要素として含む状態］をＩ，Ｓ，Ｓ′，Ｓｂから削除する。そのような状態が暫定解となっていた場合には、下記の処理を行う：Ｓ中にｂｏｏｌｅａｎ変数がｔｒｕｅとなっている状態が他にあれば、それを暫定解に置き換える［Ｓ中にあるということはその目的関数値はｙに等しいはずなので置き換えだけで十分］。
【００９１】
もし、Ｓ中になければ、Ｓ′，Ｓｂ中でｂｏｏｌｅａｎ変数がｔｒｕｅとなっている状態のうち、最小の目的関数値を与える状態を暫定解に設定して暫定値も更新すると同時にその状態をＳへ移動させ、にＳ′，Ｓｂ含まれる状態のうち、ｙ以下の目的関数値を与える状態をＳへ移動させ、さらにＳｂに含まれる状態ｓのうち、ｙｓ（ｓ）がｙ以下の状態をＳ′へ移動させる。
【００９２】
もし、Ｓ′，Ｓｂ中にｂｏｏｌｅａｎ変数がｔｒｕｅとなっている状態がひとつもなければｙ：＝-∞，ｘ＊：＝｛｝とし、Ｓ′，Ｓｂに含まれる状態すべてをＳへ移動させる。この結果、終端されていた状態が復活するので、更なる分枝が可能であれば分枝して必要に応じてｍｉｇｒａｔｅ，ｌｏｃａｌ＿ｍａｘメッセージを送信する。そして、ｕｐｄａｔｅ（ｙ，ｘ＊，Ｒ（ｘ＊），ｉ）メッセージを全隣接ホストへ送信する。
【００９３】
この処理によって、目的関数値が変化する状態が存在するならその状態の目的関数値を更新する。この更新により、さらに下記の三つの場合のいずれかが起こり得るので、それぞれ処理する［ひとつも起こらない場合もある］：
【００９４】
（ａ）目的関数値が減少してそれが暫定値になる場合：
暫定値更新処理を行う。
【００９５】
（ｂ）暫定解の目的関数値が増大した場合：
暫定値ｙをその増大した目的関数値に設定し、Ｓ′，Ｓｂ中の状態で暫定値以下の目的関数値を持つ状態をＳへ移動させ、さらにＳｂ中の状態ｓでｙｓ（ｓ）以下の状態をＳ′へ移動させる［なお、ホストｈa0の初期状態における目的関数値が変化しただけではＳ中の状態が新しいｙを越えることはない。ただし、後からいくつかの状態に対して目的関数再計算が起こり、その結果、超えてしまう可能性はある。さらに、暫定値が変化してもこの場合は暫定解は不変なので、受信したｉｎｉｔメッセージの転送により他ホストでも同じような処理が行われて暫定値が更新されるので、ｕｐｄａｔｅメッセージによる暫定値更新処理は不要である］。
【００９６】
（ｃ）暫定解の目的関数値は不変だが、他の状態の目的関数値が増大した場合：
Ｓ中の状態のうち、その目的関数値がｙを越えたものをＳ′へ移動させる［初期状態の値の変化による終端なのでＳｂへの移動はあり得ない］。
【００９７】
さらに、ａ0が変化する場合［ａ′≠ａでｙａ′（ｘ0，ｘ0）が減少することで他のホストが新たにｈa0となる場合と、ａ′≠ａでｙａ′（ｘ0，ｘ0）が増加してｙａ′（ｘ0，ｘ0）を越えてしまうことで新たにｈa0となる場合の二通りある］には、Ｓ，Ｓ′中の状態ｓのうち、Ｒ（ｓ）に新しいｈa0を含まない状態をｌｏｃａｌ＿ｉｍｐｒｏｖｅによってｈa0へ送信する。
【００９８】
２．隣接ホストｈ′からｄｅｌｅｔｅ（Ｘ）を受信したとき：
ｈ′以外のホストでｍｉｇｒａｔｅメッセージによりＸに属する変数の移動を通知したホストに当該変数（複数可）の削除メッセージ（ｄｅｌｅｔｅ）を送る［通常はｄｅｌｅｔｅ（Ｘ）をそのまま転送するが、移動コストの増大などによりこのホスト以後の移動が起こらない変数については転送する必要がないのでＸから除外できる。しかし、除外しなくても動作上は何も影響がない］。その後、変数ｘjが削除されるときの処理の２以降の処理を行う。そして、Ｘに属する変数に関するｍｉｇｒａｔｅメッセージ受信記録を削除する。
【００９９】
３．隣接ホストｈ′から暫定解更新メッセージｕｐｄａｔｅ（ｙ′，ｓ，Ｒ（ｓ），ａ′）を受信したとき：
まず、Ｒ（ｓ）に含まれないホストの初期目的関数値の最大値ｙ″を調べ、それがｙ′を越えていたら、ｙ′：＝ｙ″とする［動的変化により目的関数値が変化する場合への対応］。その上で、ｓに送受信したｄｅｌｅｔｅメッセージにより削除された変数が含まれているか、あるいは、ｓにおいて相互コストで関係する変数が削除されたことによりｌｏｃａｌ＿ｍａｘ，ｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージによりその目的関数値の再計算が実行中である［すべての隣接ホストとの送受信記録にｌｏｃａｌ＿ｍａｘ＿ｆｉｘがあり、かつ、その目的関数値がｙ′である場合（完了している可能性あり）を除き、それらメッセージの受信記録が残っている］か、あるいは、ｙ≦ｙ′ならば何もしない。ｙ＞ｙ′ならば下記を実行する：
ｘ*＝ｓ，ｙ：＝ｙ′，ａ：＝ａ′とし、もし
【０１００】
【数３】
2006338289.tif 000005
ならばｓにその目的関数値ｙを付けてＳ：＝Ｓ∪｛ｓ｝としてからそのｂｏｏｌｅａｎ変数をｔｒｕｅにし、もし、ｓ∈ＳならばＳ中のｓの目的関数値をｙに、ｂｏｏｌｅａｎ変数をｔｒｕｅにし、暫定解更新メッセージｕｐｄａｔｅ（ｙ，ｘ＊，Ｒ（ｘ＊），ａ）をｈ′以外の隣接ホストへ送信する［受信したｙ′が修正されているときにはｈ′にも影響するが、ｉｎｉｔメッセージにより修正されるはずなので、ここで送る必要はない］。
【０１０１】
∀ｓ∈Ｓに対し、ｙ（ｓ）＞ｙであればＳ＼｛ｓ｝とする。その際、ｙs（ｓ）≦ｙならば、Ｓ′：＝Ｓ′∪｛ｓ｝とし、そうでなければ、Ｓb：＝Ｓb∪｛ｓ｝とする。また、ｙs（ｓ）＞ｙでｓが隣接ホストへの移動を含んでいれば、限定メッセージｂｏｕｎｄ（ｓ，ｉ）をその隣接ホストへ送信する。ただし、先に送信済の暫定解更新メッセージによって隣接ホストで限定されることが明らかな場合には、この限定メッセージは送信しない。∀ｓ′∈Ｓ′に対しても同様に、ｙs（ｓ′）＞ｙであればＳ′＼｛ｓ′｝，Ｓb：＝Ｓb∪｛ｓ′｝とし、ｓ′が隣接ホストへの移動を含んでいて暫定解更新メッセージにより限定されると明らかでない場合は、限定メッセージｂｏｕｎｄ（ｓ′，ｉ）をその隣接ホストへ送信する。
【０１０２】
さらに、限定された状態に対応するタスク移動メッセージの受信がある場合には、その受信記録を削除し、限定された状態ｓに対応するｌｏｃａｌ＿ｍａｘメッセージまたはｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージが存在してｙa0（ｓ）≠ｙa0（ｘ0）［ｈa0へのタスク割当、あるいは、それらタスクと通信する他ホストにあるタスクの割当が初期状態から変化している］のとき、そのｌｏｃａｌ＿ｍａｘメッセージを受信したという記録を削除する。対応するｌｏｃａｌ＿ｍａｘメッセージまたはｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージが存在するがｙa0（ｓ）＝ｙa0（ｘ0）のときには、ｓがＳ′から削除された場合（ｙs（ｓ）＞ｙ）にはその受信記録を削除する。
【０１０３】
４．タスク移動メッセージｍｉｇｒａｔｅ（ｘj，Ｒ（ｘj），ｓ，Ｒ（ｓ））を受信したとき：
ｚを状態ｓの要素ｘjをｘj＝ｉと変更した状態とし、Ｒ（ｚ）＝Ｒ（ｓ）∪Ｒ（ｘj）とする。まず、受信メッセージを記録する。ｙ（ｚ）＜ｙかつ
【０１０４】
【数４】
2006338289.tif 000006
であればＳ：＝Ｓ∪｛ｚ｝とする。ｓがＳ，Ｓ′，Ｉの状態との統合により新しい状態を構成することができるならばその状態を構成し、それぞれの状態に対して重複のないように本処理を繰り返す。ただし、統合が可能になるのは、
（ａ）統合後の状態が統合の基となった状態と矛盾しない（固定されている変数が変化しない）。
（ｂ）統合後の状態が過去に列挙され限定されていない（Ｓ′から削除済の状態の部分を含む）。
（ｃ）統合後の状態が複数の隣接ホストへの移動を含まない。つまり、移動を表す変数の値は同じ。
（ｄ）∃ｊ，ｘsj≠ｘx0jでｘsjが移動動しないならば、統合後の状態ｓ′は∀ｈ，ｘs′j≠ｘsj，ｘs′ｈ≠ｘsjを満たす必要がある。
【０１０５】
新たに生成された状態が隣接ホストへの移動を含んでいて、かつ、その状態が移動先において既に送信済の情報から生成できないならば、その状態をその移動先へタスク移動メッセージとして送信する。ｚを含め新しい状態がひとつも生成できなければ［生成した状態が全て終端されてしまったら］、限定メッセージｂｏｕｎｄ（ｓ，ｉ）をタスク移動メッセージを送信してきたホストへ送信し、その受信記録を削除する。次いで、すべての変数が固定された状態の目的関数値を確定させるためと、全列挙を可能にするため、下記の処理を行う。
（ａ）すべての変数ｘj∈ｓが固定され、過去にｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），＊，＊，＊）というメッセージ（“＊”は任意の値あるいは任意の集合）を受信していない場合（ｂｏｏｌｅａｎ変数はｆａｌｓｅのはず）：
ｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），ｙ（ｓ），ｉ，｛｝）メッセージをＦ（Ｒ（ｓ））に属するすべての隣接ホストへ送信する。もし、タスク移動メッセージも同時に同じ隣接ホストへ送信することになるなら、ｌｏｃａｌ＿ｍａｘメッセージを先にする。
（ｂ）ｌｏｃａｌ＿ｍａｘ（Ｓ，Ｒ（ｓ），ｙ′，ａ′，Ｘd）メッセージを受信した場合：
まずｙ″＞ｙ′となるｌｏｃａｌ＿ｍａｘ（Ｓ，Ｒ（ｓ），ｙ″，ａ″，Ｘd）メッセージを受信したことがなければ、受信メッセージを記録するが、この内容のメッセージを過去に受信したことがない場合には、初めての受信であることも合わせて記録する。
【０１０６】
ｙ″＞ｙ′となるｌｏｃａｌ＿ｍａｘ（Ｓ，Ｒ（ｓ），ｙ″，ａ″，Ｘd）メッセージを受信したことがある場合には、単に受信メッセージを削除するだけで、下記のいずれかの処理も行わない。ただし、Ｘdの内容が過去に受信したメッセージｌｏｃａｌ＿ｍａｘ（Ｓ′，Ｒ′（ｓ′），ｙ″，ａ″，Ｘ′d）の内容と違う（つまりＸd≠Ｘ′d）の場合には、Ｓ中に存在するｓのｂｏｏｌｅａｎ変数がｔｒｕｅでなければＸ′d⊂Ｘdである場合のみ、受信メッセージが有効になり、過去の同メッセージの記録をすべて削除する。なお、Ｓ中に存在するｓのｂｏｏｌｅａｎ変数がｔｒｕｅの場合にはＸdの内容を気にする必要はなく、内容がＸ′dと異なる場合には過去の同メッセージの記録をすべて削除し、Ｓ中に存在するｓのｂｏｏｌｅａｎ変数をｆａｌｓｅに設定する。Ｘd⊂Ｘ′dの場合には単純に受信メッセージを記録を含めて削除し、後は何もしない。そうではなく、さらにＸ′d⊆Ｘdでもない場合には、ｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），ｙ（ｓ），ｉ，Ｘd∪Ｘ′d）メッセージをＦ（Ｒ（ｓ））に属するすべての隣接ホストへ送信し、この受信メッセージを含めて今までに受信したすべてのｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），＊，＊，＊）メッセージの記録を削除し、以下の処理は行わない。一方、ｓ＝ｓ′かつＸd＝Ｘ′dにも関わらずＲ（ｓ）≠Ｒ′（ｓ′）の場合には、Ｒ（ｓ）の要素数の多い方を残し後は削除する［ｓに含まれる変数が通信する変数が動的変化により増えた場合に起こるので、Ｒ（ｓ）⊂Ｒ′（ｓ′）かＲ′（ｓ′）⊂Ｒ（ｓ）のいずれかが成り立つ］。この結果受信メッセージが残る場合に限り下記の処理を行う。
【０１０７】
ｙ″＜ｙ′を満たすｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ，Ｒ（ｓ），ｙ″，ａ″，Ｘd）メッセージを送受信した記録があれば、その記録を削除する。
（ｘj＝ｉかつｘ0j≠ｉ）または（ｘj≠ｉかつｘ0j＝ｉ）またはｇi（ｓ）≠ｇi（ｘ0）となるｘj∈ｓが存在して、ｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），ｙ（ｓ），ｉ，Ｘd）メッセージを送信したことがなく、ｙ（ｓ）≦ｙで、ｙ（ｓ）＞ｙ′かｙ（ｓ）＝ｙ′かつａ′＞ｉであれば、下記を実行する。
【０１０８】
ｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），ｙ（ｓ），ｉ，Ｘd）メッセージをＦ（Ｒ（ｓ））に属するすべての隣接ホストへ送信し、ｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），＊，＊，＊）の受信記録を削除する。
［数３］
かつ
【０１０９】
【数５】
2006338289.tif 000007
であれば、ｓをＳかＳ′のうち適切な方へ加え、ｚ＝ｓとなるタスク移動メッセージを受信したときと同じ処理を行う。ただし、それより起こるタスク移動メッセージの送信は行わない。
【０１１０】
（ｘj＝ｉかつｘ0j≠ｉ）または（ｘj≠ｉかつｘ0j＝ｉ）またはｇi（ｓ）≠ｇi（ｘ0）となるｘj∈ｓが存在して、この内容のメッセージの受信が初めてで、ｙ（Ｓ）＜ｙ′≦ｙで、ｄi≧２であれば、受信メッセージｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），ｙ′，ａ′，Ｘd）をそれを送信してきたホストを除くＦ（Ｒ（ｓ））に属するすべての隣接ホストへ送信する。
【０１１１】
∀ｊ，ｘj∈ｓに対して（ｘj≠ｉかつｘ0j≠ｉまたはｘj＝ｘ0j＝ｉ）でｇi（ｓ）＝ｇi（ｘ0）となり、この内容のメッセージの受信が初めてで、ｙ′≦ｙで、ｄi＞２であれば、受信メッセージｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），ｙ′，ａ′，Ｘd）をそれを送信してきたホストを除くＦ（Ｒ（ｓ））に属するすべての隣接ホストへ送信する。
【０１１２】
上記の三つの処理がいずれも条件が合わずにメッセージ送信が実行されず、この受信によりこの内容のメッセージをすべての隣接ホストから受信したことになり、ａ′≠ｉであれば、ｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ，Ｒ（ｓ），ｙ′，ａ′，Ｘd）メッセージをＦ（Ｒ（ｓ））に属するすべての隣接ホストに送信し、ｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），＊，＊，＊）の受信記録を削除し、送信したｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージの記録を取る。
【０１１３】
∀ｊ，ｘj∈ｓに対して（ｘj≠ｉかつｘ0j≠ｉまたはｘj＝ｘ0j＝ｉ）でｇi（ｓ）＝ｇi（ｘ0）となり、ｙ′≦ｙで、［数３］かつ［数５］ならば、ｓをｙ（ｓ）≦ｙのときにはＳへ、ｙ（ｓ）＞ｙのときにはＳ′へ加え、ｚ＝ｓとなるタスク移動メッセージを受信したときと同じ処理を行う。ただし、それにより起こるタスク移動メッセージの送信は行わない。
【０１１４】
ｙ′＞ｙであるか（ｘj＝ｉかつｘ0j≠ｉ）あるいは（ｘj≠ｉかつｘ0j＝ｉ）あるいはｇi（ｓ）≠ｇi（ｘ0）となるｘj∈Ｓが存在してｙ（ｓ）＞であれば、限定メッセージｂｏｕｎｄ（ｓ，ｉ）をすべての隣接ホストへ送信し、受信したｌｏｃａｌ＿ｍａｘの受信記録を削除する。
（ｃ）ｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ，Ｒ（ｓ），ｙ′，ａ′，Ｘd）メッセージを受信した場合：
受信記録されているｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ′，Ｒ′（ｓ′），ｙ″，ａ″，Ｘ′d）あるいはｌｏｃａｌ＿ｍａｘ（ｓ′，Ｒ′（ｓ′），ｙ″，ａ″，Ｘ′d）が存在し、Ｘd≠Ｘ′dあるいはＲ（ｓ）≠Ｒ′（ｓ′）であれば受信メッセージを削除し、何もしない［ｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージは必ず同じ内容のｌｏｃａｌ＿ｍａｘメッセージが必要なので、包含関係を調べる必要はなく単に同一かどうかだけで判断される。つまり、より優先度の高い（Ｘ′d⊂ＸdかＲ′（ｓ′）⊂Ｒ（ｓ）となる）メッセージを受信することはあり得ない］。
【０１１５】
まず受信メッセージを記録する。ａ′≠ｉかつｙ≧ｙ′＞ｙ（ｓ）で、ｙ″＞ｙ′となるｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ，Ｒ（ｓ），ｙ″，ａ″，Ｘd）メッセージかｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），ｙ″，ａ″，Ｘd）メッセージを受信したことがなければ、下記を実行する。
【０１１６】
この時点で｜Ｆ（Ｒ（ｓ））｜−１個の隣接ホストから同じメッセージを受信またはそのホストへ送信していれば、ｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ，Ｒ（ｓ），ｙ′，ａ′，Ｘd）メッセージを唯一このメッセージを送信してきていないＦ（Ｒ（ｓ））に属する隣接ホストへ送信して送信を記録する。そうでなく、これが最初の受信であれば、ｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），ｙ′，ａ′，Ｘd）を相互に送信し合ったＦ（Ｒ（ｓ））に属する隣接ホスト（実際には、最初にｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），ｙ′，ａ′，Ｘd）を送ってきたＦ（Ｒ（ｓ））に属する隣接ホスト以外の隣接ホストのうち、ｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），ｙ′，ａ′，Ｘd）の受信記録があるホスト）へｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ，Ｒ（ｓ），ｙ′，ａ′，Ｘd）メッセージを送信し、その送信を記録すると同時にｌｏｃａｌ＿ｍａｘ（ｓ，Ｒ（ｓ），ｙ′，ａ′，Ｘd）の受信記録を削除する。
【０１１７】
ａ′＝ｉ（ｙ′＝ｙ（ｓ）のはず）、ｙ′≦ｙ、ｇa0（ｓ）＝ｇa0（ｘ0）  で、このメッセージをＦ（Ｒ（ｓ））に属するすべての隣接ホストから受信していて、∀ｊ，ｘj∈ｓに対して（ｘj＝ａ0かつｘ0j＝ａ0）または（ｘj≠ａ0かつｘ0j≠ａ0）となり、さらに、Ｒ（ｓ）に属するホストの初期状態における目的関数値の最大値よりもｙ′の方が小さければ、ｌｏｃａｌ＿ｉｍｐｒｏｖｅ（ｓ，ｙ（ｓ））メッセージをｈa0に向けて送信［実際にはｈa0方向の隣接ホスト、つまり、Ｆ（｛ｈa0｝）に属する唯一のホストへ送信］し、対応するｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージの送受信記録を削除する。さらに、ＳまたはＳ′中に存在するこの状態ｓのｂｏｏｌｅａｎ変数をｔｒｕｅにする。
【０１１８】
ａ′＝ｉ（ｙ′＝ｙ（ｓ）のはず）、ｙ（ｓ）＜ｙでこのメッセージをＦ（Ｒ（ｓ））に属する全ての隣接ホストから受信していて、かつ、ｇa0（ｓ）≠ｇa0（ｘ0）となるあるいは（ｘj＝ａ0かつｘ0j≠ａ0）または（ｘj≠ａ0かつｘj0＝ａ0）となるｘj∈ｓが存在するならば、Ｒ（ｓ）に属さないホスト（つまりＨ＼Ｒ（ｓ）に属するホスト）の初期状態における目的関数値の最大値をｙ′′′として、下記を実行する。ｙ（ｓ）＜ｙ′′′かつｙ′′′＞ｙならば、Ｓ中のｓのｂｏｏｌｅａｎ変数をｔｒｕｅにした上で、Ｓからｓを削除してＳ′に挿入し、必要に応じてｂｏｕｎｄメッセージを用いてｓが終端されたことを隣接ホストへ通知する。ｙ（ｓ）＜ｙ′′′かつｙ′′′＜ｙならばｙ：＝ｙ′′′，ｙ′＞ｙ′′′ならばｙ：＝ｙ（ｓ）として、どちらの場合においても、Ｓ中のｓのｂｏｏｌｅａｎ変数をｔｒｕｅにした上で、暫定解更新メッセージｕｐｄａｔｅ（ｙ（ｓ），ｉ）を全ての隣接ホストへ送信し、ｕｐｄａｔｅ（ｙ（ｓ），ｉ）を受信したときと同じ処理（ｕｐｄａｔｅの転送処理を除く）をしてから、対応するｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージの送受信記録を削除する。
【０１１９】
ａ′＝ｉでこのメッセージをまだすべての隣接ホストから受信し終わっていないなら、受信メッセージの記録のみを行う。
【０１２０】
ｙ′＞ｙであるか、あるいは、ｙ（ｓ）＞ｙで（ｘj＝ｉかつｘ0j≠ｉ）あるいは（ｘj≠ｉかつｘ0j＝ｉ）あるいはｇi（ｓ）≠ｇi（ｘ0））となるｘj∈ｓが存在するならば、ｂｏｕｎｄ（ｓ，ｉ）メッセージを、この限定メッセージを送受信したことがない場合に限りすべての隣接ホストへ送信し、対応するｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージの送受信記録を削除する。
（ｄ）ｌｏｃａｌ＿ｉｍｐｒｏｖｅ（ｓ，ｙ′）メッセージを受信した場合：
ｉ≠ａ0かつｙ′≦ｙならばこのメッセージは単にｈa0へ中継されるが、もしｓがＳまたはＳ′に含まれていなければｓを適切な方に追加してタスク移動メッセージを受信してｓが生成されたときと同じ処理を行う。ただし、このメッセージに対応するｌｏｃａｌ＿ｍａｘを受信していたのであれば中継以外には何もすることはないはずである。ｉ＝ａ0かつｙ′≦ｙならば、下記を実行する：
ｙ（ｓ）≦ｙならばｓ（ｂｏｏｌｅａｎ変数はｔｒｕｅ）をＳに加える。そうでなく、かつ、ｙ（ｓ）＝ｙ0＞ｙ≧ｙ′ならば、ｓをＳ′に加える。そして、タスク移動メッセージを受信してｓが生成されたときと同じ処理を行う［ただし、このメッセージに対応するｌｏｃａｌ＿ｍａｘを受信していたのであればｂｏｏｌｅａｎ変数の設定以外に何もすることはないはずである］。
【０１２１】
一方、ｙ′＞ｙであればｂｏｕｎｄ（ｓ，ｉ）メッセージを、この限定メッセージを送受信したことがない限り、すべての隣接ホストへ送信する。
【０１２２】
５．限定メッセージｂｏｕｎｄ（ｓ，ｉ′）を受信した場合：
まず、ｓが移動（ｈiへの移動のみ含みうる）を含んでいなければ、その限定メッセージを記録する。そして、これが状態ｓを限定する最初のメッセージ受信であれば、ｓ∈Ｓまたはｓ∈Ｉならば、その集合からｓを削除してＳbへ追加する。さらに、ｓを基にして生成された状態ｓ′があればそれもＳbへ移動する。
【０１２３】
これら削除（Ｓbへ移動）された状態が隣接ホストにある状態に影響するなら、限定メッセージをそのホストへ送信する。実際にはこの判断は難しいので下記のようにする：ｉ≠ｉ′でこれがこの限定メッセージの最初の受信であり、ｓがｈiから他のホストへの移動を含まないならば、受信した限定メッセージを、それを送信してきたホストを除くすべての隣接ホストへ転送する。そして、同じ限定メッセージをすべての隣接ホストから受信したら、その記録を削除できる（アルゴリズムの記述終了）。
【０１２４】
上記アルゴリズムは、アルゴリズムによって生じるすべてのメッセージがシステム中で送信されなくなった場合に解が求まる。その解は、ホストｈaで負荷量ｙの状態である。ただし、その後、動的変化が生じればまた新たな最適解に向かって動作し始める。実際にこの負荷量を実現するためには、この状態を関係するすべてのホストが認知して、それに従ってタスクを移動させればよい。このアルゴリズムの停止状態を検出するひとつの方法はスナップショットを取ることであるが、それ以外に、システム中の状態を確認するメッセージ（ＯｐｔＦｌｏｏｄＭａｘの拡張）を送信して、その確認メッセージ以外のメッセージがシステム中にないことをもって終了と判定する方法もある。
【０１２５】
このアルゴリズムは、逐次環境における分枝限定法と同様に、途中で止めた場合には近似解法として使うことができる。また、他の近似解法の結果得られた状態とそのときの負荷量とを使って、暫定解更新メッセージを作り出し、さらに、その状態を関連ホストに通知することによって、本アルゴリズムの効率化に有効に利用できる。
【０１２６】
（状況毎の動作例）
ここではある程度具体的な実行例を挙げて本アルゴリズムを説明する。ただし、先願のタスク分散決定方法に該当する機能については説明を省略する。また、説明を分かりやすくするために、実際の状況ではなく説明用に意図的に作成した状況での挙動で説明を行う。ここで示すのは、
１．ホストが追加されたときの追加されたホストの処理の例
２．変数が追加されたときのその変数が追加されたホストの処理の例
３．変数が故障したか削除されたときのその変数を持つホストの処理の例
４．ｉｎｉｔメッセージ受信時の処理の例（二例）
５．ｄｅｌｅｔｅメッセージ受信時の処理の例
である。故障や動的変化には、上記以外にさらに三つの場合がある。ホストが故障したか削除される場合、他のホストに新しい変数が追加され、その変数との通信が追加される場合、そして、隣接ホストが追加される場合、である。第一の場合は、そのときのホストの処理はアルゴリズムで示した内容で十分なためここでは実行例は示さない。第二の場合は、そのときの処理はアルゴリズムで示したように必要に応じてｌｏｃａｌ＿ｍａｘメッセージを使って目的関数値を再計算する［つまり、同メッセージを送信する］ことだけであり、例を示すまでもないため、ここでは示さない。第三の場合もｉｎｉｔメッセージを送信して一部の内部変数を処理するだけであり例を示すまでもないため、ここでは示さない。
【０１２７】
ホストの内部状態の変化は、通常、記録している送受信メッセージ、内部変数（ｙ，ａ，Ｉ，Ｓ，Ｓ′，Ｓb）の変化がわかればよく、それ以外は起こった動的変化または受信したメッセージと、処理の結果送信されるメッセージがわかれば処理の内容は理解できるが、これらのうち、記録している送受信メッセージについては動的変化に関しては重要ではないため、記録している送受信メッセージを除く上記の情報のみを提示し、必要に応じて説明を加える。
【０１２８】
以下ではホストｈ1での動作で説明する。ここで使用するホストｈ1は、次数ｄ1が２（隣接ホスト数２）で、具体的には２台のホストｈ2、ｈ3に隣接していて、さらに初期状態において、タスクτ1のみ保持している（ｘ01＝１，∀j≠１，ｘ0j≠１）。また、ここでは計算の詳細は省き、動作のみを理解できるようにするための仮想的な値を用いる。具体的には、実際よりも状態数（特にＳの要素数）を極端に減らして分かりやすくすると共に、各詳細の数値（ｐi，ｗj，ｃｉj，ｑij，ｂj）を使った計算は明示的には行わず、その計算の結果起こる操作に都合がよいように計算結果を与えることで分かりやすくする。
【０１２９】
さらに、過去に故障や動的な変化が起きていないことと、既に起動時に各ホストから送信されるｉｎｉｔメッセージはすべてのホストが受信済であることを仮定する。そして、いずれの場合も受信メッセージはｈ2から送られてきたとする。なお、以下の各例の間の関連性はない［つまり、同一の実行例からの抜粋ではない］ので注意。例を示す前に、下記の例で使用する記法を説明する。
【０１３０】
｛ｘ1＝１，ｘ2＝３｝（Ｔ，３０００）：状態とｂｏｏｌｅａｎ変数値（Ｔ（ｔｒｕｅ）かＦ（ｆａｌｓｅ））およびその状態による目的関数値の下限、Ｓの要素などに使われる。この例の場合にはｘ1＝１，ｘ2＝３以外は未固定、つまり、初期状態の割当をそのまま継承しており、そのときの目的関数値は現在分かっている限りでは３０００を下回ることなく、ｌｏｃａｌ＿ｍａｘ，ｌｏｃａｌ＿ｍａｘ＿ｆｉｘによって既にこの状態の目的関数値を確定している。ということを表している。
【０１３１】
ｘ1＝２s：この状態をｈ1が持つならば、タスクτ1がｈ1からｈ2の方向へ移動されることを表す。初期状態から値が変更されるが、その変更の方向を規定していることになる。具体的なホストは未設定であり、目的関数値の下界の計算では仮にｘ1＝２として計算する。
送信メッセージ：送信メッセージはメッセージを送信側に“，”で区切って列挙することで表す。実際には、そのリンクに前に送信されたメッセージがたまっていることがあるので、実際のリンク上にはここで記されたメッセージ以前にも存在する可能性もある。
【０１３２】
以下で先に述べた五つの場合の実行例を示す。
１．ホストｈ1が追加されたときの追加されたホストｈ1の処理の例：
このホストにとっては、アルゴリズムの起動直後の処理と、アルゴリズムの実行中にこのホストが追加された場合の処理との区別がない。ここでは変数ｘ1を持つホストｈ1が追加される場合のｈ1における処理を示す。
【０１３３】
【数６】
2006338289.tif 000008
２．変数ｘ3が追加されたときのその変数ｘ3が追加されたホストｈ1の処理の例：
【０１３４】
【数７】
2006338289.tif 000009
３．変数ｘ1が故障したか削除されたときのその変数ｘ1を持つホストｈ1の処理の例：
【０１３５】
【数８】
2006338289.tif 000010
４．ｉｎｉｔメッセージ受信時の処理の例：
【０１３６】
【数９】
2006338289.tif 000011
【０１３７】
【数１０】
2006338289.tif 000012
５．ｄｅｌｅｔｅ（｛ｘ2｝）メッセージ受信時の処理の例：
【０１３８】
【数１１】
2006338289.tif 000013
【産業上の利用可能性】
【０１３９】
本発明により、環境の動的変化が頻繁に発生するような大規模システムにおける負荷分散処理を効率良く行うことができる。
【図面の簡単な説明】
【０１４０】
【図１】本実施例のタスク分散処理装置のブロック構成図。
【図２】本実施例の情報処理方法の手順を示すフローチャート。
【符号の説明】
【０１４１】
１  動的変化通信部
２  動的変化検出部
３  動的変化対応処理部
４  削除情報蓄積部
５  タスク分散決定方法実行部
６  記憶領域
【図１】
2006338289.tif 000014
【図２】
2006338289.tif 000015