(57)【要約】【課題】  非同期完全分散環境において全情報を単一サーバに集約させず、かつ、システムを制御する唯一の存在もない状況において、最適解を求める。【解決手段】  ホスト毎にその時点で持っている情報だけを用いて可能なタスク割当の状態の列挙を並列に実行し、タスク等の隣接ホストへの移動に相当する状態については該当隣接ホストへ通知し、通知を受け取ったホストはそれを基に新たなタスク割当の状態の列挙を繰り返し、さらに全列挙のために必要な通信を行うことにより、分散的に厳密な解を求める分散分岐限定法を用いて情報または制御を単一のホストに集約することなく、分散的に最適な負荷分散を実現する。【選択図】  図１
2006185361.tif 000002
【特許請求の範囲】
【請求項１】
２以上のサーバを有し、複数のタスクを前記２以上のサーバに分散させて実行する情報処理システムであって、
前記情報処理システムを構成するそれぞれのサーバは、
当該サーバで実行するタスクを識別するタスク識別子を格納しているタスク識別子格納部と、
前記タスク識別子格納部に格納されているタスク識別子に対応付けられた情報であり、かつ前記タスク識別子で識別されるタスクを実行する際の負荷を示す情報であるタスク負荷情報または当該サーバの処理性能を示す処理性能情報を格納しているＣＰＵ負荷情報格納部と、
当該サーバと他のサーバ間の通信の負荷に関する情報である通信負荷情報または前記タスク識別子格納部に格納されているタスク識別子で識別されるタスクと、他のサーバに格納されているタスク識別子で識別されるタスクとの間の通信量に関する情報であるタスク間通信負荷情報とを格納している通信負荷情報格納部と、
前記タスク負荷情報または前記処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出するＣＰＵ負荷算出部と、
前記通信負荷情報または前記タスク間通信量情報に基づいて通信負荷に関する情報である通信負荷情報を算出する通信負荷算出部と、
前記ＣＰＵ負荷算出部が算出したＣＰＵ負荷情報および前記通信負荷算出部が算出した通信負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出する総合負荷情報算出部と、
前記タスク識別子格納部に格納されているタスク識別子を有する情報であり、
複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、
前記総合負荷情算報出部が算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信するタスク実行負荷情報送信部と、
１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信するタスク実行負荷情報受信部と、
前記タスク実行負荷情報受信部が受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記総合負荷情算出部が算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得するタスク実行負荷情報取得部と、
タスク実行負荷情報が既に蓄積されていない場合には、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積するタスク実行負荷情報蓄積部と、
前記タスク識別子格納部に格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信するタスク移動情報送信部と
を備えたことを特徴とする情報処理システム。
【請求項２】
２以上のサーバを有し、複数のタスクを前記２以上のサーバに分散させて実行する情報処理システムであって、
前記情報処理システムを構成するそれぞれのサーバは、
当該サーバで実行するタスクを識別するタスク識別子を格納しているタスク識別子格納部と、
前記タスク識別子格納部に格納されているタスク識別子に対応付けられた情報であり、かつ前記タスク識別子で識別されるタスクを実行する際の負荷を示す情報であるタスク負荷情報または当該サーバの処理性能を示す処理性能情報を格納しているＣＰＵ負荷情報格納部と、
前記タスク識別子格納部に格納されているタスク識別子で識別されるタスクのプログラムのサイズに関する情報であるサイズ情報を格納しているプログラムサイズ情報格納部と、
前記タスク負荷情報または前記処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出するＣＰＵ負荷算出部と、
前記サイズ情報に基づいてタスクが移動する場合の負荷に関する情報である移動負荷情報を算出する移動負荷算出部と、
前記ＣＰＵ負荷算出部が算出したＣＰＵ負荷情報および前記移動負荷算出部が算出した移動負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出する総合負荷情報算出部と、
前記タスク識別子格納部に格納されているタスク識別子を有する情報であり、
複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、
前記総合負荷情算報出部が算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信するタスク実行負荷情報送信部と、
１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信するタスク実行負荷情報受信部と、
前記タスク実行負荷情報受信部が受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記総合負荷情算出部が算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得するタスク実行負荷情報取得部と、
タスク実行負荷情報が既に蓄積されていない場合には、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積するタスク実行負荷情報蓄積部と、
前記タスク識別子格納部に格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信するタスク移動情報送信部と
を備えたことを特徴とする情報処理システム。
【請求項３】
２以上のサーバを有し、複数のタスクを前記２以上のサーバに分散させて実行する情報処理システムであって、
前記情報処理システムを構成するそれぞれのサーバは、
当該サーバで実行するタスクを識別するタスク識別子を格納しているタスク識別子格納部と、
前記タスク識別子格納部に格納されているタスク識別子に対応付けられた情報であり、かつ前記タスク識別子で識別されるタスクを実行する際の負荷を示す情報であるタスク負荷情報または当該サーバの処理性能を示す処理性能情報を格納しているＣＰＵ負荷情報格納部と、
当該サーバと他のサーバ間の通信の負荷に関する情報である通信負荷情報または前記タスク識別子格納部に格納されているタスク識別子で識別されるタスクと、他のサーバに格納されているタスク識別子で識別されるタスクとの間の通信量に関する情報であるタスク間通信負荷情報とを格納している通信負荷情報格納部と、
前記タスク識別子格納部に格納されているタスク識別子で識別されるタスクのプログラムのサイズに関する情報であるサイズ情報を格納しているプログラムサイズ情報格納部と、
前記タスク負荷情報または前記処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出するＣＰＵ負荷算出部と、
前記通信負荷情報または前記タスク間通信負荷情報に基づいて通信負荷に関する情報である通信負荷情報を算出する通信負荷算出部と、
前記サイズ情報に基づいてタスクが移動する場合の負荷に関する情報である移動負荷情報を算出する移動負荷算出部と、
前記ＣＰＵ負荷算出部が算出したＣＰＵ負荷情報および前記通信負荷算出部が算出した通信負荷情報および前記移動負荷算出部が算出した移動負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出する総合負荷情報算出部と、
前記タスク識別子格納部に格納されているタスク識別子を有する情報であり、
複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、
前記総合負荷情算報出部が算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信するタスク実行負荷情報送信部と、
１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信するタスク実行負荷情報受信部と、
前記タスク実行負荷情報受信部が受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記総合負荷情算出部が算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得するタスク実行負荷情報取得部と、
タスク実行負荷情報が既に蓄積されていない場合には、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積するタスク実行負荷情報蓄積部と、
前記タスク識別子格納部に格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信するタスク移動情報送信部と
を備えたことを特徴とする情報処理システム。
【請求項４】
前記総合負荷情報算出部は、当該サーバが保持しているタスク負荷情報または処理性能情報またはタスク間通信負荷情報またはサイズ情報および前記タスク実行負荷情報受信部が受信したタスク実行負荷情報に基づいて、当該サーバの負荷を示す情報である中間負荷情報を算出し、当該中間負荷情報が示す負荷が蓄積した最大総合負荷情報が示す負荷を超えるか否かを判断する中間判断手段を備え、
前記中間判断手段は、中間負荷情報の示す負荷が蓄積した最大総合負荷情報が示す負荷を超えると判断した場合に、当該タスク実行負荷情報が有するタスク実行情報と所定の関係を満たすタスク実行情報における総合負荷情報の算出を禁止する手段を備えた
請求項１ないし３のいずれか記載の情報処理システム。
【請求項５】
前記総合負荷情報算出部は、当該サーバが保持しているタスク負荷情報または処理性能情報またはタスク間通信負荷情報またはサイズ情報および前記タスク実行負荷情報受信部が受信したタスク実行負荷情報に基づいて、当該サーバの負荷を示す情報である中間負荷情報を算出し、当該中間負荷情報が示す負荷が蓄積した最大総合負荷情報が示す負荷を超えるか否かを判断する中間判断手段を備え、
前記情報処理システムを構成するそれぞれのサーバは、前記中間判断手段が中間負荷情報の示す負荷が蓄積した最大総合負荷情報が示す負荷を超えると判断した場合に、当該タスク実行負荷情報が有するタスク実行情報を有する情報であり、総合負荷情報の算出が不要である旨を示す情報である評価不要情報を、他の１以上のサーバに送信する評価不要情報送信部と、
他の１以上のサーバから評価不要情報を受信する評価不要情報受信部と
をさらに備え、
前記総合負荷情報算出部は、前記評価不要情報受信部が受信した評価不要情報が有するタスク実行情報と所定の関係を満たすタスク実行情報における総合負荷情報の算出は禁止する手段を備えた
請求項１ないし４のいずれか記載の情報処理システム。
【請求項６】
前記情報処理システムを構成するそれぞれのサーバにおいて、
前記タスク実行負荷情報送信部は、前記タスク実行負荷情報蓄積部が、タスク実行負荷情報が既に蓄積されており、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さいために当該タスク実行負荷情報を蓄積した場合に、当該蓄積したタスク実行負荷情報を送信する手段を備えた
請求項１ないし請求項５のいずれか記載の情報処理システム。
【請求項７】
汎用のコンピュータ装置にインストールすることにより、その汎用のコンピュータ装置に、請求項１ないし６のいずれかに記載の情報処理システムにおけるサーバに相応する機能を実現させるプログラム。
【請求項８】
複数のタスクを２以上のサーバに分散させて実行するタスク分散処理方法であって、
前記２以上のサーバにおいて、独自に、タスク負荷情報または処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出し、
通信負荷情報またはタスク間通信負荷情報に基づいて通信負荷に関する情報である通信負荷情報を算出し、
前記ＣＰＵ負荷情報および前記通信負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出し、
格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、前記算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信し、
１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信し、
前記受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、
前記算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得し、
タスク実行負荷情報が既に蓄積されていない場合には、前記取得したタスク実行負荷情報タスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積し、
前記格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信し、
かつ、所定の終了条件を満たした際に、１以上のサーバに蓄積されているタスク実行負荷情報が有するタスク実行情報に基づいて、２以上のサーバで複数のタスクを実行する
ことを特徴とするタスク分散処理方法。
【請求項９】
複数のタスクを２以上のサーバに分散させて実行するタスク分散処理方法であって、  
前記２以上のサーバにおいて、独自に、格納されているタスク負荷情報または格納されている処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出し、
格納されているサイズ情報に基づいてタスクが移動する場合の負荷に関する情報である移動負荷情報を算出し、
前記ＣＰＵ負荷情報および前記移動負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出し、
格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、前記総合負荷情算報出部が算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信し、
１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信し、
前記受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得し、
タスク実行負荷情報が既に蓄積されていない場合には、前記取得したタスク実行負荷情報タスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積し、
格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信し、
かつ、所定の終了条件を満たした際に、１以上のサーバに蓄積されているタスク実行負荷情報が有するタスク実行情報に基づいて、２以上のサーバで複数のタスクを実行する
ことを特徴とするタスク分散処理方法。
【請求項１０】
複数のタスクを２以上のサーバに分散させて実行するタスク分散処理方法であって、
前記２以上のサーバにおいて、独自に、格納されているタスク負荷情報または格納されている処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出し、
格納されている通信負荷情報または格納されているタスク間通信負荷情報に基づいて通信負荷に関する情報である通信負荷情報を算出し、
格納されているサイズ情報に基づいてタスクが移動する場合の負荷に関する情報である移動負荷情報を算出し、
前記ＣＰＵ負荷情報および前記通信負荷情報および前記移動負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出し、
格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、前記総合負荷情算報出ステップで算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信し、
１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信し、
前記受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、
前記し算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得し、
タスク実行負荷情報が既に蓄積されていない場合には、前記取得したタスク実行負荷情報タスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積し、
格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信し、
かつ、所定の終了条件を満たした際に、１以上のサーバに蓄積されているタスク実行負荷情報が有するタスク実行情報に基づいて、２以上のサーバで複数のタスクを実行する
ことを特徴とするタスク分散処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット等の分散システムにおけるタスク割当、および、資源割当に関する。なお、並列システムは分散システムの一種であるため、本発明は並列システムでも分散システムでも使えるが、それぞれのシステムにおいては用語が異なるため、以下では並列システムにおけるプロセッサ、ＣＰＵ、分散システムにおけるエージェント、プロセス、計算機、サーバ、情報処理装置等の用語を一括してサーバと呼ぶ。
【０００２】
なお、厳密にはサーバとプロセスまたはプロセッサは異なるが、本発明の範囲では区別の必要がないためサーバと呼んで差し支えない。また、タスクとしてエージェントやプロセスを扱うことがあるため、上記エージェントおよびプロセスはサーバとして扱われる場合とタスクとして扱われる場合とがある。
【背景技術】
【０００３】
タスク割当・負荷分散手法は従来から数多く存在し、その実施方法も集中的な手法から分散的な手法までさまざまである。ここでは、非同期完全分散環境において、大域的に最適な負荷分散を実現する負荷分散を考えるが、従来はこのような非同期完全分散環境で分散的に最適解を求める手法は存在しない。なお、ここでの最適解とは、負荷量最大のサーバの負荷量を最小化することであり、別の意味での最適化ならば従来法に存在する。
【０００４】
従来の分散環境における動的なタスク割当、いわゆる負荷分散は基本的に、マルチキャストを利用して他サーバの負荷量を収集し、各サーバが他のサーバと一対一で交渉してタスクを移動させることにより、局所的に負荷を均衡化させ、それを各サーバが自律的に繰り返すことで大域的な負荷の均衡化を実現しようというものである（例えば、非特許文献１参照）。
【０００５】
このような手法は基本的に近似解法のひとつである局所探索法の分散版とみなせる。つまり、一対一交渉である限りは最適解が求まる保証はない。この交渉を一対一でなく、局所探索法の、λ−ｏｐｔ近傍（例えば、非特許文献２参照）と同様に全サーバの協調にまで拡張できれば最適解に収束するが、従来の分散手法にはそのような協調を行う手法は存在しない。
【０００６】
一方、局所的な均衡化でなく、最初から大域的な均衡化を目指す手法も存在する。それが、特許文献１、特許文献２、特許文献３において述べられている。これらは大域的な最適化を目指した動的かつ分散的な手法であるが、基本的に新たに到着したタスクの割当先を決める手法であり、現在割当済のタスクも移動対象にしての最適化はできないし、最適化の指標も違う。
【０００７】
これらとは別に、負荷分散を対象としていないものの、負荷分散を最適化問題として捉えて整数計画法で解くことが考えられる。整数計画法を解く分散手法としては、分枝限定法を分散環境で実行するように拡張した手法が二つ存在する。同期型分枝限定法（例えば、非特許文献３参照）と分散分枝限定法（例えば、非特許文献４参照）がそれである。
【０００８】
同期型分枝限定法は逐次の分枝限定法を分散環境でシミュレートしているだけである。そのため、分散処理の並列性や耐故障性といった利点が失われてしまう。
【０００９】
一方、分散分枝限定法は、全情報を単一サーバに集約して分枝限定法を開始し、分枝が生じたら別のサーバに分枝先の処理（部分問題）を移す、という方法で分散処理を実現している。これにより処理の並列性は保証できるが、大域的な処理は単一サーバが管理することになるので、耐故障性や動的な変化への対応の可能性が低くなる。負荷分散のように元々分散している情報に関する最適化問題には向かない手法である。
【００１０】
なお、集中的環境の場合には、通信遅延の影響や情報の局所性の問題が生じないため、数理計画法に基づいた厳密解法や近似解法を採用することができる。しかし、実際の分散システムでは通信遅延の影響や情報の局所性の問題が無視できないため、集中的環境で扱える問題は小規模な問題などに限られてしまう。
【００１１】
【非特許文献１】Ｂ．Ａ．Ｓｈｉｒａｚｉ、Ａ．Ｒ．Ｈｕｒｓｏｎ、ａｎｄ  Ｋ．Ｍ．Ｋａｖｉ  ｅｄｓ．、Ｓｃｈｅｄｕｌｉｎｇ  ａｎｄ  Ｌｏａｄ  Ｂａｌａｎｃｉｎｇ  ｉｎ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ  Ｐｒｅｓｓ、１９９５
【非特許文献２】柳浦睦憲、茨木俊秀、組合せ最適化−メタ戦略を中心として−、朝倉書店、２００１
【非特許文献３】平山勝敏、横尾真、分散不完全制約充足問題、人工知能学会論文誌、Ｖｏｌ．１４、Ｎｏ．４、ｐｐ．６３６−６４５、１９９９
【非特許文献４】Ｊａｒｏｓｌａｖ  Ｂ´Ｓｔ．ａｎｋｏｖ´ａｒｔａ、Ｏｌｇａ．ｅｐ´ａ、  ａｎｄ  Ｍｉｃｈａｌ  Ｐ．ｅｃｈｏｕ．ｃｅｋ、“Ｄｉｓｔｒｉｂｕｔｅｄ  Ｂｒａｎｃｈ  ａｎｄ  Ｂｏｕｎｄ  Ａｌｇｏｒｉｔｈｍ  ｉｎ  Ｃｏａｌｉｔｉｏｎ  Ｐｌａｎｎｉｎｇ、”  Ｌｅｃｔｕｒｅ  Ｎｏｔｅ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、Ｖｏｌ．２３２２（ＭＡＳＡ２００１）、ｐｐ．１５９−１６８、２００２
【特許文献１】特願２０００−３５６０９３
【特許文献２】特願２００１−１１５５２２
【特許文献３】特願２００１−２４１１９７、
【発明の開示】
【発明が解決しようとする課題】
【００１２】
従来の分散環境での分枝限定法にはそれぞれ先に述べたような欠点がある。本発明では、より分散環境に適し、かつ、最適解が求められる手法を構築する。具体的には、非同期完全分散環境において、情報を単一サーバに集約したり全体の制御を単一サーバが担ったりせずに、最適解（最大負荷量の最小化）を求める。さらに、逐次環境における分枝限定法と同様に、実行途中で止めた場合にその時点で得られているものがひとつの近似解とでき、また、逆に他の近似解法で得られた近似解を利用することもできる手法にする。
【００１３】
本発明が対象とする問題を下記のように定義する。ネットワークＧ＝（Ｈ，Ｌ）を考える。ここで、ＨはネットワークＧ上のｎ個のホストの集合で、Ｌはそれらホストを結ぶ通信リンクの集合である。また、ｍ個のタスクに対応するｍ次元ベクトルｘ＝（ｘ1  ｘ2  …  ｘm）Tを考え、この各要素がタスクとしてＧ上のホストに分散している。ｘj＝ｉはｈiがタスクｊを保持していることを表している。つまり、１≦ｘi≦ｎとなる。このタスクの配置ｘの初期状態としてｘ0を定義する。このような状況の下で、下記のような最適化問題を考える。
【００１４】
【数１】
2006185361.tif 000003
【００１５】
【数２】
2006185361.tif 000004
【００１６】
上記の典型的な問題が負荷分散である。このとき、ｆi（ｘ）はｈiのＣＰＵコストを、ｇi（ｘ）はタスク間の通信コストを、ｋi（ｘ0，ｘ）はタスクのｈiへの移動コストを表す。もし、∀i，ｇi（ｘ）＝ｋi（ｘ0，ｘ）＝０であれはこの問題はＣＰＵコストのみを考慮した問題となり、基本的なｍｕｌｔｉｐｒｏｃｅｓｓｏｒ  ｓｃｈｅｄｕｌｉｎｇと同等になる（なお、∀i，ｋi（ｘ0，ｘ）＝０の場合の問題が請求項１で扱う問題に相当し、∀i，ｇi（ｘ）＝０の場合の問題が請求項２で扱う問題に相当し、すべてのコストを考慮した問題が請求項３で扱う問題に相当している）。この問題においては下記の制約が存在する。
１．初期状態でｈiが持つ情報：
（ａ）ｈiに初期状態で存在するタスクｊ（ｘj＝ｉ）とその情報（ｗj、ｂj、∀ｒ，ｃjr）
（ｂ）隣接ホスト集合
（ｃ）ｙ0＝ｍａｘjｙj（ｘ0，ｘ）
（ｄ）ｙ0＝ｙa0となるホストｈa0
（ｅ）Ｑ＝（ｑj r）
２．各ホストが直接通信できる相手は隣接ホストに限られる。
３．各ホストは（隣接ホストでない）通信先ホストが与えられればそこへのルーティング（対応する隣接ホスト）とそこへの単位量当りの通信コスト（Ｑ）は得られるが、システム中に存在するホスト数やタスク数に関する情報は得られない。
４．各ホストは他のホスト固有の情報（ｐj）を知ることはできない。
【００１７】
なお、実際にｙ0，ａ0を知るには、拡散アルゴリズムやブロードキャストを使うのが簡単な方法になる。
【００１８】
最後に分散システムのモデルを述べる。本発明で扱う分散システムは非同期システムである。非同期システムでは、各通信リンクがＦＩＦＯ（先入先出）で通信遅延が有限であるという仮定の下で各プロセス（ホスト）が独立に送受信処理を行う。また、同一プロセス（ホスト）上では二つのイベント（メッセージ受信など）が同時には起こらないことを仮定する。
【００１９】
すなわち、本発明は、非同期完全分散環境において全情報を単一サーバに集約させず、かつ、システムを制御する唯一の存在もない状況において、最適解を求めることが可能となる情報処理システムおよびタスク分散処理方法を提供することを目的とする。
【課題を解決するための手段】
【００２０】
本発明の第一の観点は、２以上のサーバを有し、複数のタスクを前記２以上のサーバに分散させて実行する情報処理システムであって、本発明の特徴とするところは、前記情報処理システムを構成するそれぞれのサーバは、当該サーバで実行するタスクを識別するタスク識別子を格納しているタスク識別子格納部と、前記タスク識別子格納部に格納されているタスク識別子に対応付けられた情報であり、かつ前記タスク識別子で識別されるタスクを実行する際の負荷を示す情報であるタスク負荷情報または当該サーバの処理性能を示す処理性能情報を格納しているＣＰＵ負荷情報格納部と、当該サーバと他のサーバ間の通信の負荷に関する情報である通信負荷情報または前記タスク識別子格納部に格納されているタスク識別子で識別されるタスクと、他のサーバに格納されているタスク識別子で識別されるタスクとの間の通信量に関する情報であるタスク間通信負荷情報とを格納している通信負荷情報格納部と、前記タスク負荷情報または前記処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出するＣＰＵ負荷算出部と、前記通信負荷情報または前記タスク間通信量情報に基づいて通信負荷に関する情報である通信負荷情報を算出する通信負荷算出部と、前記ＣＰＵ負荷算出部が算出したＣＰＵ負荷情報および前記通信負荷算出部が算出した通信負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出する総合負荷情報算出部と、前記タスク識別子格納部に格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、前記総合負荷情算報出部が算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信するタスク実行負荷情報送信部と、１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信するタスク実行負荷情報受信部と、前記タスク実行負荷情報受信部が受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記総合負荷情算出部が算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得するタスク実行負荷情報取得部と、タスク実行負荷情報が既に蓄積されていない場合には、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積するタスク実行負荷情報蓄積部と、前記タスク識別子格納部に格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信するタスク移動情報送信部とを備えたところにある。
【００２１】
あるいは、本発明は、２以上のサーバを有し、複数のタスクを前記２以上のサーバに分散させて実行する情報処理システムであって、本発明の特徴とするところは、前記情報処理システムを構成するそれぞれのサーバは、当該サーバで実行するタスクを識別するタスク識別子を格納しているタスク識別子格納部と、前記タスク識別子格納部に格納されているタスク識別子に対応付けられた情報であり、かつ前記タスク識別子で識別されるタスクを実行する際の負荷を示す情報であるタスク負荷情報または当該サーバの処理性能を示す処理性能情報を格納しているＣＰＵ負荷情報格納部と、前記タスク識別子格納部に格納されているタスク識別子で識別されるタスクのプログラムのサイズに関する情報であるサイズ情報を格納しているプログラムサイズ情報格納部と、前記タスク負荷情報または前記処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出するＣＰＵ負荷算出部と、前記サイズ情報に基づいてタスクが移動する場合の負荷に関する情報である移動負荷情報を算出する移動負荷算出部と、前記ＣＰＵ負荷算出部が算出したＣＰＵ負荷情報および前記移動負荷算出部が算出した移動負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出する総合負荷情報算出部と、前記タスク識別子格納部に格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、前記総合負荷情算報出部が算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信するタスク実行負荷情報送信部と、１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信するタスク実行負荷情報受信部と、前記タスク実行負荷情報受信部が受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記総合負荷情算出部が算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得するタスク実行負荷情報取得部と、タスク実行負荷情報が既に蓄積されていない場合には、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積するタスク実行負荷情報蓄積部と、前記タスク識別子格納部に格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信するタスク移動情報送信部とを備えたところにある。
【００２２】
あるいは、本発明は、２以上のサーバを有し、複数のタスクを前記２以上のサーバに分散させて実行する情報処理システムであって、本発明の特徴とするところは、前記情報処理システムを構成するそれぞれのサーバは、当該サーバで実行するタスクを識別するタスク識別子を格納しているタスク識別子格納部と、前記タスク識別子格納部に格納されているタスク識別子に対応付けられた情報であり、かつ前記タスク識別子で識別されるタスクを実行する際の負荷を示す情報であるタスク負荷情報または当該サーバの処理性能を示す処理性能情報を格納しているＣＰＵ負荷情報格納部と、当該サーバと他のサーバ間の通信の負荷に関する情報である通信負荷情報または前記タスク識別子格納部に格納されているタスク識別子で識別されるタスクと、他のサーバに格納されているタスク識別子で識別されるタスクとの間の通信量に関する情報であるタスク間通信負荷情報とを格納している通信負荷情報格納部と、前記タスク識別子格納部に格納されているタスク識別子で識別されるタスクのプログラムのサイズに関する情報であるサイズ情報を格納しているプログラムサイズ情報格納部と、前記タスク負荷情報または前記処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出するＣＰＵ負荷算出部と、前記通信負荷情報または前記タスク間通信負荷情報に基づいて通信負荷に関する情報である通信負荷情報を算出する通信負荷算出部と、前記サイズ情報に基づいてタスクが移動する場合の負荷に関する情報である移動負荷情報を算出する移動負荷算出部と、前記ＣＰＵ負荷算出部が算出したＣＰＵ負荷情報および前記通信負荷算出部が算出した通信負荷情報および前記移動負荷算出部が算出した移動負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出する総合負荷情報算出部と、前記タスク識別子格納部に格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、前記総合負荷情算報出部が算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信するタスク実行負荷情報送信部と、１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信するタスク実行負荷情報受信部と、前記タスク実行負荷情報受信部が受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記総合負荷情算出部が算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得するタスク実行負荷情報取得部と、タスク実行負荷情報が既に蓄積されていない場合には、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積するタスク実行負荷情報蓄積部と、前記タスク識別子格納部に格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信するタスク移動情報送信部とを備えたところにある。
【００２３】
また、前記総合負荷情報算出部は、当該サーバが保持しているタスク負荷情報または処理性能情報またはタスク間通信負荷情報またはサイズ情報および前記タスク実行負荷情報受信部が受信したタスク実行負荷情報に基づいて、当該サーバの負荷を示す情報である中間負荷情報を算出し、当該中間負荷情報が示す負荷が蓄積した最大総合負荷情報が示す負荷を超えるか否かを判断する中間判断手段を備え、前記中間判断手段は、中間負荷情報の示す負荷が蓄積した最大総合負荷情報が示す負荷を超えると判断した場合に、当該タスク実行負荷情報が有するタスク実行情報と所定の関係を満たすタスク実行情報における総合負荷情報の算出を禁止する手段を備えることができる。
【００２４】
また、前記総合負荷情報算出部は、当該サーバが保持しているタスク負荷情報または処理性能情報またはタスク間通信負荷情報またはサイズ情報および前記タスク実行負荷情報受信部が受信したタスク実行負荷情報に基づいて、当該サーバの負荷を示す情報である中間負荷情報を算出し、当該中間負荷情報が示す負荷が蓄積した最大総合負荷情報が示す負荷を超えるか否かを判断する中間判断手段を備え、前記情報処理システムを構成するそれぞれのサーバは、前記中間判断手段が中間負荷情報の示す負荷が蓄積した最大総合負荷情報が示す負荷を超えると判断した場合に、当該タスク実行負荷情報が有するタスク実行情報を有する情報であり、総合負荷情報の算出が不要である旨を示す情報である評価不要情報を、他の１以上のサーバに送信する評価不要情報送信部と、他の１以上のサーバから評価不要情報を受信する評価不要情報受信部とをさらに備え、前記総合負荷情報算出部は、前記評価不要情報受信部が受信した評価不要情報が有するタスク実行情報と所定の関係を満たすタスク実行情報における総合負荷情報の算出は禁止する手段を備えることができる。
【００２５】
また、前記情報処理システムを構成するそれぞれのサーバにおいて、前記タスク実行負荷情報送信部は、前記タスク実行負荷情報蓄積部が、タスク実行負荷情報が既に蓄積されており、前記タスク実行負荷情報取得部が取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さいために当該タスク実行負荷情報を蓄積した場合に、当該蓄積したタスク実行負荷情報を送信する手段を備えることができる。
【００２６】
本発明の第二の観点は、汎用のコンピュータ装置にインストールすることにより、その汎用のコンピュータ装置に、本発明の情報処理システムにおけるサーバに相応する機能を実現させるプログラムである。
【００２７】
本発明のプログラムは記録媒体に記録されることにより、前記コンピュータ装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記コンピュータ装置に本発明のプログラムをインストールすることもできる。
【００２８】
これにより、汎用のコンピュータ装置を用いて、本発明のサーバを実現することができる。
【００２９】
本発明の第三の観点は、複数のタスクを２以上のサーバに分散させて実行するタスク分散処理方法であって、本発明の特徴とするところは、前記２以上のサーバにおいて、独自に、タスク負荷情報または処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出し、通信負荷情報またはタスク間通信負荷情報に基づいて通信負荷に関する情報である通信負荷情報を算出し、前記ＣＰＵ負荷情報および前記通信負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出し、格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、前記算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信し、１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信し、前記受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得し、タスク実行負荷情報が既に蓄積されていない場合には、前記取得したタスク実行負荷情報タスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積し、前記格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信し、かつ、所定の終了条件を満たした際に、１以上のサーバに蓄積されているタスク実行負荷情報が有するタスク実行情報に基づいて、２以上のサーバで複数のタスクを実行するところにある。
【００３０】
あるいは、本発明は、複数のタスクを２以上のサーバに分散させて実行するタスク分散処理方法であって、本発明の特徴とするところは、前記２以上のサーバにおいて、独自に、格納されているタスク負荷情報または格納されている処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出し、格納されているサイズ情報に基づいてタスクが移動する場合の負荷に関する情報である移動負荷情報を算出し、前記ＣＰＵ負荷情報および前記移動負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出し、格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、前記総合負荷情算報出部が算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信し、１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信し、前記受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得し、タスク実行負荷情報が既に蓄積されていない場合には、前記取得したタスク実行負荷情報タスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積し、格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信し、かつ、所定の終了条件を満たした際に、１以上のサーバに蓄積されているタスク実行負荷情報が有するタスク実行情報に基づいて、２以上のサーバで複数のタスクを実行するところにある。
【００３１】
あるいは、本発明は、複数のタスクを２以上のサーバに分散させて実行するタスク分散処理方法であって、本発明の特徴とするところは、前記２以上のサーバにおいて、独自に、格納されているタスク負荷情報または格納されている処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出し、格納されている通信負荷情報または格納されているタスク間通信負荷情報に基づいて通信負荷に関する情報である通信負荷情報を算出し、格納されているサイズ情報に基づいてタスクが移動する場合の負荷に関する情報である移動負荷情報を算出し、前記ＣＰＵ負荷情報および前記通信負荷情報および前記移動負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出し、格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、前記総合負荷情算報出ステップで算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信し、１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信し、前記受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記し算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得し、タスク実行負荷情報が既に蓄積されていない場合には、前記取得したタスク実行負荷情報タスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積し、格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信し、かつ、所定の終了条件を満たした際に、１以上のサーバに蓄積されているタスク実行負荷情報が有するタスク実行情報に基づいて、２以上のサーバで複数のタスクを実行するところにある。
【発明の効果】
【００３２】
本発明により、非同期完全分散環境において全情報を単一サーバに集約させず、かつ、システムを制御する唯一の存在もない状況において、最適解を求めることが可能となる。これはどの従来法でも実現できていない。
【００３３】
また、完全ではないが、ホストやリンクの故障やメッセージ消失などに対する耐故障性や、メッセージの順番の入れ替えに対する頑健性、ホスト毎の動作の自律性（自由度の大きさ）、他手法との融合、という点も従来法よりも向上している。
【発明を実施するための最良の形態】
【００３４】
本実施例におけるサーバ１台あたりのシステム構成を図１に示す。また、本実施例におけるサーバの動作を示すフローチャートを図２〜１２に示す。また、実行例におけるネットワーク形状と初期配置を図１３に示す。
【００３５】
本実施例は、図１３に示すように、２以上のサーバ（ホストｈ1〜ｈ4）を有し、複数のタスク（タスク１（ｘ1）、タスク２（ｘ2）、タスク３（ｘ3））を前記２以上のサーバに分散させて実行する情報処理システムであって、本実施例の特徴とするところは、前記情報処理システムを構成するそれぞれのサーバは、図１示すように、当該サーバで実行するタスクを識別するタスク識別子を格納しているタスク識別子格納部１０と、タスク識別子格納部１０に格納されているタスク識別子に対応付けられた情報であり、かつ前記タスク識別子で識別されるタスクを実行する際の負荷を示す情報であるタスク負荷情報または当該サーバの処理性能を示す処理性能情報を格納しているＣＰＵ負荷情報格納部１１と、当該サーバと他のサーバ間の通信の負荷に関する情報である通信負荷情報またはタスク識別子格納部１０に格納されているタスク識別子で識別されるタスクと、他のサーバに格納されているタスク識別子で識別されるタスクとの間の通信量に関する情報であるタスク間通信負荷情報とを格納している通信負荷情報格納部１２と、前記タスク負荷情報または前記処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出するＣＰＵ負荷算出部７と、前記通信負荷情報または前記タスク間通信量情報に基づいて通信負荷に関する情報である通信負荷情報を算出する通信負荷算出部８と、ＣＰＵ負荷算出部７が算出したＣＰＵ負荷情報および通信負荷算出部８が算出した通信負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出する総合負荷情報算出部５と、タスク識別子格納部１０に格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、総合負荷情算報出部５が算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信するタスク実行負荷情報送信部４と、１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信するタスク実行負荷情報受信部１と、タスク実行負荷情報受信部１が受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、総合負荷情算出部５が算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得するタスク実行負荷情報取得部２と、タスク実行負荷情報が既に蓄積されていない場合には、タスク実行負荷情報取得部２が取得したタスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、タスク実行負荷情報取得部２が取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積するタスク実行負荷情報蓄積部３と、タスク識別子格納部１０に格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信するタスク移動情報送信部６とを備えたところにある。
【００３６】
あるいは、情報処理システムを構成するそれぞれのサーバは、当該サーバで実行するタスクを識別するタスク識別子を格納しているタスク識別子格納部１０と、タスク識別子格納部１０に格納されているタスク識別子に対応付けられた情報であり、かつ前記タスク識別子で識別されるタスクを実行する際の負荷を示す情報であるタスク負荷情報または当該サーバの処理性能を示す処理性能情報を格納しているＣＰＵ負荷情報格納部１１と、タスク識別子格納部１０に格納されているタスク識別子で識別されるタスクのプログラムのサイズに関する情報であるサイズ情報を格納しているプログラムサイズ情報格納部１３と、前記タスク負荷情報または前記処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出するＣＰＵ負荷算出部１１と、前記サイズ情報に基づいてタスクが移動する場合の負荷に関する情報である移動負荷情報を算出する移動負荷算出部９と、ＣＰＵ負荷算出部１１が算出したＣＰＵ負荷情報および移動負荷算出部が算出した移動負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出する総合負荷情報算出部５と、タスク識別子格納部１０に格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、総合負荷情算報出部５が算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信するタスク実行負荷情報送信部４と、１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信するタスク実行負荷情報受信部１と、タスク実行負荷情報受信部１が受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、総合負荷情報算出部５が算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得するタスク実行負荷情報取得部２と、タスク実行負荷情報が既に蓄積されていない場合には、タスク実行負荷情報取得部２が取得したタスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、タスク実行負荷情報取得部２が取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積するタスク実行負荷情報蓄積部３と、タスク識別子格納部１０に格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信するタスク移動情報送信部６とを備えたことを特徴とする。
【００３７】
あるいは、本実施例のサーバは、当該サーバで実行するタスクを識別するタスク識別子を格納しているタスク識別子格納部１０と、タスク識別子格納部１０に格納されているタスク識別子に対応付けられた情報であり、かつ前記タスク識別子で識別されるタスクを実行する際の負荷を示す情報であるタスク負荷情報または当該サーバの処理性能を示す処理性能情報を格納しているＣＰＵ負荷情報格納部１１と、当該サーバと他のサーバ間の通信の負荷に関する情報である通信負荷情報またはタスク識別子格納部１０に格納されているタスク識別子で識別されるタスクと、他のサーバに格納されているタスク識別子で識別されるタスクとの間の通信量に関する情報であるタスク間通信負荷情報とを格納している通信負荷情報格納部１２と、タスク識別子格納部１０に格納されているタスク識別子で識別されるタスクのプログラムのサイズに関する情報であるサイズ情報を格納しているプログラムサイズ情報格納部１３と、前記タスク負荷情報または前記処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出するＣＰＵ負荷算出部７と、前記通信負荷情報または前記タスク間通信負荷情報に基づいて通信負荷に関する情報である通信負荷情報を算出する通信負荷算出部８と、前記サイズ情報に基づいてタスクが移動する場合の負荷に関する情報である移動負荷情報を算出する移動負荷算出部９と、ＣＰＵ負荷算出部７が算出したＣＰＵ負荷情報および通信負荷算出部８が算出した通信負荷情報および移動負荷算出部９が算出した移動負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出する総合負荷情報算出部５と、タスク識別子格納部１０に格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、総合負荷情算報出部５が算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信するタスク実行負荷情報送信部４と、１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信するタスク実行負荷情報受信部１と、タスク実行負荷情報受信部１が受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、総合負荷情算出部５が算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得するタスク実行負荷情報取得部２と、タスク実行負荷情報が既に蓄積されていない場合には、タスク実行負荷情報取得部２が取得したタスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、タスク実行負荷情報取得部２が取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積するタスク実行負荷情報蓄積部３と、タスク識別子格納部１０に格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信するタスク移動情報送信部６とを備えたことを特徴とする。
【００３８】
また、総合負荷情報算出部５は、当該サーバが保持しているタスク負荷情報または処理性能情報またはタスク間通信負荷情報またはサイズ情報およびタスク実行負荷情報受信部１が受信したタスク実行負荷情報に基づいて、当該サーバの負荷を示す情報である中間負荷情報を算出し、当該中間負荷情報が示す負荷が蓄積した最大総合負荷情報が示す負荷を超えるか否かを判断する中間判断手段を備え、この中間判断手段は、中間負荷情報の示す負荷が蓄積した最大総合負荷情報が示す負荷を超えると判断した場合に、当該タスク実行負荷情報が有するタスク実行情報と所定の関係を満たすタスク実行情報における総合負荷情報の算出を禁止する手段を備える。
【００３９】
あるいは、総合負荷情報算出部５は、当該サーバが保持しているタスク負荷情報または処理性能情報またはタスク間通信負荷情報またはサイズ情報およびタスク実行負荷情報受信部１が受信したタスク実行負荷情報に基づいて、当該サーバの負荷を示す情報である中間負荷情報を算出し、当該中間負荷情報が示す負荷が蓄積した最大総合負荷情報が示す負荷を超えるか否かを判断する中間判断手段を備え、前記情報処理システムを構成するそれぞれのサーバは、前記中間判断手段が中間負荷情報の示す負荷が蓄積した最大総合負荷情報が示す負荷を超えると判断した場合に、当該タスク実行負荷情報が有するタスク実行情報を有する情報であり、総合負荷情報の算出が不要である旨を示す情報である評価不要情報を、他の１以上のサーバに送信する評価不要情報送信部１４と、他の１以上のサーバから評価不要情報を受信する評価不要情報受信部１５とをさらに備え、総合負荷情報算出部５は、前記評価不要情報受信部１５が受信した評価不要情報が有するタスク実行情報と所定の関係を満たすタスク実行情報における総合負荷情報の算出は禁止する手段を備える。
【００４０】
また、前記情報処理システムを構成するそれぞれのサーバにおいて、タスク実行負荷情報送信部４は、タスク実行負荷情報蓄積部３が、タスク実行負荷情報が既に蓄積されており、タスク実行負荷情報取得部２が取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さいために当該タスク実行負荷情報を蓄積した場合に、当該蓄積したタスク実行負荷情報を送信する手段を備える。
【００４１】
本実施例は、汎用のコンピュータ装置にインストールすることにより、そのコンピュータ装置に本実施例のサーバに相応する機能を実現させるプログラムとして実現することができる。このプログラムは、記録媒体に記録されてコンピュータ装置にインストールされ、あるいは通信回線を介してコンピュータ装置にインストールされることにより当該コンピュータ装置に、図１に示す本実施例のサーバに相応する機能を実現させることができる。
【００４２】
また、本実施例は、複数のタスクを２以上のサーバに分散させて実行するタスク分散処理方法であって、本実施例の特徴とするところは、前記２以上のサーバにおいて、独自に、タスク負荷情報または処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出し、通信負荷情報またはタスク間通信負荷情報に基づいて通信負荷に関する情報である通信負荷情報を算出し、前記ＣＰＵ負荷情報および前記通信負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出し、格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、前記算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信し、１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信し、前記受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得し、タスク実行負荷情報が既に蓄積されていない場合には、前記取得したタスク実行負荷情報タスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積し、前記格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信し、かつ、所定の終了条件を満たした際に、１以上のサーバに蓄積されているタスク実行負荷情報が有するタスク実行情報に基づいて、２以上のサーバで複数のタスクを実行するところにある。
【００４３】
あるいは、本実施例のタスク分散処理方法は、前記２以上のサーバにおいて、独自に、格納されているタスク負荷情報または格納されている処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出し、格納されているサイズ情報に基づいてタスクが移動する場合の負荷に関する情報である移動負荷情報を算出し、前記ＣＰＵ負荷情報および前記移動負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出し、格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、前記総合負荷情算報出部が算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信し、１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信し、前記受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得し、タスク実行負荷情報が既に蓄積されていない場合には、前記取得したタスク実行負荷情報タスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積し、格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信し、かつ、所定の終了条件を満たした際に、１以上のサーバに蓄積されているタスク実行負荷情報が有するタスク実行情報に基づいて、２以上のサーバで複数のタスクを実行することを特徴とする。
【００４４】
あるいは、本実施例のタスク分散処理方法は、前記２以上のサーバにおいて、独自に、格納されているタスク負荷情報または格納されている処理性能情報に基づいてＣＰＵの負荷に関する情報であるＣＰＵ負荷情報を算出し、格納されている通信負荷情報または格納されているタスク間通信負荷情報に基づいて通信負荷に関する情報である通信負荷情報を算出し、格納されているサイズ情報に基づいてタスクが移動する場合の負荷に関する情報である移動負荷情報を算出し、前記ＣＰＵ負荷情報および前記通信負荷情報および前記移動負荷情報に基づいて、当該サーバの負荷を示す情報である総合負荷情報を算出し、格納されているタスク識別子を有する情報であり、複数のタスクが実行されるサーバに関する情報であるタスク実行情報と、前記総合負荷情算報出ステップで算出した総合負荷情算報の組であるタスク実行負荷情報とを他の１以上のサーバに送信し、１以上の他のサーバから当該他の情報の１以上のタスク実行負荷情報を受信し、前記受信した１以上のタスク実行負荷情報が有する１以上の総合負荷情報と、前記し算出した総合負荷情報の中で最大の負荷を示す最大総合負荷情報が有するタスク実行負荷情報とを取得し、タスク実行負荷情報が既に蓄積されていない場合には、前記取得したタスク実行負荷情報タスク実行負荷情報を蓄積し、タスク実行負荷情報が既に蓄積されている場合には、前記取得したタスク実行負荷情報が有する最大総合負荷情報が、蓄積されているタスク実行負荷情報が有する最大総合負荷情報より小さい場合に当該タスク実行負荷情報を蓄積し、格納されているタスク識別子を有するタスク移動情報を前記１以上の他のサーバに送信し、かつ、所定の終了条件を満たした際に、１以上のサーバに蓄積されているタスク実行負荷情報が有するタスク実行情報に基づいて、２以上のサーバで複数のタスクを実行することを特徴とする。
【００４５】
以下では、本実施例をさらに詳細に説明する。
【００４６】
本実施例は分枝限定法と基本としているものの、通常の分枝限定法のような単一の分枝木に基づいた解の探索を行うのではなく、各ホストごとに異なる分枝木に基づいて並列に解の探索を行う。具体的には、分枝は初期状態と隣接ホストから送られてきた情報に基づいて起こる。また、各状態（各変数の値を固定したもの：解の候補（タスク割当）のひとつ）における目的関数値（負荷量）の計算は、各ホストごとに自身の値を計算し、そのなかの最大値を取る必要がある。つまり、目的関数値の計算にもホスト間の協調が必要になる。本発明のアルゴリズムは、逐次環境における分枝限定法と同様に、大きく分けて三つの機能から成り立つ。
１．暫定解の更新：拡散アルゴリズムを利用して実現する。
２．分枝操作：二つあるいはそれ以上の状態の組合せにより実現し、すべての可能な組合せを試す。そして、新たに生成された状態にタスクの移動が含まれていればその移動先へその状態を通知する。さらに、すべての状態を列挙するために特別な処理（後述）も必要に応じて行う。
３．限定操作：ある状態が現在の暫定解よりも良い解を導き出すことがないと判明した場合には、その状態を限定（削除）する。そして、必要があればその事実を関係する隣接ホストへ通知する。
【００４７】
これらのうち、分枝操作だけでも最適解を求めることは可能である（請求項１〜３に相当）。つまり、すべての状態の列挙だけを行い、それをし尽くした段階で最小の目的関数値を与える状態を選択すれば最適解は求まる。他の二つの機能は効率化のための工夫であり、暫定解の更新は他の近似解法の結果の反映にも使われる（暫定解を保持することは請求項４に相当し、限定操作は請求項５に相当し、全ホストの暫定解を更新することは請求項６に相当する）。詳細なアルゴリズム下記に示す。ただし、上記のようにアルゴリズムから一部分だけを取出しても動作することに注意のこと。
【００４８】
変数と定数の定義：
【００４９】
【数３】
2006185361.tif 000005
【００５０】
【数４】
2006185361.tif 000006
メッセージ受信により起動される処理：
１．隣接ホストｈ′から暫定解更新メッセージｕｐｄａｔｅ（ｙ′，ａ′）を受信したとき：図４および図５にフローチャートを示す。
【００５１】
ｙ≦ｙ′ならば何もしない。ｙ＞ｙ′ならば下記を実行する：ｙ：＝ｙ′、ａ：＝ａ′とし、暫定解更新メッセージｕｐｄａｔｅ（ｙ，ａ）をｈ′以外の隣接ホストへ送信する。∀ｓ∈Ｓに対し、ｙ（ｓ）＞ｙであれば
【００５２】
【数５】
2006185361.tif 000007
とする。その際、
【００５３】
【数６】
2006185361.tif 000008
ならば、Ｓ′：＝Ｓ′∪｛ｓ｝とする。また、ｙs（ｓ）＞ｙでｓが隣接ホストへの移動を含んでいれば、限定メッセージｂｏｕｎｄ（ｓ，ｉ）をその隣接ホストへ送信する。ただし、先に送信済の暫定解更新メッセージによって隣接ホストで限定されることが明らかな場合にはこの限定メッセージは送信しない。∀ｓ′∈Ｓ′に対しても同様に、ｙs（ｓ′）＞ｙであれば
【００５４】
【数７】
2006185361.tif 000009
とし、ｓ′が隣接ホストへの移動を含んでいて暫定解更新メッセージにより限定されると明らかでない場合は、限定メッセージｂｏｕｎｄ（ｓ′，ｉ）をその隣接ホストへ送信する。
【００５５】
さらに、限定された状態に対応するタスク移動メッセージの受信がある場合には、その受信記録を削除し、限定された状態ｓに対応するｌｏｃａｌ＿ｍａｘメッセージまたはｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージが存在してｙa0（ｓ）≠ｙa0（ｘ0）（ｈa0へのタスク割当、あるいは、それらタスクと通信する他ホストにあるタスクの割当が初期状態から変化している）のとき、そのｌｏｃａｌ＿ｍａｘメッセージを受信したという記録を削除する。対応するｌｏｃａｌ＿ｍａｘメッセージまたはｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージが存在するがｙa0（ｓ）＝ｙa0（ｘ0）のときには、ｓがＳ′から削除された場合（ｙs（ｓ）＞ｙ）にはその受信記録を削除する。
２．タスク移動メッセージｍｉｇｒａｔｅ（ｘj，ｓ）を受信したとき：図６にフローチャートを示す。
【００５６】
ｚを状態ｓからｘj＝ｉと変更した状態とする。まず、受信メッセージを記録する。
【００５７】
【数８】
2006185361.tif 000010
であればＳ：＝Ｓ∪｛ｚ｝とする。ｓがＳ，Ｓ′，Ｉの状態との統合により新しい状態を構成することができるならばその状態を構成し、それぞれの状態に対して重複のないように本処理を繰り返す。ただし、統合が可能になるのは、
（ａ）統合後の状態が統合の基となった状態と矛盾しない（固定されている変数が変化しない）
（ｂ）統合後の状態が過去に列挙され限定されていない（Ｓ′から削除済の状態の部分を含む）
（ｃ）統合後の状態が複数の隣接ホストへの移動を含まない。つまり、移動を表す変数の値は同じ
（ｄ）∃ｊ，ｘsj≠ｘx0jでｘsjが移動しないならば、統合後の状態ｓ′は∀ｈ，ｘs′j≠ｘsj，ｘs′h≠ｘsjを満たす必要がある。
【００５８】
新たに生成された状態が隣接ホストへの移動を含んでいて、かつ、その状態が送信済の情報から移動先で生成できないならば、その状態をその移動先へタスク移動メッセージとして送信する。ｚを含め新しい状態がひとつも生成できなければ（生成した状態がすべて限定されてしまったら）、限定メッセージｂｏｕｎｄ（ｓ，ｉ）をタスク移動メッセージを送信してきたホストへ送信し、その受信記録を削除する。次いで、すべての変数が固定された状態の目的関数値を確定させるためと、全列挙を可能にするために、下記の処理を行う。
（ａ）すべての変数ｘj∈ｓが固定され、過去にｌｏｃａｌ＿ｍａｘ（ｓ，＊，＊）というメッセージ（“＊”は任意の値）を受信していない場合：ｌｏｃａｌ＿ｍａｘ（ｓ，ｙ（ｓ），ｉ）メッセージをすべての隣接ホストへ送信する。もし、タスク移動メッセージも同時に送信することになるなら、ｌｏｃａｌ＿ｍａｘメッセージの方を先にする。
（ｂ）ｌｏｃａｌ＿ｍａｘ（ｓ，ｙ′，ａ′）メッセージを受信した場合：図７および図８にフローチャートを示す。
【００５９】
まずｙ″＞ｙ′となるｌｏｃａｌ＿ｍａｘ（ｓ，ｙ″，ａ″）メッセージを受信したことがなければ、受信メッセージを記録するが、この内容のメッセージを過去に受信したことがない場合には、初めての受信であることも合わせて記録する。ｙ″＞ｙ′となるｌｏｃａｌ＿ｍａｘ（ｓ，ｙ″，ａ″）メッセージを受信したことがある場合には、単に受信メッセージを削除するだけで、下記のいずれの処理も行わない。
【００６０】
ｙ″＜ｙ′を満たすｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ，ｙ″，ａ″）メッセージを送受信した記録があれば、その記録を削除する。
（ｘj＝ｉかつｘ0j≠ｉ）または（ｘj≠ｉかつｘ0j＝ｉ）またはｇi（ｓ）≠ｇi（ｘ0）となるｘj∈ｓが存在して、ｌｏｃａｌ＿ｍａｘ（ｓ，ｙ（ｓ），ｉ）メッセージを送信したことがなく、ｙ（ｓ）≦ｙで、ｙ（ｓ）＞ｙ′かｙ（ｓ）＝ｙ′かつａ′＞ｉであれば、下記を実行する。
【００６１】
ｌｏｃａｌ＿ｍａｘ（ｓ，ｙ（ｓ），ｉ）メッセージをすべての隣接ホストへ送信し、ｌｏｃａｌ＿ｍａｘ（ｓ，＊，＊）の受信記録を削除する。
【００６２】
【数９】
2006185361.tif 000011
であれば、ｓをＳかＳ′のうち適切な方へ加え、ｚ＝ｓとなるタスク移動メッセージを受信したときと同じ処理を行う。ただし、それにより起こるタスク移動メッセージの送信は行わない。
（ｘj＝ｉかつｘ0j≠ｉ）または（ｘj≠ｉかつｘ0j＝ｉ）またはｇi（ｓ）≠ｇi（ｘ0）となるｘj∈ｓが存在して、この内容のメッセージの受信が初めてで、ｙ（ｓ）＜ｙ′≦ｙで、ｄi≧２であれば、受信メッセージｌｏｃａｌ＿ｍａｘ（ｓ，ｙ′，ａ′）をそれを送信してきたホストを除くすべての隣接ホストへ送信する。
【００６３】
∀ｊ，ｘｊ∈ｓに対して（ｘj≠ｉかつｘ0j≠ｉまたはｘj＝ｘ0j＝ｉ）でｇｉ（ｓ）＝ｇｉ（ｘ0）となり、この内容のメッセージの受信が初めてで、ｙ′≦ｙで、ｄi≧２であれば、受信メッセージｌｏｃａｌ＿ｍａｘ（ｓ，ｙ′，ａ′）をそれを送信してきたホストを除くすべての隣接ホストへ送信する。
【００６４】
上記の三つの処理がいずれも条件が合わずにメッセージ送信が実行されず、この受信によりこの内容のメッセージをすべての隣接ホストから受信したことになり、ａ′≠ｉであれば、ｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ，ｙ′，ａ′）メッセージをすべての隣接ホストへ送信し、ｌｏｃａｌ＿ｍａｘ（ｓ，＊，＊）の受信記録を削除し、送信したｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージの記録を取る。
【００６５】
∀ｊ，ｘj∈ｓに対して（ｘj≠ｉかつｘ0j≠ｉまたはｘj＝ｘ0j＝ｉ）でｇi（ｓ）＝ｇi（ｘ0）となり、ｙ′≦ｙで、
【００６６】
【数１０】
2006185361.tif 000012
ならば、ｓをｙ（ｓ）≦ｙのときにはＳへ、ｙ（ｓ）＞ｙのときにはＳ′へ加え、ｚ＝ｓとなるタスク移動メッセージを受信したときと同じ処理を行う。ただし、それにより起こるタスク移動メッセージの送信は行わない。
【００６７】
ｙ′＞ｙであるか、（ｘj＝ｉかつｘ0j≠ｉ）あるいは（ｘj≠ｉかつｘ0j＝ｉ）あるいはｇi（ｓ）≠ｇi（ｘ0）となるｘj∈ｓが存在してｙ（ｓ）＞ｙであれば、限定メッセージｂｏｕｎｄ（ｓ，ｉ）をすべての隣接ホストへ送信し、受信したｌｏｃａｌ＿ｍａｘの受信記録を削除する。
（ｃ）ｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ，ｙ′，ａ′）メッセージを受信した場合：図９および図１０にフローチャートを示す。
【００６８】
まず受信メッセージを記録する。ａ′≠ｉかつｙ≧ｙ′＞ｙ（ｓ）で、ｙ″＞ｙ′となるｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ，ｙ″，ａ″）メッセージかｌｏｃａｌ＿ｍａｘ（ｓ，ｙ″，ａ″）メッセージを受信したことがなければ、下記を実行する。
【００６９】
この時点でｄi−１個の隣接ホストから同じメッセージを受信またはそのホストへ送信していれば、ｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ，ｙ′，ａ′）メッセージを唯一このメッセージを送信してきていない隣接ホストへ送信して送信を記録する。そうでなく、これが最初の受信であれば、ｌｏｃａｌ＿ｍａｘ（ｓ，ｙ′，ａ′）を相互に送信し合った隣接ホスト（実際には、最初にｌｏｃａｌ＿ｍａｘ（ｓ，ｙ′，ａ′）を送ってきた隣接ホスト以外の隣接ホストのうち、ｌｏｃａｌ＿ｍａｘ（ｓ，ｙ′，ａ′）の受信記録があるホスト）へｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（ｓ，ｙ′，ａ′）メッセージを送信し、その送信を記録すると同時にｌｏｃａｌ＿ｍａｘ（ｓ，ｙ′，ａ′）の受信記録を削除する。
【００７０】
ａ′＝ｉ（ｙ′＝ｙ（ｓ）のはず）、ｙ′≦ｙ、ｇa0（ｓ）＝ｇa0（ｘ0）で、このメッセージをすべての隣接ホストから受信していて、∀ｊ，ｘj∈ｓに対して（ｘj＝ａ0かつｘj０＝ａ0）または（ｘj≠ａ0かつｘj０≠ａ0）となるならば、ｌｏｃａｌ＿ｉｍｐｒｏｖｅ（ｓ，ｙ（ｓ））メッセージをｈa0に向けて送信（実際にはｈa0方向の隣接ホストへ送信）し、対応するｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージの送受信記録を削除する。
【００７１】
ａ′＝ｉ（ｙ′＝ｙ（ｓ）のはず）、ｙ（ｓ）＜ｙでこのメッセージをすべての隣接ホストから受信していて、かつ、ｇa0（ｓ）≠ｇa0（ｘ0）となるかあるいは（ｘj＝ａ0かつｘj≠ａ0）または（ｘj≠ａ0かつｘj0＝ａ0）となるｘj∈ｓが存在するならば、ｙ：＝ｙ（ｓ）として暫定解更新メッセージｕｐｄａｔｅ（ｙ（ｓ），ｉ）をすべての隣接ホストへ送信し、ｕｐｄａｔｅ（ｙ（ｓ），ｉ）を受信したときと同じ処理（ｕｐｄａｔｅの転送処理を除く）をしてから、対応するｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージの送受信記録を削除する。
【００７２】
ａ′＝ｉでこのメッセージをまだすべての隣接ホストから受信し終わっていないなら、受信メッセージの記録のみを行う。
【００７３】
ｙ′＞ｙであるか、あるいは、ｙ（ｓ）＞ｙで（ｘj＝ｉかつｘj≠ｉ）あるいは（ｘj≠ｉかつｘj0＝ｉ）あるいはｇi（ｓ）≠ｇi（ｘ0））となるｘj∈ｓが存在するならば、ｂｏｕｎｄ（ｓ，ｉ）メッセージを、この限定メッセージを送受信したことがない場合に限りすべての隣接ホストへ送信し、対応するｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージの送受信記録を削除する。
（ｄ）ｌｏｃａｌ＿ｉｍｐｒｏｖｅ（ｓ，ｙ′）メッセージを受信した場合：図１１にフローチャートを示す。
【００７４】
ｉ≠ａ0かつｙ′≦ｙならばこのメッセージは単にｈa0へ中継されるが、もしｓがＳまたはＳ′に含まれていなければｓを適切な方に追加してタスク移動メッセージを受信してｓが生成されたときと同じ処理を行う。ただし、このメッセージに対応するｌｏｃａｌ＿ｍａｘを受信していたのであれば中継以外には何もすることはないはずである。
【００７５】
ｉ＝ａ0かつｙ′≦ｙならば、下記を実行する：
ｙ（ｓ）≦ｙならばｓをＳに加える。そうでなく、かつ、ｙ（ｓ）＝ｙ0＞ｙ≧ｙ′ならば、ｓをＳ′に加える。そして、タスク移動メッセージを受信してｓが生成されたときと同じ処理を行う。ただし、このメッセージに対応するｌｏｃａｌ＿ｍａｘを受信していたのであれば何もすることはないはずである。
【００７６】
一方、ｙ′＞ｙであればｂｏｕｎｄ（ｓ，ｉ）メッセージを、この限定メッセージを送受信したことがない場合に限り、すべての隣接ホストへ送信する。
３．限定メッセージｂｏｕｎｄ（ｓ，ｉ′）を受信した場合：図１２にフローチャートを示す。
【００７７】
まず、ｓが移動（ｈiへの移動のみ含みうる）を含んでいなければ、その限定メッセージを記録する。そして、これが状態ｓを限定する最初のメッセージ受信であれば、ｓ∈Ｓまたはｓ∈Ｉならば、その集合からｓを削除する。さらに、ｓを基にして生成された状態ｓ′があればそれも削除する。これら削除された状態が隣接ホストにある状態に影響するなら、限定メッセージをそのホストへ送信する。実際にはこの判断は難しいので下記のようにする：ｉ≠ｉ′でこれがこの限定メッセージの最初の受信であり、ｓがｈiから他のホストへの移動を含まないならば、受信した限定メッセージを、それを送信してきたホストを除くすべての隣接ホストへ転送する。そして、同じ限定メッセージをすべての隣接ホストから受信したら、その記録を削除できる。
【００７８】
上記アルゴリズムは、アルゴリズムによって生じるすべてのメッセージがシステム中で送信されなくなった場合に解が求まる。その解は、ホストｈaで負荷量ｙの状態である。実際にこの負荷量を実現するためには、この状態を関係するすべてのホストが認知して、それに従ってタスクを移動させれば良い。このアルゴリズムの停止状態を検出するひとつの方法はスナップショットを取ることであるが、それ以外に、システム中の状態を確認するメッセージ（拡散アルゴリズムの拡張）を送信して、その確認メッセージ以外のメッセージがシステム中にないことをもって終了と判定する方法もある。
【００７９】
このアルゴリズムは、逐次環境における分枝限定法と同様に、途中で止めた場合には近似解法として使うことができる。また、他の近似解法の結果得られた状態とそのときの負荷量を使って、暫定解更新メッセージを作り出し、さらに、その状態を関連ホストに通知することによって、本アルゴリズムの効率化に有効に利用できる。
【００８０】
なお、上記アルゴリズムにおいて、暫定解更新処理と移動を含まない状態の限定処理については、上記のような処理をせずに、ブロードキャストを使用する方法もある。また、各状態の目的関数値の計算も上記のようにｌｏｃａｌ＿ｍａｘメッセージとｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージを使用せずに、マルチキャストを利用する方法もある。マルチキャストを利用する場合には、ｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージに対応するようなａｃｋ（その値を了解したことを示すメッセージ）を返すことにより、関連するホスト間の合意を取る。ただし、マルチキャストを利用する場合には、関連ホスト以外がその情報を利用することが困難になる。
【００８１】
ここではある程度具体的な実行例を挙げて本方法を説明する．
（Ｉ）状況ごとの動作例
まず始めに、アルゴリズムのそれぞれの構成要素の動作例を仮想的に作成した状況において示す。ここで示すのは、
１．初期状態における処理の例
２．ｍｉｇｒａｔｅメッセージ受信時の処理の例
３．ｌｏｃａｌ＿ｍａｘメッセージ受信時の処理の例（三例）
４．ｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージ受信時の処理の例（二例）
５．ｌｏｃａｌ＿ｉｍｐｒｏｖｅメッセージ受信時の処理の例（二例）
６．ｕｐｄａｔｅメッセージ受信時の処理の例
７．ｂｏｕｎｄメッセージ受信時の処理の例（二例）
であり、それぞれそのときの状況によって動作が変わるので、状況も分けて示す。プロセスの内部状態の変化は記録している送受信メッセージ、内部変数（ｙ，ａ，Ｉ，Ｓ，Ｓ′）の変化がわかればよく、それ以外は受信したメッセージと、処理の結果送信されるメッセージがわかれば処理の内容は理解できるので、これらの情報のみを提示し、必要に応じて説明を加える。ここで使用するサーバｈiは、次数ｄiが２（隣接ホスト数２）で、初期状態において、タスクｊのみ保持している（ｘj0＝ｉ）。
【００８２】
また、ここでは計算の詳細は省き、動作のみを理解できるようにするための仮想的な値を用いる。具体的には、実際よりも状態数（特にＳの要素数）を極端に減らして分かりやすくすると共に、各詳細の数値（ｐi，ｗj，ｃij，ｑij，ｂj）を使った計算は明示的には行わず、その計算の結果起こる操作に都合が良いように計算結果を与えることで分かりやすくする。
【００８３】
以下では一部を除いてホストｈ1での動作で説明する。ｈ1は２台のホストｈ2，ｈ3に隣接しているとする。そして、いずれの場合も受信メッセージはｈ2から送られてきたとする。なお、以下の各例の間の関連性はない（つまり、同一の実行例からの抜粋ではない）ので注意。また、一部の例においては、このｈ1の設定では生じない状況を説明することになるため、上記の設定を説明用の設定に変更することがある。例を示す前に、下記の例で使われる記法の説明をする。
｛ｘ1＝１，ｘ2＝３｝（３０００）：状態とその状態による目的関数値の下限。Ｓの要素などに使われる。
【００８４】
この例の場合にはｘ1＝１，ｘ2＝３以外は未固定、つまり、初期状態の割当をそのまま継承しており、そのときの目的関数値は現在分かっている限りでは３０００を下回ることはない、ことを表している。ｘ1＝２s：ｔ1がｈ1からｈ2の方向へ移動されることを表す。初期状態から値が変更されるが、その変更の方向を規定していることになる。
【００８５】
送信メッセージ：送信メッセージはメッセージを送信順に”、”で区切って列挙することで表す。実際には、そのリンクに前に送信したメッセージがたまっていることがあるので、実際のリンク上にはここで記されたメッセージ以前にも存在する可能性もある。
１．初期状態における処理の例：
初期状態でｈ1にあるタスクをｔ1，ｔ2（つまり、ｘ1＝１，ｘ2＝１）とする。そして、事前の処理により、ｙ0＝１００００，ａ0＝２と判明しているとする。このとき、起動直後の処理により、ｈ1の内部状態と送信メッセージは下記のようになる。（ｙ0，ａ0は不変（定数）なので他の例も含め以下では省略する。）
内部状態：
・ｙ＝１００００
・ａ＝２
・Ｉ＝｛｛ｘ1＝２s｝，｛ｘ1＝３s｝，｛ｘ2＝２s｝，｛ｘ2＝３s｝｝
・Ｓ＝｛ｘ0（１００００）｝
・Ｓ′＝｛｝
送信メッセージ：
ｈ2へのメッセージ：ｍｉｇｒａｔｅ（ｘ1，ｘ0）、ｍｉｇｒａｔｅ（ｘ2，ｘ0）
ｈ3へのメッセージ：ｍｉｇｒａｔｅ（ｘ1，ｘ0）、ｍｉｇｒａｔｅ（ｘ2，ｘ0）
２．ｍｉｇｒａｔｅ（ｘ3，ｘ0）メッセージ受信時の処理の例：
受信前の内部状態を例１の処理結果の状態とする。すると、このメッセージ受信により、下記のような内部状態に変化して下記のようなメッセージを送信する。内部状態：
・ｙ＝１００００
・ａ＝２
・Ｉ＝｛｛ｘ1＝２s｝，｛ｘ1＝３s｝，｛ｘ2＝２s｝，｛ｘ2＝３s｝｝
・Ｓ＝｛ｘ0（１００００），｛ｘ1＝３s，ｘ3＝１｝（９０００），｛ｘ2＝３s，ｘ3＝１｝（８０００），｛ｘ3＝３s｝（１００００）｝
・Ｓ′＝｛ｘ3＝１｝
・受信メッセージ記憶領域：
ｈ2からのｍｉｇｒａｔｅメッセージ：｛（ｘ3，ｘ0）｝
送信メッセージ：
ｈ2へのメッセージ：
ｈ3へのメッセージ：ｍｉｇｒａｔｅ（ｘ3，ｘ0）、ｍｉｇｒａｔｅ（ｘ1，｛ｘ3＝１｝）、ｍｉｇｒａｔｅ（ｘ2，｛ｘ3＝１｝）
【００８６】
このような結果になった経緯を説明する。ｈ2から変数ｘ3の移動を受信したので、その変数の扱いとして、自身に割り当てる（ｘ3＝１）か送信元以外の隣接ホストへ転送する（ｘ3＝３s）かのいずれかになる。さらに、これら二つの状態とＩ，Ｓ，Ｓ′に含まれる各状態との組合わせによって新しい状態を構成していく。
【００８７】
このとき、可能な組合せの数は、この時点では変数の値が固定されたもの同士の組合わせの状態が存在しないため、すべてを列挙すると、ｘ1，ｘ2，ｘ3の各変数に対して割当方法としてそれぞれ３通り、３通り、２通りあるので、合計３×３×  ２＝１８通りある。しかし、アルゴリズム中にある制約により、このうちの多くは実際には生成されない。
【００８８】
まず、異なる方向への移動の組合せ、たとえばｘ1＝２sとｘ2＝３s、は生成しないので除外される。また、移動を含む状態は、送受信済の情報から生成できるものは除外するため、ｈ3へ送信済のｘ2およびｘ3をｈ3へ移動させるという情報から構成できるものは除外する。
【００８９】
この場合には、この時点でｘ3＝３sという状態が生成され、これがｈ3に送信されることにより、｛ｘ1＝３s，ｘ3＝３s｝などの状態はｈ3で生成され得り、かつ、移動を含んでいる状態ではまともな目的関数値計算はできないので、ｈ1では生成しない。さらに、生成された状態の目的関数値がｙを越えることが確実な場合には削除される。
【００９０】
この例においては、｛ｘ3＝１｝の状態の目的関数値がｙ＝１００００を越えることが判明したために、｛ｘ3＝１｝はＳに含まれていない。しかし、｛ｘ3＝１｝はｘ1あるいはｘ2のどちらか一方、あるいは両方が他のホストへ移動することにより目的関数値がｙ＝１００００以下になる可能性があるので、Ｓには入らないもののＳ′には含まれている。これらの結果、Ｓには上記のように新たに三つの状態のみが加わり、送信メッセージは上記のように三つになる。なお、この送信メッセージの順番に関する規定はない。そのため、このメッセージが逆になっても正常に動作する。ただし、順序が変わることで以後の動作に変化を及ぼすことはある。
【００９１】
また、ここでの例では生じなかったが、すべての変数が固定された状態が生成された場合にはｌｏｃａｌ＿ｍａｘメッセージを送信することになる。例えば、この例において、｛ｘ3＝１｝が削除されなかった場合には、そのときのこのホストの負荷量をｙ′とすると、ｌｏｃａｌ＿ｍａｘ（｛ｘ3＝１｝，ｙ′，１）というメッセージを送信することになる。
【００９２】
このメッセージはこの割当によって初期状態から負荷量が変化するホストにだけ送信されれば十分なので、もし、タスクｔ3が通信を必要としないのであればｈ1と初期状態でｔ3を持つホストの二ホスト間で計算すればよい。しかし、ｔ3が他のホストと通信する場合には、その通信相手タスクがあるホストでも負荷量が変化するので、そちらにも送信する必要がある。そのため、基本的には両隣にこのｌｏｃａｌ＿ｍａｘメッセージを送信することになる。
３．ｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２｝，４０００，２）メッセージ受信時の処理の例
（ａ）最初の受信：
既にｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２｝，ｙ′，ｊ）という形のメッセージを受信したことがあれば、そのメッセージのｙ′とこのメッセージの４０００とを比較し、大きい方のみを採用する。具体的には、ｙ′＞４０００ならばこのメッセージ受信による処理は何もなく、ｙ′＜４０００ならば、今まで記録していたｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２｝，ｙ′，ｊ）メッセージをすべて削除してから、下記のように処理を行う。なお、下記の例は、上記のｍｉｇｒａｔｅメッセージ受信後の状態でｈ2からｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２｝，４０００，２）を受信した場合の処理結果である。
内部状態：
・ｙ＝１００００
・ａ＝２
・Ｉ＝｛｛ｘ1＝２s｝，｛ｘ1＝３s｝，｛ｘ2＝２s｝，｛ｘ2＝３s｝｝
・Ｓ＝｛ｘ0（１００００），｛ｘ1＝３s，ｘ3＝１｝（９０００），｛ｘ2＝３s，ｘ3＝１｝（８０００），｛ｘ3＝３s｝（１００００），｛ｘ1＝２｝（６０００），｛ｘ1＝２，ｘ3＝１｝（９０００），｛ｘ1＝２，ｘ2＝３s，ｘ3＝１｝（３０００），｛ｘ1＝２，ｘ3＝３s｝（４０００），｛ｘ1＝２，ｘ2＝３s｝（０）｝
・Ｓ′＝｛ｘ3＝１｝
・受信メッセージ記憶領域：
ｈ2からのｍｉｇｒａｔｅメッセージ：｛（ｘ3，ｘ0）｝
ｈ2からのｌｏｃａｌ＿ｍａｘメッセージ：｛｝
送信メッセージ：
ｈ2へのメッセージ：ｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２｝，６０００，１），ｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２，ｘ3＝１｝，９０００，１）
ｈ3へのメッセージ：ｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２｝，６０００，１），ｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２，ｘ3＝１｝，９０００，１）
【００９３】
このような結果になった経緯を説明する。まず、受信したメッセージを記録する。その際、これが最初の受信なので、最初の受信であることも含めて記録される。このｈ2から受信したメッセージにより、新たに｛ｘ1＝２｝という状態が作成される。そして、この状態に対するｈ1の負荷量を計算すると６０００となり、これは受信したメッセージにあるｈ2の負荷量よりも高い。そのため、この状態のシステム負荷量の下限はｈ2が与えることはなくなり、現時点ではｈ1が与えている。
【００９４】
従って、最初に記録した受信メッセージは削除され、その代わりにｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２｝，６０００，１）というメッセージが全隣接ホストへ送信される。さらに、新たに生じた｛ｘ1＝２｝という状態と他の状態との組合わせにより、いくつかの状態が作成される。
【００９５】
そのうち、｛ｘ1＝２，ｘ3＝１｝という状態ではすべての変数割当が固定されているので、これの負荷量を求めるために、ｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２，ｘ3＝１｝，９０００，１）メッセージを全隣接ホストへ送信する。それ以外にいくつかの状態が生成されているが、いずれもこれら二つのメッセージとそれ以前に送受信したメッセージにある情報から生成できる状態であるため、ｍｉｇｒａｔｅメッセージなどは生じない。
【００９６】
ただし、そのようなｍｉｇｒａｔｅメッセージなどが実際に送られたとしてもシステムとしての動作には処理すべきメッセージが増えてその分遅くなる以外は影響はない。なお、この例においては受信した値が無効になり削除されて新たなｌｏｃａｌ＿ｍａｘメッセージの送信となったが、無効にならなかった場合には、他の隣接ホスト、この場合にはｈ3への転送が行われる。それ以外は同じである。
（ｂ）２回目以降ｄ−１回目までの受信：
受信の記録のみをし、あとは何もしない。
（ｃ）全隣接ホストからの受信：
ここでは、上記のｍｉｇｒａｔｅメッセージを受信した状態から、まずｈ2からｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２｝，４０００，２）を受信し、これが先の例とは異なり有効のまま残り、次いで同じｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２｝，４０００，２）をｈ3からも受信した場合の処理を示す。この場合には、Ｓ，Ｓ′等の内部状態には変化がないので、受信メッセージの記憶領域の変化と処理の結果送信されるメッセージのみを示す。
【００９７】
まず、受信前の受信メッセージ記憶領域は、
ｈ2からのｍｉｇｒａｔｅメッセージ：｛（ｘ3，ｘ0）｝
ｈ2からのｌｏｃａｌ＿ｍａｘメッセージ：｛（｛ｘ1＝２｝，４０００，２）*｝
であるとする。なお、ｌｏｃａｌ＿ｍａｘメッセージの受信記録において、右肩に．＊が付いているのは、このメッセージを最初に受信したのがこのホスト（ｈ2）であることを示している。このとき、上記メッセージ受信により、
受信メッセージ記憶領域：
ｈ2からのｍｉｇｒａｔｅメッセージ：｛（ｘ3，ｘ0）｝
ｈ2からのｌｏｃａｌ＿ｍａｘメッセージ：｛｝
ｈ2とのｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージ：（｛ｘ1＝２｝，４０００，２）
ｈ3とのｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージ：（｛ｘ1＝２｝，４０００，２）
送信メッセージ：
ｈ2へのメッセージ：ｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（｛ｘ1＝２｝，４０００，２）
ｈ3へのメッセージ：ｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（｛ｘ1＝２｝，４０００，２）
となる。具体的には、当該ｌｏｃａｌ＿ｍａｘメッセージの受信記録をすべて削除し、その代わりに、全隣接ホストに対し、ｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（｛ｘ1＝２｝，４０００，２）メッセージを送信し、その送信した内容を上記のように記憶する。この場合にのみ送受信の区別なく記録する点が他の受信メッセージ記録と異なる。
４．ｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（｛ｘ1＝２｝，４０００，２）メッセージ受信時の処理の例：
ここでは二つのホストｈ1、ｈ2での動作を説明する。このメッセージにおいて、メッセージの最後の要素と一致するｈ2を起点ホストと呼び、それ以外のこのメッセージを受信するホストを中継ホストと呼ぶ。なお、この例においては、ｈ1はｈ3からこのメッセージを受信するものとし、ｈ2はｈ1から受信するものとする。
（ａ）中継ホストｈ1：
まず、受信メッセージを記録するが、この例ではｈ3へ既に同じメッセージを送信済の場合には何もせず、そうでない場合にのみ、このメッセージを記録する。そして、これが最初のｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（｛ｘ1＝２｝，４０００，２）の受信の場合には、過去にｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２｝，４０００，２）を送信してきているホストに対してｈ1からもｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２｝，４０００，２）を送信していれば（最初にｌｏｃａｌ＿ｍａｘ（｛ｘ1＝２｝，４０００，２）を受信したときの処理により、それを送信してきたホスト以外へは送信しているはずで、その最初に送信してきたホストは記録されているので判断できる）、受信したｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（｛ｘ1＝２｝，４０００，２）を送信し、送信を記録する。
【００９８】
この時点でｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（｛ｘ1＝２｝，４０００，２）を未送信の隣接ホスト数が１であれば、そこへこのメッセージを送信するが、２以上であれば、それらからｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（｛ｘ1＝２｝，４０００，２）が送られてくるのを待つ。この例における内部状態の変化は基本的にメッセージに記憶領域だけであり、送信メッセージも内容は受信メッセージと同じでどこへ送信するかという問題だけで、状況によって変化するので、特定の状況における具体的な内部状態や送信メッセージの明示は省略する。
（ｂ）起点ホストｈ2：
受信メッセージを記録する。その時点で、すべての隣接ホストから同じメッセージを受信し終わっていれば、そのメッセージに含まれる状態とその目的関数値が確定したことになる。この状態がｈa0の負荷量を減らしていて、かつ、暫定解ｙよりも小さい場合には、暫定解を更新すると同時にｕｐｄａｔｅメッセージを全隣接ホストに送信する。
【００９９】
暫定解が更新されれば、Ｓ中の状態のなかには限定操作を適用されて削除される状態もある。その場合には、必要に応じてｂｏｕｎｄメッセージを送信する。一方、この状態がｈa0には何の影響を与えておらず、かつ、受信メッセージに添付されている目的関数値が暫定解ｙよりも小さい場合には、その状態と値をｌｏｃａｌ＿ｉｍｐｒｏｖｅメッセージに入れてｈa0へ送る。
【０１００】
この例において、内部状態が大きく変化するのは暫定解が更新される場合である。そのため、ここではそのような状況に限定して実際の例を簡略化したものを示す。ここでは、ホストｈ2の隣接ホストはｈ1のみとする。まず、メッセージ受信前の状態を下記に示す。
内部状態：
・ｙ0＝１００００
・ａ0＝１
・ｙ＝１００００
・ａ＝１
・Ｉ＝｛｝
・Ｓ＝｛ｘ0（１００００），｛ｘ1＝２｝（４０００），｛ｘ2＝２｝（５０００），｛ｘ1＝２，ｘ2＝２｝（９０００）｝
・Ｓ′＝｛｝
・受信メッセージ記憶領域：
ｈ1からのｍｉｇｒａｔｅメッセージ：｛（ｘ1，ｘ0）；（ｘ２，ｘ0）｝この状態で、ｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（｛ｘ1＝２｝，４０００，２）を受信すると、下記のような状態に変化する。
内部状態：
・ｙ0＝１００００
・ａ0＝１
・ｙ＝４０００
・ａ＝２
・Ｉ＝｛｝
・Ｓ＝｛｛ｘ1＝２｝（４０００）｝
・Ｓ′＝｛ｘ0｝
受信メッセージ記憶領域：
ｈ1からのｍｉｇｒａｔｅメッセージ：｛（ｘ1，ｘ0）｝
ｈ1からのｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージ：｛｝
送信メッセージ：
ｈ1へのメッセージ：ｕｐｄａｔｅ（４０００，２）、ｂｏｕｎｄ（｛ｘ2＝２s｝，２）
【０１０１】
このように変化する経緯を説明する。まず、ｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（｛ｘ1  ＝２｝，４０００，２）を受信したことにより、ｈ2の次数が１でｘ1はｈa0＝ｈ1から移動してきている（ｈa0の負荷量を変化させている）ので、｛ｘ1＝２｝という状態における目的関数値が４０００であることが確定したことがわかる。このメッセージは一旦は記録されるが後の処理で削除されるので、結局受信メッセージ記憶領域は上記のようになる。
【０１０２】
｛ｘ1＝２｝が４０００なので、暫定解ｙをこの値に更新し、ａも自身のＩＤに更新する。暫定解が更新されたのでｕｐｄａｔｅ（４０００，２）を送信する。次いで、Ｓから４０００を越える目的関数値の状態を削除し、値が固定されていないものを除けば４０００以下になる可能性のあるものはＳ′に移動する。その結果、この例においてはＳからｘ0（１００００），｛ｘ2＝２｝（５０００），｛ｘ1＝２，ｘ2＝２｝（９０００）が削除され、ｘ0がＳ′へ追加される。これにより、ｘ2はもうすべての割当の可能性がなくなったので、ｈ1にその旨を知らせるためにｂｏｕｎｄ（｛ｘ2＝２s｝，２）をｈ1へ送信する。なお、｛ｘ1＝２，ｘ2＝２｝も削除されているが、ｘ2のｈ1からの移動がなくなればこの状態もなくなるので、｛ｘ1＝２，ｘ2＝２｝に対する特別な処理は不要である。
５．ｌｏｃａｌ＿ｉｍｐｒｏｖｅ（ｓ，ｙ′）メッセージ受信時の処理の例
（ａ）中継ホスト：
ｙ′＜ｙであれば、内部状態に依存せずそのままｈa0への送信（中継）を行う。ただし、もしこのメッセージに含まれる状態がＳまたはＳ′に含まれていないのであれば、ＳかＳ′へ追加するが、対応するｌｏｃａｌ＿ｍａｘ（ｓ，ｙ′，＊）メッセージを受信していれば既にＳかＳ′へ追加されているはずなので、これに関する動作はｌｏｃａｌ＿ｍａｘ（ｓ，ｙ′，＊）メッセージ受信時の動作の一部と同じになる。そのため、ここでは具体例は示さない。
（ｂ）ｈa0：
ｙ（ｓ），ｙ′，ｙの関係により、ｓをＳかＳ′に加えるか、あるいは限定されるが、対応するｌｏｃａｌ＿ｍａｘ（ｓ，ｙ′；＊）メッセージを受信していれば既にＳかＳ′へ追加されているはずなので、これに関する動作はｌｏｃａｌ＿ｍａｘ（ｓ，ｙ′，＊）メッセージ受信時の動作の一部と同じになる。そのため、ここでは具体例は示さない。結局のところ、ｌｏｃａｌ＿ｍａｘ、ｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージが全ホストを通過してその過程で各ホストに状態が追加される状況においてはこのメッセージの必要性は低いが、マルチキャストを用いて各状態の目的関数値を計算する場合には必須になる。
６．ｕｐｄａｔｅ（ｙ′，ａ′）メッセージ受信時の処理の例：
ｙ≦ｙ′であれば何もしない。以下の処理はｙ＞ｙ′の場合に限られる。まず、暫定解が更新され、受信メッセージを転送すると共にそれに伴う状態の削除を行う。さらに、削除された状態があっても暫定解更新メッセージだけでは隣接ホストにその削除が伝わらない場合には限定メッセージを送信することになる。下記にそのような状況が起こる簡略化した例を示す。まず受信前のホストｈ1の状態を示す。
内部状態：
・ｙ＝１００００
・ａ＝２
・Ｉ＝｛｛ｘ1＝２s｝，｛ｘ1＝３s｝，｛ｘ2＝２s｝，｛ｘ2＝３s｝｝
・Ｓ＝｛ｘ0（１００００），｛ｘ1＝３s，ｘ3＝１｝（９０００），｛ｘ2＝３s，ｘ3＝１｝（８０００），｛ｘ3＝３s｝（１００００），｛ｘ1＝２｝（６０００），｛ｘ1＝２，ｘ3＝１｝（９０００），｛ｘ1＝２，ｘ2＝３s，ｘ3＝１｝（３０００），｛ｘ1＝２，ｘ3＝３s｝（３９００），｛ｘ1＝２，ｘ2＝３s｝（０），｛ｘ1＝３｝（４０００），｛ｘ1＝３，ｘ3＝１｝（９０００），｛ｘ1＝３，ｘ2＝３s，ｘ3＝１｝（３０００），｛ｘ1＝３，ｘ3＝３s｝（３９００），｛ｘ1＝３，ｘ2＝３s｝（０）｝
・Ｓ′＝｛ｘ3＝１｝
・受信メッセージ記憶領域：
ｈ2からのｍｉｇｒａｔｅメッセージ：｛（ｘ3，ｘ0）｝
ｈ2とのｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージ：（｛ｘ1＝２｝，６０００）
ｈ3とのｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージ：（｛ｘ1＝３｝，４０００）
この状態において、ｈ3からｕｐｄａｔｅ（４０００，３）を受信した場合には、下記のような状態になる。
内部状態：
・ｙ＝４０００
・ａ＝３
・Ｉ＝｛｛ｘ1＝２s｝，｛ｘ1＝３s｝，｛ｘ2＝２s｝，｛ｘ2＝３s｝｝
・Ｓ＝｛｛ｘ1＝２，ｘ2＝３s，ｘ3＝１｝（３０００），｛ｘ1＝２，ｘ3＝３s｝（３９００），｛ｘ1＝２，ｘ2＝３s｝（０），｛ｘ1＝３｝（４０００），｛ｘ1＝３，ｘ2＝３s，ｘ3＝１｝（３０００），｛ｘ1＝３，ｘ3＝３s｝（３９００），｛ｘ1＝３，ｘ2＝３s｝（０）｝
・Ｓ′＝｛｛ｘ3＝１｝，ｘ0，｛ｘ1＝３s，ｘ3＝１｝，｛ｘ2＝３s，ｘ3＝１｝，｛ｘ3＝３s｝，｛ｘ1＝２｝，｛ｘ1＝２，ｘ3＝１｝，｛ｘ1＝３，ｘ3＝１｝｝
受信メッセージ記憶領域：
ｈ2からのｍｉｇｒａｔｅメッセージ：｛（ｘ3，ｘ0）｝
ｈ2とのｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージ：｛｝
ｈ3とのｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージ：（｛ｘ1＝３｝，４０００）
送信メッセージ：
ｈ2へのメッセージ：ｕｐｄａｔｅ（４０００，３）
ｈ3へのメッセージ：
【０１０３】
上記のようになった経緯を説明する。まず、ｙとａを更新して受信メッセージを転送する。その後、Ｓから４０００を越える負荷量の状態を削除し、固定されている割当だけなら４０００を越えない（判断不能も含む）ものをＳ′へ移す。この例においては、固定された割当だけではっきりと４０００を越えるものはなかったので、Ｓから削除された状態はすべてＳ′へ移動している。これら削除された状態で、隣接ホストへの移動を含むものは存在するが、それ自体を送信しているわけではないので、ここでは限定メッセージは送信しないことにする。さらに、記憶領域にある受信メッセージのうち、ｈa0の負荷量を変化させ、かつ、４０００を越える状態に関するもの、この場合にはｈ2へ送信したｌｏｃａｌ＿ｍａｘ＿ｆｉｘ（｛ｘ1＝２｝，６０００）メッセージの情報が削除された。
７．ｂｏｕｎｄ（ｓ，ｉ′）メッセージ受信時の処理の例
（ａ）以前送信したｍｉｇｒａｔｅメッセージに対応した限定：
タスク移動メッセージに対応した限定のため、他のホストへの影響はない。そのため、このメッセージは記録する必要がない。これを受信した場合には、ｈi′に向けて送信した状態ｓに関するタスク移動メッセージが無効になったことを意味するので、ｈi′への移動を含む状態ｓをＳまたはＩから削除する。さらに、この状態削除によりさらに隣接ホストに関連する状態削除が起これば、それに関する限定メッセージを送信する。
【０１０４】
具体的な内部状態の変化にまでは言及しないが、ひとつの動作例として、ｂｏｕｎｄ（｛ｘ3＝３s｝，３）をｈ3から受信したホストｈ1の動作を挙げる隣接ホストｈ2からｍｉｇｒａｔｅ（ｘ3，ｘ0）によって移動してきたｘ3について、ｘ3＝１という状態はＳ′にも入らない、つまり、ｘ3＝１とすると他の変数割当に関わらずｙを越えるときに、ｈ3への移動（ｍｉｇｒａｔｅ（ｘ3，ｘ0））に対してｈ3からその移動についての限定メッセージｂｏｕｎｄ（｛ｘ3＝３s｝，３）が届いた場合を考える。
【０１０５】
この場合には、このホストｈ1においてはもうｘ3の割当に関するあらゆる可能性がなくなったことになる。そのため、元々のｘ3のｈ2からの移動に対して限定メッセージｂｏｕｎｄ（｛ｘ3＝１s｝，１）をｈ2へ送信する。
（ｂ）特定の状態の限定：
受信メッセージを記録して未受信ならば他のホストへ転送する、という以外は上記と同じである。なお、メッセージの記録は閉路の存在などによって同一メッセージがいつまでもシステム中を流れるのを避けるために行われる。上の例と差が小さいため、ここでは具体例は示さない。
（ＩＩ）実行例
ここでは、起動から終了までの動作の一例として、ホスト数４、タスク数３の場合の例を示す。まず、各定数の設定および初期状態を示す。図１３に実行例におけるネットワーク形状と初期配置を示す。
【０１０６】
【数１１】
2006185361.tif 000013
【０１０７】
【数１２】
2006185361.tif 000014
上記設定から得られる暫定解の初期値：
ａ0＝２
ｙ0（＝ｙ2（ｘ0））＝５×（５００＋３００）＋１×５０＋１×４０＝４０９０
実際には非同期システムなので通信が同時に起こることはなく，各サーバｈiの動作も同じように進むことはないが、説明を簡単にする都合上、同期システム（１単位時間で各リンクから１メッセージずつ受信）として扱う。実際のシステムでの動作はメッセージの受信順などによって下記とは異なる動作をするが、最終的に得られる結果は同じである。
【０１０８】
ただし、下記においてはメッセージ受信ひとつにつきアルゴリズムが１回実行されるため、同時に複数の隣接ホストからメッセージを受信した場合にはどれかひとつを先に実行し、その処理が完了してから残りの処理を行う。なお、メッセージの受信順序等に関して制約が緩いため、現実に実現する際には、ほぼ同時に受信したメッセージを一緒に扱うようにしてメッセージ数を減らそうとすることは可能である。以下では時刻をラウンドとして箇条書きの番号で表し、各ラウンドの実行結果となる内部状態とその時点でのメッセージキューの内容を示す。
【０１０９】
【数１３】
2006185361.tif 000015
【０１１０】
【数１４】
2006185361.tif 000016
【０１１１】
【数１５】
2006185361.tif 000017
【０１１２】
【数１６】
2006185361.tif 000018
【０１１３】
【数１７】
2006185361.tif 000019
【０１１４】
【数１８】
2006185361.tif 000020
【０１１５】
【数１９】
2006185361.tif 000021
【０１１６】
【数２０】
2006185361.tif 000022
【０１１７】
【数２１】
2006185361.tif 000023
【０１１８】
【数２２】
2006185361.tif 000024
【０１１９】
【数２３】
2006185361.tif 000025
【０１２０】
【数２４】
2006185361.tif 000026
【０１２１】
【数２５】
2006185361.tif 000027
【０１２２】
【数２６】
2006185361.tif 000028
【０１２３】
【数２７】
2006185361.tif 000029
【０１２４】
【数２８】
2006185361.tif 000030
【０１２５】
【数２９】
2006185361.tif 000031
【０１２６】
【数３０】
2006185361.tif 000032
【０１２７】
【数３１】
2006185361.tif 000033
【０１２８】
【数３２】
2006185361.tif 000034
【０１２９】
【数３３】
2006185361.tif 000035
【０１３０】
【数３４】
2006185361.tif 000036
【０１３１】
【数３５】
2006185361.tif 000037
【０１３２】
【数３６】
2006185361.tif 000038
【０１３３】
【数３７】
2006185361.tif 000039
【０１３４】
【数３８】
2006185361.tif 000040
【０１３５】
【数３９】
2006185361.tif 000041
【０１３６】
【数４０】
2006185361.tif 000042
【０１３７】
【数４１】
2006185361.tif 000043
【０１３８】
【数４２】
2006185361.tif 000044
【０１３９】
【数４３】
2006185361.tif 000045
【０１４０】
【数４４】
2006185361.tif 000046
【０１４１】
【数４５】
2006185361.tif 000047
【０１４２】
【数４６】
2006185361.tif 000048
【０１４３】
【数４７】
2006185361.tif 000049
【０１４４】
【数４８】
2006185361.tif 000050
【０１４５】
【数４９】
2006185361.tif 000051
【０１４６】
【数５０】
2006185361.tif 000052
【０１４７】
【数５１】
2006185361.tif 000053
【０１４８】
【数５２】
2006185361.tif 000054
【０１４９】
【数５３】
2006185361.tif 000055
【０１５０】
【数５４】
2006185361.tif 000056
【０１５１】
【数５５】
2006185361.tif 000057
【０１５２】
【数５６】
2006185361.tif 000058
【０１５３】
【数５７】
2006185361.tif 000059
【０１５４】
【数５８】
2006185361.tif 000060
【０１５５】
【数５９】
2006185361.tif 000061
【０１５６】
【数６０】
2006185361.tif 000062
【０１５７】
【数６１】
2006185361.tif 000063
【０１５８】
【数６２】
2006185361.tif 000064
【０１５９】
【数６３】
2006185361.tif 000065
【０１６０】
【数６４】
2006185361.tif 000066
【０１６１】
【数６５】
2006185361.tif 000067
【０１６２】
【数６６】
2006185361.tif 000068
【０１６３】
【数６７】
2006185361.tif 000069
【０１６４】
【数６８】
2006185361.tif 000070
【０１６５】
【数６９】
2006185361.tif 000071
【０１６６】
【数７０】
2006185361.tif 000072
【０１６７】
【数７１】
2006185361.tif 000073
【０１６８】
【数７２】
2006185361.tif 000074
【０１６９】
【数７３】
2006185361.tif 000075
【０１７０】
【数７４】
2006185361.tif 000076
【０１７１】
【数７５】
2006185361.tif 000077
【０１７２】
【数７６】
2006185361.tif 000078
【０１７３】
【数７７】
2006185361.tif 000079
【０１７４】
【数７８】
2006185361.tif 000080
【０１７５】
【数７９】
2006185361.tif 000081
【０１７６】
【数８０】
2006185361.tif 000082
【０１７７】
【数８１】
2006185361.tif 000083
【０１７８】
【数８２】
2006185361.tif 000084
【０１７９】
【数８３】
2006185361.tif 000085
【０１８０】
【数８４】
2006185361.tif 000086
【０１８１】
【数８５】
2006185361.tif 000087
【０１８２】
【数８６】
2006185361.tif 000088
【０１８３】
【数８７】
2006185361.tif 000089
【０１８４】
【数８８】
2006185361.tif 000090
【０１８５】
【数８９】
2006185361.tif 000091
【０１８６】
【数９０】
2006185361.tif 000092
【０１８７】
【数９１】
2006185361.tif 000093
【０１８８】
【数９２】
2006185361.tif 000094
【０１８９】
【数９３】
2006185361.tif 000095
【０１９０】
【数９４】
2006185361.tif 000096
【０１９１】
【数９５】
2006185361.tif 000097
【０１９２】
【数９６】
2006185361.tif 000098
【０１９３】
【数９７】
2006185361.tif 000099
【０１９４】
【数９８】
2006185361.tif 000100
【０１９５】
【数９９】
2006185361.tif 000101
【０１９６】
【数１００】
2006185361.tif 000102
【０１９７】
【数１０１】
2006185361.tif 000103
【０１９８】
【数１０２】
2006185361.tif 000104
【０１９９】
【数１０３】
2006185361.tif 000105
【０２００】
【数１０４】
2006185361.tif 000106
【０２０１】
【数１０５】
2006185361.tif 000107
【０２０２】
【数１０６】
2006185361.tif 000108
【０２０３】
【数１０７】
2006185361.tif 000109
【０２０４】
【数１０８】
2006185361.tif 000110
【０２０５】
【数１０９】
2006185361.tif 000111
【０２０６】
【数１１０】
2006185361.tif 000112
【０２０７】
【数１１１】
2006185361.tif 000113
【０２０８】
【数１１２】
2006185361.tif 000114
【０２０９】
【数１１３】
2006185361.tif 000115
【０２１０】
【数１１４】
2006185361.tif 000116
【０２１１】
【数１１５】
2006185361.tif 000117
【０２１２】
【数１１６】
2006185361.tif 000118
【０２１３】
【数１１７】
2006185361.tif 000119
【０２１４】
【数１１８】
2006185361.tif 000120
【０２１５】
【数１１９】
2006185361.tif 000121
【０２１６】
【数１２０】
2006185361.tif 000122
【０２１７】
【数１２１】
2006185361.tif 000123
【０２１８】
【数１２２】
2006185361.tif 000124
【０２１９】
【数１２３】
2006185361.tif 000125
【０２２０】
【数１２４】
2006185361.tif 000126
【０２２１】
【数１２５】
2006185361.tif 000127
【０２２２】
【数１２６】
2006185361.tif 000128
【０２２３】
【数１２７】
2006185361.tif 000129
【０２２４】
【数１２８】
2006185361.tif 000130
【０２２５】
【数１２９】
2006185361.tif 000131
【０２２６】
【数１３０】
2006185361.tif 000132
【０２２７】
【数１３１】
2006185361.tif 000133
【０２２８】
【数１３２】
2006185361.tif 000134
【０２２９】
【数１３３】
2006185361.tif 000135
【０２３０】
【数１３４】
2006185361.tif 000136
【０２３１】
【数１３５】
2006185361.tif 000137
【０２３２】
【数１３６】
2006185361.tif 000138
【０２３３】
【数１３７】
2006185361.tif 000139
【０２３４】
【数１３８】
2006185361.tif 000140
【０２３５】
【数１３９】
2006185361.tif 000141
【０２３６】
【数１４０】
2006185361.tif 000142
【０２３７】
【数１４１】
2006185361.tif 000143
【０２３８】
【数１４２】
2006185361.tif 000144
【０２３９】
【数１４３】
2006185361.tif 000145
【０２４０】
【数１４４】
2006185361.tif 000146
【０２４１】
【数１４５】
2006185361.tif 000147
【０２４２】
【数１４６】
2006185361.tif 000148
【０２４３】
【数１４７】
2006185361.tif 000149
【０２４４】
【数１４８】
2006185361.tif 000150
【０２４５】
【数１４９】
2006185361.tif 000151
【０２４６】
【数１５０】
2006185361.tif 000152
【０２４７】
【数１５１】
2006185361.tif 000153
【０２４８】
【数１５２】
2006185361.tif 000154
【０２４９】
【数１５３】
2006185361.tif 000155
【０２５０】
【数１５４】
2006185361.tif 000156
【０２５１】
【数１５５】
2006185361.tif 000157
【０２５２】
【数１５６】
2006185361.tif 000158
【０２５３】
【数１５７】
2006185361.tif 000159
【０２５４】
【数１５８】
2006185361.tif 000160
【０２５５】
【数１５９】
2006185361.tif 000161
【０２５６】
【数１６０】
2006185361.tif 000162
【０２５７】
【数１６１】
2006185361.tif 000163
【０２５８】
【数１６２】
2006185361.tif 000164
【０２５９】
【数１６３】
2006185361.tif 000165
【０２６０】
【数１６４】
2006185361.tif 000166
【０２６１】
【数１６５】
2006185361.tif 000167
【０２６２】
【数１６６】
2006185361.tif 000168
【０２６３】
【数１６７】
2006185361.tif 000169
【０２６４】
【数１６８】
2006185361.tif 000170
【０２６５】
【数１６９】
2006185361.tif 000171
【０２６６】
【数１７０】
2006185361.tif 000172
【０２６７】
【数１７１】
2006185361.tif 000173
【０２６８】
【数１７２】
2006185361.tif 000174
【０２６９】
【数１７３】
2006185361.tif 000175
【０２７０】
【数１７４】
2006185361.tif 000176
【０２７１】
【数１７５】
2006185361.tif 000177
【０２７２】
【数１７６】
2006185361.tif 000178
【０２７３】
【数１７７】
2006185361.tif 000179
【０２７４】
【数１７８】
2006185361.tif 000180
【０２７５】
【数１７９】
2006185361.tif 000181
【０２７６】
【数１８０】
2006185361.tif 000182
【０２７７】
【数１８１】
2006185361.tif 000183
【０２７８】
【数１８２】
2006185361.tif 000184
【０２７９】
【数１８３】
2006185361.tif 000185
【０２８０】
【数１８４】
2006185361.tif 000186
【０２８１】
【数１８５】
2006185361.tif 000187
【０２８２】
【数１８６】
2006185361.tif 000188
【０２８３】
【数１８７】
2006185361.tif 000189
【０２８４】
【数１８８】
2006185361.tif 000190
【０２８５】
【数１８９】
2006185361.tif 000191
【０２８６】
【数１９０】
2006185361.tif 000192
【０２８７】
【数１９１】
2006185361.tif 000193
【０２８８】
【数１９２】
2006185361.tif 000194
【０２８９】
【数１９３】
2006185361.tif 000195
【０２９０】
【数１９４】
2006185361.tif 000196
【０２９１】
【数１９５】
2006185361.tif 000197
【０２９２】
【数１９６】
2006185361.tif 000198
【０２９３】
【数１９７】
2006185361.tif 000199
【０２９４】
【数１９８】
2006185361.tif 000200
【０２９５】
【数１９９】
2006185361.tif 000201
【０２９６】
【数２００】
2006185361.tif 000202
【０２９７】
【数２０１】
2006185361.tif 000203
【０２９８】
【数２０２】
2006185361.tif 000204
【０２９９】
【数２０３】
2006185361.tif 000205
【０３００】
【数２０４】
2006185361.tif 000206
【０３０１】
【数２０５】
2006185361.tif 000207
【０３０２】
【数２０６】
2006185361.tif 000208
【０３０３】
【数２０７】
2006185361.tif 000209
【０３０４】
【数２０８】
2006185361.tif 000210
【０３０５】
【数２０９】
2006185361.tif 000211
【０３０６】
【数２１０】
2006185361.tif 000212
【０３０７】
【数２１１】
2006185361.tif 000213
【０３０８】
【数２１２】
2006185361.tif 000214
【０３０９】
【数２１３】
2006185361.tif 000215
【０３１０】
【数２１４】
2006185361.tif 000216
【０３１１】
【数２１５】
2006185361.tif 000217
【０３１２】
【数２１６】
2006185361.tif 000218
【０３１３】
【数２１７】
2006185361.tif 000219
【０３１４】
【数２１８】
2006185361.tif 000220
【０３１５】
【数２１９】
2006185361.tif 000221
【０３１６】
【数２２０】
2006185361.tif 000222
【０３１７】
【数２２１】
2006185361.tif 000223
【０３１８】
【数２２２】
2006185361.tif 000224
【０３１９】
【数２２３】
2006185361.tif 000225
【０３２０】
【数２２４】
2006185361.tif 000226
【０３２１】
【数２２５】
2006185361.tif 000227
【０３２２】
【数２２６】
2006185361.tif 000228
【０３２３】
【数２２７】
2006185361.tif 000229
【０３２４】
【数２２８】
2006185361.tif 000230
【０３２５】
【数２２９】
2006185361.tif 000231
【０３２６】
【数２３０】
2006185361.tif 000232
【０３２７】
【数２３１】
2006185361.tif 000233
【０３２８】
【数２３２】
2006185361.tif 000234
【０３２９】
【数２３３】
2006185361.tif 000235
【０３３０】
【数２３４】
2006185361.tif 000236
【０３３１】
【数２３５】
2006185361.tif 000237
【０３３２】
【数２３６】
2006185361.tif 000238
【０３３３】
【数２３７】
2006185361.tif 000239
【０３３４】
【数２３８】
2006185361.tif 000240
【０３３５】
【数２３９】
2006185361.tif 000241
【０３３６】
【数２４０】
2006185361.tif 000242
【０３３７】
【数２４１】
2006185361.tif 000243
【０３３８】
【数２４２】
2006185361.tif 000244
【０３３９】
【数２４３】
2006185361.tif 000245
【０３４０】
【数２４４】
2006185361.tif 000246
【０３４１】
【数２４５】
2006185361.tif 000247
【０３４２】
【数２４６】
2006185361.tif 000248
【０３４３】
【数２４７】
2006185361.tif 000249
【０３４４】
【数２４８】
2006185361.tif 000250
【０３４５】
【数２４９】
2006185361.tif 000251
【０３４６】
【数２５０】
2006185361.tif 000252
【０３４７】
【数２５１】
2006185361.tif 000253
【０３４８】
【数２５２】
2006185361.tif 000254
【０３４９】
【数２５３】
2006185361.tif 000255
【０３５０】
【数２５４】
2006185361.tif 000256
【０３５１】
【数２５５】
2006185361.tif 000257
【０３５２】
【数２５６】
2006185361.tif 000258
【０３５３】
【数２５７】
2006185361.tif 000259
【０３５４】
【数２５８】
2006185361.tif 000260
【０３５５】
【数２５９】
2006185361.tif 000261
【０３５６】
【数２６０】
2006185361.tif 000262
【０３５７】
【数２６１】
2006185361.tif 000263
【０３５８】
【数２６２】
2006185361.tif 000264
【０３５９】
【数２６３】
2006185361.tif 000265
【０３６０】
【数２６４】
2006185361.tif 000266
【０３６１】
【数２６５】
2006185361.tif 000267
【０３６２】
【数２６６】
2006185361.tif 000268
【０３６３】
【数２６７】
2006185361.tif 000269
【０３６４】
【数２６８】
2006185361.tif 000270
【０３６５】
【数２６９】
2006185361.tif 000271
【０３６６】
【数２７０】
2006185361.tif 000272
【０３６７】
【数２７１】
2006185361.tif 000273
【０３６８】
【数２７２】
2006185361.tif 000274
【０３６９】
【数２７３】
2006185361.tif 000275
【０３７０】
【数２７４】
2006185361.tif 000276
【０３７１】
【数２７５】
2006185361.tif 000277
【０３７２】
【数２７６】
2006185361.tif 000278
【０３７３】
【数２７７】
2006185361.tif 000279
【０３７４】
【数２７８】
2006185361.tif 000280
【０３７５】
【数２７９】
2006185361.tif 000281
【０３７６】
【数２８０】
2006185361.tif 000282
【０３７７】
【数２８１】
2006185361.tif 000283
【０３７８】
【数２８２】
2006185361.tif 000284
【０３７９】
【数２８３】
2006185361.tif 000285
【０３８０】
【数２８４】
2006185361.tif 000286
【０３８１】
【数２８５】
2006185361.tif 000287
【０３８２】
【数２８６】
2006185361.tif 000288
【０３８３】
【数２８７】
2006185361.tif 000289
【０３８４】
【数２８８】
2006185361.tif 000290
【０３８５】
【数２８９】
2006185361.tif 000291
【０３８６】
【数２９０】
2006185361.tif 000292
【０３８７】
【数２９１】
2006185361.tif 000293
【０３８８】
【数２９２】
2006185361.tif 000294
【０３８９】
【数２９３】
2006185361.tif 000295
【０３９０】
【数２９４】
2006185361.tif 000296
【０３９１】
【数２９５】
2006185361.tif 000297
【０３９２】
【数２９６】
2006185361.tif 000298
【０３９３】
【数２９７】
2006185361.tif 000299
【０３９４】
【数２９８】
2006185361.tif 000300
【０３９５】
【数２９９】
2006185361.tif 000301
【０３９６】
【数３００】
2006185361.tif 000302
【０３９７】
【数３０１】
2006185361.tif 000303
【０３９８】
【数３０２】
2006185361.tif 000304
【０３９９】
【数３０３】
2006185361.tif 000305
【０４００】
【数３０４】
2006185361.tif 000306
【０４０１】
【数３０５】
2006185361.tif 000307
【０４０２】
【数３０６】
2006185361.tif 000308
【０４０３】
【数３０７】
2006185361.tif 000309
【０４０４】
【数３０８】
2006185361.tif 000310
【０４０５】
【数３０９】
2006185361.tif 000311
【０４０６】
【数３１０】
2006185361.tif 000312
【０４０７】
【数３１１】
2006185361.tif 000313
【０４０８】
【数３１２】
2006185361.tif 000314
【０４０９】
【数３１３】
2006185361.tif 000315
【０４１０】
【数３１４】
2006185361.tif 000316
【０４１１】
【数３１５】
2006185361.tif 000317
【０４１２】
【数３１６】
2006185361.tif 000318
【０４１３】
【数３１７】
2006185361.tif 000319
【０４１４】
【数３１８】
2006185361.tif 000320
この状態において、システム中にメッセージがなく、全ホストでｙ＝２５５０，ａ＝２となったので、ｈ2でｙ2＝２５５０となる状態｛ｘ3＝４｝が解となる。
【産業上の利用可能性】
【０４１５】
本発明により、非同期完全分散環境において全情報を単一サーバに集約させず、かつ、システムを制御する唯一の存在もない状況において、最適解を求めることが可能となる。これによりネットワークの有効利用を図ることができる。
【０４１６】
また、ホストやリンクの故障やメッセージ消失などに対する耐故障性や、メッセージの順番の入れ替えに対する頑健性、ホスト毎の動作の自律性（自由度の大きさ）、他手法との融合により信頼性および自由度の大きいネットワークを実現することができる。
【図面の簡単な説明】
【０４１７】
【図１】本実施例のサーバのブロック構成図。
【図２】起動直後の処理を示すフローチャート。
【図３】メッセージ受信により起動される処理を示すフローチャート。
【図４】ｕｐｄａｔｅ（暫定解更新）メッセージ受信時の処理を示すフローチャート（その１）。
【図５】ｕｐｄａｔｅ（暫定解更新）メッセージ受信時の処理を示すフローチャート（その２）。
【図６】ｍｉｇｒａｔｅ（タスク移動）メッセージ受信時の処理を示すフローチャート。
【図７】ｌｏｃａｌ＿ｍａｘメッセージ受信時の処理を示すフローチャート（その１）。
【図８】ｌｏｃａｌ＿ｍａｘメッセージ受信時の処理を示すフローチャート（その２）。
【図９】ｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージ受信時の処理を示すフローチャート（その１）。
【図１０】ｌｏｃａｌ＿ｍａｘ＿ｆｉｘメッセージ受信時の処理を示すフローチャート（その２）。
【図１１】ｌｏｃａｌ＿ｉｍｐｒｏｖｅメッセージ受信時の処理を示すフローチャート。
【図１２】ｂｏｕｎｄ（限定）メッセージ受信時の処理を示すフローチャート。
【図１３】実行例におけるネットワーク形状と初期配置を示す図。
【符号の説明】
【０４１８】
１  タスク実行負荷情報受信部
２  タスク実行負荷情報取得部
３  タスク実行負荷情報蓄積部
４  タスク実行負荷情報送信部
５  総合負荷情報算出部
６  タスク移動情報送信部
７  ＣＰＵ負荷算出部
８  通信負荷算出部
９  移動負荷算出部
１０  タスク識別子格納部
１１  ＣＰＵ負荷情報格納部
１２  通信負荷情報格納部
１３  プログラムサイズ情報格納部
１４  評価不要情報送信部
１５  評価不要情報受信部
【図１】
2006185361.tif 000321
【図２】
2006185361.tif 000322
【図３】
2006185361.tif 000323
【図４】
2006185361.tif 000324
【図５】
2006185361.tif 000325
【図６】
2006185361.tif 000326
【図７】
2006185361.tif 000327
【図８】
2006185361.tif 000328
【図９】
2006185361.tif 000329
【図１０】
2006185361.tif 000330
【図１１】
2006185361.tif 000331
【図１２】
2006185361.tif 000332
【図１３】
2006185361.tif 000333