(57)【要約】分散処理におけるイベントデータ配送性能を向上する。  通信ネットワークを介して互いに接続している複数の分散処理装置毎に個別に与えられている識別子としてのキーを含む複数のキーが予め定められている順番で並んでいるキー空間における複数の前記識別子としてのキーの中から選択されたキーをサクセッサの識別子として有するレコードを格納するルーティングテーブルを生成するに際し、前記サクセッサの識別子を決定する際に前記キー空間において基点となる基点キーを互いに異なる２つの手法を利用して算出する。その互いに異なる２つの手法のうちの一つは、前記キー空間を等間隔あるいは略等間隔に分割する分割位置に対応する前記キーを前記基点キーとして算出する分割手法である。
2012124448.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワークを介して互いに接続している複数の分散処理装置毎に個別に与えられている識別子としてのキーを含む複数のキーが予め定められている順番で並んでいるキー空間における複数の前記識別子としてのキーの中から選択されたキーをサクセッサの識別子として有するレコードを格納するルーティングテーブルと、
前記ルーティングテーブルに格納する前記サクセッサの識別子を決定する際に前記キー空間において基点となる基点キーを互いに異なる２つの手法を利用して算出する算出手段と、
前記キー空間において前記基点キーからの予め定められた定義に基づいた距離が最も短い前記識別子としてのキーを検索し、当該キーを前記サクセッサの識別子として前記基点キーと共に有する前記レコードを前記ルーティングテーブルに格納する初期化手段と
を有し、
前記算出手段は、前記互いに異なる２つの手法のうちの一つとして、前記キー空間を等間隔あるいは略等間隔に分割する分割位置に対応する前記キーを前記基点キーとして算出する分割手法を利用するルーティングテーブル生成装置。
【請求項２】
前記キーは、ｍ（ｍは正の整数）ビットの値により表され、
前記値がＫである前記キーから前記キー空間において距離Ｄだけ離れている前記キーの値は、（Ｋ＋Ｄ）ｍｏｄ  ２ｍであると定義されている場合に、
前記算出手段は、基準として定められた前記識別子としてのキーからの距離が２ｊ−１（ｊ＝１，２，．．．，ｍ）である前記キーをそれぞれ前記基点キーとして算出する手法を利用し、さらに、前記分割手法として、予め定められた起点値Ｃ１からの距離が２ｍ×Ｋ／Ｃ２（Ｃ２は予め定められた分割数）（Ｋ＝１，２，．．．，Ｃ２）である位置に対応する値を持つ前記キーを前記基点キーとして算出する手法を利用して、前記基点キーを算出する請求項１に記載のルーティングテーブル生成装置。
【請求項３】
前記初期化手段は、前記ルーティングテーブルに格納されている全ての前記レコードから、他のレコードと前記サクセッサの識別子が重複している前記レコードを除いた前記レコードの数を表す非重複レコード数が予め与えられている上限値に達している場合に、前記ルーティングテーブルに前記レコードを追加しない請求項１又は請求項２に記載のルーティングテーブル生成装置。
【請求項４】
前記算出手段は、算出した複数の前記基点キーに優先順位を設定し、
前記初期化手段は、前記算出手段によって設定された前記優先順位の高い前記基点キーを有する前記レコードから順に前記非重複レコード数が前記上限値に達するまで、前記レコードを前記ルーティングテーブルに格納する請求項３に記載のルーティングテーブル生成装置。
【請求項５】
前記算出手段は、前記分割手法により算出した前記基点キーよりも他方の手法によって算出した前記基点キーの優先順位を高く設定し、前記分割手法により算出した前記基点キーに関しては、前記キー空間を分割する分割数が少ない方の分割位置に対応する基点キーを、分割数が多い方の分割位置に対応する基点キーよりも優先順位を高く設定する請求項４に記載のルーティングテーブル生成装置。
【請求項６】
他のルーティングテーブル生成装置に対して新規の前記レコードを前記ルーティングテーブルに登録することを要求する更新要求データを出力する更新要求手段と、
他のルーティングテーブル生成装置から受信した更新要求データに基づいて前記ルーティングテーブルを更新する必要があると判断した場合に、前記新規のレコードを前記ルーティングテーブルに格納することによって前記ルーティングテーブルを更新し、更新後の前記ルーティングテーブルにおける前記非重複レコード数が前記上限値を超えている場合には、前記優先順位が低い前記基点キーを含む前記レコードから順に、前記非重複レコード数が前記上限値以下になるまで、前記レコードを前記ルーティングテーブルから削除する更新手段と、
をさらに有する請求項４または請求項５に記載のルーティングテーブル生成装置。
【請求項７】
請求項１乃至請求項６のいずれか一つに記載のルーティングテーブル生成装置と、
外部からデータを受信した場合に、前記受信したデータに含まれる情報と、前記ルーティングテーブル生成装置により生成されたルーティングテーブルとに基づいて前記データの転送先を決定し、当該転送先に向けて前記データを転送する転送手段と
を有する分散処理装置。
【請求項８】
複数の、請求項７に記載されている分散処理装置が通信ネットワークを介して互いに接続されている分散処理システム。
【請求項９】
通信ネットワークを介して互いに接続している複数の分散処理装置毎に個別に与えられている識別子としてのキーを含む複数のキーが予め定められている順番で並んでいるキー空間における複数の前記識別子としてのキーの中から選択されたキーをサクセッサの識別子として有するレコードを格納するルーティングテーブルを用意し、
前記ルーティングテーブルに格納する前記サクセッサの識別子を決定する際に前記キー空間において基点となる基点キーを互いに異なる２つの手法を利用して算出し、
前記キー空間において前記基点キーからの予め定められた定義に基づいた距離が最も短い前記識別子としてのキーを検索し、当該キーを前記サクセッサの識別子として前記基点キーと共に有する前記レコードを前記ルーティングテーブルに格納する、
という工程順で前記ルーティングテーブルを生成する途中における前記基点キーを算出する前記互いに異なる２つの手法のうちの一つとして、前記キー空間を等間隔あるいは略等間隔に分割する分割位置に対応する前記キーを前記基点キーとして算出する分割手法を利用するルーティングテーブル生成方法。
【請求項１０】
通信ネットワークを介して互いに接続している複数の分散処理装置毎に個別に与えられている識別子としてのキーを含む複数のキーが予め定められている順番で並んでいるキー空間における複数の前記識別子としてのキーの中から選択されたキーをサクセッサの識別子として有するレコードを格納するルーティングテーブルを用意し、
前記ルーティングテーブルに格納する前記サクセッサの識別子を決定する際に前記キー空間において基点となる基点キーを互いに異なる２つの手法を利用して算出し、
前記キー空間において前記基点キーからの予め定められた定義に基づいた距離が最も短い前記識別子としてのキーを検索し、当該キーを前記サクセッサの識別子として前記基点キーと共に有する前記レコードを前記ルーティングテーブルに格納する、
という工程順で前記ルーティングテーブルを生成する途中における前記基点キーを算出する前記互いに異なる２つの手法のうちの一つとして、前記キー空間を等間隔あるいは略等間隔に分割する分割位置に対応する前記キーを前記基点キーとして算出する分割手法を利用して前記基点キーを算出する制御手順をコンピュータに実行させるコンピュータプログラムを記憶している記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルーティングテーブル生成装置、分散処理装置、分散処理システム、ルーティングテーブル生成方法、および、記憶媒体に関する。
【背景技術】
【０００２】
刻一刻と生成されるイベントデータを高速に処理するシステムとして、分散処理システムが知られている。分散処理システムとは、複数の分散処理装置が相互に連携することにより、イベントデータを分散処理するシステムである。ここでのイベントデータとは、分散処理システムの外部で生成されるデータであり、分散処理システムによって、予め与えられたアプリケーションプログラムに基づいて処理される。
図２６は、一般的な分散処理システムの一例を示すブロック図である。図２６に示す分散処理システムにおいて、各分散処理装置７０は、受信したイベントデータを、他の分散処理装置７０へ転送する機能を有する。各分散処理装置７０は、イベントデータを転送するために、ルーティングテーブル７２を記憶している。そのルーティングテーブル７２には、分散処理システムを構築する複数の分散処理装置７０の中から選択された他の分散処理装置７０のアドレスが書き込まれている。
また、各分散処理装置７０は、イベントデータを最終転送先である分散処理装置７０に到達させるために、予め定めた手順に従って、イベントデータを送付（転送）する宛先（他の分散処理装置７０）を決定する機能を有する。さらに、各分散処理装置７０は、自装置がイベントデータの最終転送先である場合には、そのイベントデータを予め与えられたアプリケーションプログラム７１に基づいて処理する機能を有する。
非特許文献１は、Ｃｈｏｒｄと呼ばれるアルゴリズムを利用した分散処理システムの一例を示している。Ｃｈｏｒｄでは、分散処理システムを構成する各分散処理装置は、識別子として、ｍビット（ｍは正の整数）のキーを保持している。これらのキーは、モジュロ２ｍを利用した環状のキー空間で表現される。図２７は、そのキー空間の一例を概念的に表すイメージ図である。この図２７に示されるキー空間は、ｍ＝３とした場合のキー空間である。当該キー空間では、キーは、０から７までの整数である。これらキー０，・・・，７は、環状に時計回りで小さい数値から大きい数値の順に一列で並んでいる。なお、以下に述べる説明では、キーの数値は符号無し整数で表されるが、コンピュータ処理で用られるので、実際には二進数である。
Ｃｈｏｒｄでは、イベントデータＤからハッシュ関数によってハッシュ値（キー）Ｈが算出される。また、イベントデータＤをアプリケーションプログラムに従って処理する分散処理装置はサクセッサと呼ばれる。当該サクセッサは、イベントデータＤから算出されたハッシュ値（キー）Ｈに基づいて導き出される。なお、以下に述べる説明では、ハッシュ値（キー）Ｈに基づいて導き出されるサクセッサを、サクセッサ（Ｈ）と記載する。
Ｃｈｏｒｄでは、サクセッサ（Ｈ）は、分散処理システムを構成する複数の分散処理装置のうち、前記キー空間においてキーＨからの距離が最も短い識別子（キー）を有する分散処理装置である。
具体的には、Ｃｈｏｒｄでは、キー空間におけるキーＨからの距離（時計回りの距離）がＬであるキーは、（Ｈ＋Ｌ）ｍｏｄ  ２ｍであると定義されている。なお、ｍｏｄは、モジュロ（ｍｏｄｕｌｏ）であり、除算により余りを求める整数演算である。
図２７の例では、識別子としてキー０を持つ分散処理装置と、識別子としてキー１を持つ分散処理装置と、識別子としてキー３を持つ分散処理装置とが分散処理システムを構成しているとする。例えば、キー６から距離が最も短い識別子（キー）を持つ分散処理装置は、キー０を持つ分散処理装置である。換言すれば、キー６からの距離が２であるキーは、（６＋２）ｍｏｄ  ２３＝０（つまり、キー０）である。これにより、サクセッサ（６）は、識別子としてキー０を持つ分散処理装置である。同様に、サクセッサ（１）は、識別子としてキー１を持つ分散処理装置である。また、サクセッサ（２）は、識別子としてキー３を持つ分散処理装置である。
また、Ｃｈｏｒｄでは、分散処理システムを構成している各分散処理装置において、自装置が保持しているキー（識別子）からの距離が２ｊ−１（ｊ＝１，２，．．．，ｍ）であるキーを基点キーＳとしている。各分散処理装置におけるルーティングテーブルに格納される分散処理装置のアドレスは、サクセッサ（Ｓ）のアドレスである。図２８は、分散処理装置が記憶するルーティングテーブル７５の一例を示している。この図２８の例では、ｍ＝８としたキー空間を想定している。また、分散処理装置ＩＤ２１と、分散処理装置ＩＤ６０と、分散処理装置ＩＤ１３１と、分散処理装置ＩＤ１９２とが分散処理システムを構成しているとしている。それら分散処理装置ＩＤ２１，ＩＤ６０，ＩＤ１３１，ＩＤ１９２は、それぞれ、識別子として、キー２１，６０，１３１，１９２を保持している。
例えば、分散処理装置ＩＤ１９２においては、（１９２＋２ｊ−１）ｍｏｄ  ２ｍにより求まる値（キー）が基点キーＳとして設定される。つまり、ｊ＝１，２，．．．，ｍであり、ｍ＝８であるから、分散処理装置ＩＤ１９２における基点キーＳは、図２８に示されるように、１９３，１９４，１９６，２００，２０８，２２４，０，６４である。また、それら基点キーＳに基づいてサクセッサが導き出される。つまり、サクセッサ（１９３，１９４，１９６，２００，２０８，２２４，０）は、分散処理装置ＩＤ２１であり、サクセッサ（６４）は、分散処理装置ＩＤ１３１である。
上記のような基点キーＳと、サクセッサ（Ｓ）に関する情報との組み合わせは、各基点キーＳ毎に、レコードとして、各分散処理装置ＩＤ２１，ＩＤ６０，ＩＤ１３１，ＩＤ１９２のルーティングテーブル７５に格納される。なお、図２８では、ルーティングテーブル７５にサクセッサのアドレスは記載されていないが、実際には、サクセッサ（Ｓ）に関する情報の一つとして、サクセッサのアドレスもルーティングテーブル７５に格納される。ここで、アドレスとは、データ通信時に、通信ネットワークに接続される装置を特定するための情報である。例えば、ＴＣＰ／ＩＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）で通信する場合には、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）アドレスとポート番号のペアがアドレスとなる。
非特許文献２は、別の分散処理システムの一例を開示している。この非特許文献２に記載された分散処理システムでは、分散処理装置は、他の分散処理装置のアドレスを検知すると、そのアドレスを無条件にルーティングテーブルに格納していく。そして、分散処理装置は、格納したアドレス数が所定数を超えた場合に、削除対象としてのアドレスを選択し、選択したアドレスを削除する。このとき、この分散処理装置は、自装置から、格納されている各アドレスに対応する分散処理装置までの距離の分布状態が予め定められた分布となるように、削除対象のアドレスを選択する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｉ．Ｓｔｏｎｉｃａ，Ｒ．Ｍｏｒｒｉｓ，Ｄ．Ｋａｒｇｅｒ，Ｍ．Ｆ．Ｋａａｓｈｏｅｋ，ａｎｄ  Ｈ．Ｂａｌａｋｒｉｓｈｎａｎ，“Ｃｈｏｒｄ：Ａ  Ｓｃａｌａｂｌｅ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｌｏｏｋｕｐ  Ｓｅｒｖｉｃｅ  ｆｏｒ  Ｉｎｔｅｒｎｅｔ  Ａｐｐｌｉｃａｔｉｏｎｓ”，Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ  ＳＩＧＣＯＭＭ，Ａｕｇｕｓｔ  ２００１
【非特許文献２】長尾洋也、首藤一幸，「柔軟な経路表によるオーバレイネットワークの設計」，情報処理学会研究報告（ＩＰＳＪ  ＳＩＧ  Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ）Ｖｏｌ．２０１０．ＯＳ−１１４  Ｎｏ．１１，２０１０年４月，Ｐ１−Ｐ８
【発明の概要】
【発明が解決しようとする課題】
【０００４】
非特許文献１に示されている分散処理システムでは、分散処理装置のメモリリソースが十分に活用されないために、イベントデータが無駄に転送される場合がある。例えば、図２８に示した例では、各分散処理装置は、８つの分散処理装置のアドレスを記憶可能なメモリリソースを有している。換言すれば、各分散処理装置は、分散処理システムを構成する他の全て（図２８の例では３つ）の分散処理装置のアドレスを記憶可能なメモリリソースを有している。
ところが、例えば、分散処理装置ＩＤ６０は、２つの分散処理装置ＩＤ１３１，ＩＤ１９２のアドレスをルーティングテーブル７５に格納しているが、分散処理装置ＩＤ２１のアドレスをルーティングテーブル７５に格納していない。つまり、８つの基本キーＳのうちの７つの基本キーＳ（６１，６２，６４，６８，７６，９２，１２４）に対応するサクセッサ（Ｓ）が同じである。このことから、分散処理装置ＩＤ６０は、ルーティングテーブル７５に同じアドレス（分散処理装置ＩＤ１３１のアドレス）を重複して格納している。
ここで、最終転送先が分散処理装置ＩＤ２１であるイベントデータＡを分散処理装置ＩＤ６０が受け取ったとする。前記のように、分散処理装置ＩＤ６０は、分散処理装置ＩＤ２１のアドレスをルーティングテーブル７５に記憶していないから、イベントデータＡを分散処理装置ＩＤ２１に直接に送信できない。このため、そのイベントデータＡは分散処理装置ＩＤ６０から別の分散処理装置を介して分散処理装置ＩＤ２１に配送されることになる。
上記のように、非特許文献１に記載されている分散処理システムでは、分散処理装置のメモリリソースが十分に活用されないために、イベントデータが無用に転送される場合がある。このような場合には、イベントデータ配送性能（予め定められた単位時間に最終転送先の分散処理装置まで配送（転送）できるイベントデータの数）が低下するという問題が生じる。
一方、非特許文献２に記載されている分散処理システムでは、イベントデータを転送する過程で、分散処理装置が、他の分散処理装置のアドレスを追加したり、削除する。このため、非特許文献２における分散処理システムでは、イベントデータを転送する工程中に転送処理以外の処理が発生する。そのような転送処理以外の処理は、イベントデータ配送性能を低下させる要因となる。つまり、非特許文献２における分散処理システムにおいても、イベントデータ配送性能が低下するという問題がある。
本発明は上記のような課題を解決するためになされたものである。本発明の主な目的は、イベントデータ配送性能を向上できるルーティングテーブル生成装置、分散処理装置、分散処理システム、ルーティングテーブル生成方法、および、記憶媒体を提供することである。
【課題を解決するための手段】
【０００５】
本発明のルーティングテーブル生成装置は、
通信ネットワークを介して互いに接続している複数の分散処理装置毎に個別に与えられている識別子としてのキーを含む複数のキーが予め定められている順番で並んでいるキー空間における複数の前記識別子としてのキーの中から選択されたキーをサクセッサの識別子として有するレコードを格納するルーティングテーブルと、
前記ルーティングテーブルに格納する前記サクセッサの識別子を決定する際に前記キー空間において基点となる基点キーを互いに異なる２つの手法を利用して算出する算出手段と、
前記キー空間において前記基点キーからの予め定められた定義に基づいた距離が最も短い前記識別子としてのキーを検索し、当該キーを前記サクセッサの識別子として前記基点キーと共に有する前記レコードを前記ルーティングテーブルに格納する初期化手段と
を有し、
前記算出手段は、前記互いに異なる２つの手法のうちの一つとして、前記キー空間を等間隔あるいは略等間隔に分割する分割位置に対応する前記キーを前記基点キーとして算出する分割手法を利用する。
本発明の分散処理装置は、
本発明のルーティングテーブル生成装置と、
外部からデータを受信した場合に、前記受信したデータに含まれる情報と、前記ルーティングテーブル生成装置により生成されたルーティングテーブルとに基づいて前記データの転送先を決定し、当該転送先に向けて前記データを転送する転送手段と
を有する。
本発明の分散処理システムは、
本発明の複数の分散処理装置が通信ネットワークを介して互いに接続されている。
本発明のルーティングテーブル生成方法は、
通信ネットワークを介して互いに接続している複数の分散処理装置毎に個別に与えられている識別子としてのキーを含む複数のキーが予め定められている順番で並んでいるキー空間における複数の前記識別子としてのキーの中から選択されたキーをサクセッサの識別子として有するレコードを格納するルーティングテーブルを用意し、
前記ルーティングテーブルに格納する前記サクセッサの識別子を決定する際に前記キー空間において基点となる基点キーを互いに異なる２つの手法を利用して算出し、
前記キー空間において前記基点キーからの予め定められた定義に基づいた距離が最も短い前記識別子としてのキーを検索し、当該キーを前記サクセッサの識別子として前記基点キーと共に有する前記レコードを前記ルーティングテーブルに格納する、
という工程順で前記ルーティングテーブルを生成する途中における前記基点キーを算出する前記互いに異なる２つの手法のうちの一つとして、前記キー空間を等間隔あるいは略等間隔に分割する分割位置に対応する前記キーを前記基点キーとして算出する分割手法を利用する。
本発明の記憶媒体は、
通信ネットワークを介して互いに接続している複数の分散処理装置毎に個別に与えられている識別子としてのキーを含む複数のキーが予め定められている順番で並んでいるキー空間における複数の前記識別子としてのキーの中から選択されたキーをサクセッサの識別子として有するレコードを格納するルーティングテーブルを用意し、
前記ルーティングテーブルに格納する前記サクセッサの識別子を決定する際に前記キー空間において基点となる基点キーを互いに異なる２つの手法を利用して算出し、
前記キー空間において前記基点キーからの予め定められた定義に基づいた距離が最も短い前記識別子としてのキーを検索し、当該キーを前記サクセッサの識別子として前記基点キーと共に有する前記レコードを前記ルーティングテーブルに格納する、
という工程順で前記ルーティングテーブルを生成する途中における前記基点キーを算出する前記互いに異なる２つの手法のうちの一つとして、前記キー空間を等間隔あるいは略等間隔に分割する分割位置に対応する前記キーを前記基点キーとして算出する分割手法を利用して前記基点キーを算出する制御手順をコンピュータに実行させるコンピュータプログラムを記憶している。
【発明の効果】
【０００６】
本発明によれば、イベントデータ配送性能を向上できる。
【図面の簡単な説明】
【０００７】
図１は、本発明に係る第１実施形態の分散処理システムの構成を示すブロック図である。
図２は、第１実施形態の分散処理システムを構成する分散処理装置のハードウェア構成を示すブロック図である。
図３は、第１実施形態における分散処理装置が持つ機能を模式的に示すブロック図である。
図４は、第１実施形態におけるルーティングテーブルの一構造例を説明する図である。
図５は、第１実施形態における分散処理装置が基点キーを算出する動作例を説明するフローチャートである。
図６は、第１実施形態における分散処理装置が検索要求データを送信する動作例を説明するフローチャートである。
図７は、第１実施形態において、検索要求データを受信した分散処理装置の動作例を説明するフローチャートである。
図８は、第１実施形態において、検索応答データを受信した分散処理装置の動作例を説明するフローチャートである。
図９は、第１実施形態における分散処理システムの処理フローを説明するシーケンス図である。
図１０は、本発明に係る第２実施形態の分散処理装置が持つ機能を示すブロック図である。
図１１は、第２実施形態における分散処理装置がデータを転送する動作例を説明するフローチャートである。
図１２は、第２実施形態において、データを受信した分散処理装置の動作例を説明するフローチャートである。
図１３は、第２実施形態における分散処理装置が基点キーを算出する動作例を説明するフローチャートである。
図１４は、第２実施形態において、分散処理装置が検索要求データを送信する動作例を説明するフローチャートである。
図１５は、第２実施形態において、検索要求データを受信した分散処理装置の動作例を説明するフローチャートである。
図１６は、第２実施形態において、検索応答データを受信した分散処理装置の動作例を説明するフローチャートである。
図１７は、第２実施形態における分散処理装置が生成するルーティングテーブルの一例を示す図である。
図１８は、本発明に係る第３実施形態の分散処理装置が持つ機能を示すブロック図である。
図１９は、第３実施形態における分散処理装置が基点キーを算出する動作例を説明するフローチャートである。
図２０は、第３実施形態において、分散処理装置が検索要求データを送信する動作例を説明するフローチャートである。
図２１は、第３実施形態において、分散処理装置が更新要求データを送信する動作例を説明するフローチャートである。
図２２は、第３実施形態において、分散処理装置が更新要求データを転送する動作例を説明するフローチャートである。
図２３は、第３実施形態における分散処理装置がルーティングテーブルを更新する動作例を説明するフローチャートである。
図２４は、第３実施形態において、分散処理システムに新規に参加した分散処理装置が保持するルーティングテーブルを生成する処理フローを説明するシーケンス図である。
図２５は、第３実施形態における分散処理システムがルーティングテーブルを更新する処理例を説明するシーケンス図である。
図２６は、非特許文献１に記載されている分散処理システムの一例を説明するブロック図である。
図２７は、キー空間の一例を説明する図である。
図２８は、分散処理装置が保持するルーティングテーブルの一例を示す図である。
【発明を実施するための形態】
【０００８】
以下に、本発明に係る実施形態を図面を参照して説明する。
（第１実施形態）
図１は、本発明に係る第１実施形態の分散処理システムの構成を示す図である。第１実施形態では、分散処理システム１は、複数の分散処理装置１０を備えている。これら分散処理装置１０は、通信ネットワークを介して互いに接続している。その通信ネットワークは、例えば、インターネット、イントラネット、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、公衆回線網、無線通信網、又は、それらの組合せによって構成されている。なお、図１には、４つの分散処理装置１０が示されているが、本発明に係る分散処理システムを構成する分散処理装置の数は４つに限定されない。
図２は、分散処理装置１０のハードウェア構成を示すブロック図である。図２に示すように、分散処理装置１０は、コンピュータＣ１０を有する。コンピュータＣ１０は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１００１と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１００２と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１００３と、記憶装置（例えばハードディスク装置）１００４と、ネットワークインタフェース１００５とを備えている。
ＲＯＭ１００３は記憶媒体である。記憶装置１００４は記憶媒体１００６を有している。ネットワークインターフェース１００５は、記憶媒体１００７を有している。それら各記憶媒体１００３，１００６，１００７は、それぞれ、適宜なコンピュータプログラム（以下、略してプログラムとも記す）を記憶する。そのプログラムは、分散処理装置１０が実行する制御動作の制御手順を含んでいる。
ＣＰＵ１００１は、コンピュータプログラムを実行することによって、分散処理装置１０の全体的な動作を司る。つまり、ＣＰＵ１００１は、各記憶媒体１００３，１００６，１００７からプログラムを読み出し、この読み出したプログラムをＲＡＭ１００２に書き込む（格納する）。そして、ＣＰＵ１００１は、そのＲＡＭ１００２に格納したプログラムに基づいて制御動作を実行することによって、次のような機能を持つ。
図３にはＣＰＵ１００１の機能がブロック図により示されている。図３に示されるように、ＣＰＵ１００１は、転送部（転送手段）１２と、算出部（算出手段）１３と、初期化部（初期化手段）１４とを有している。また、記憶装置１００４は、ルーティングテープル１１を記憶している。この第１実施形態では、ルーティングテープル１１と、算出部１３と、初期化部１４とによって、ルーティングテーブル生成装置１００が構成されている。
ルーティングテーブル１１には、レコードが格納される。そのレコードは、算出部１３により算出される基点キーＳと、当該基点キーＳに対応するサクセッサとしての分散処理装置１０の識別子との組み合わせを含む。この第１実施形態では、分散処理装置１０は、識別子として、キー空間を構成するキーを保持している。そのキー空間では、複数のキーが、予め定められている順番でもって、例えば図２６に示すように環状に、かつ、一例に並んでいる。分散処理装置１０は、自装置の識別子としてのキーをＲＡＭ１００２あるいは記憶装置１００４に保持している。
なお、キー空間では、距離は次のように定義されている。例えば、或るキーＫ１から他のキーＫ２までの距離は、環状のキー空間を、時計回りと反時計回りのうちの予め定められた一方の方向（例えば時計回り）に、キーＫ１からキーＫ２まで移動した長さであるというように定義されている。
さらに、前記レコードには、サクセッサのアドレスが含まれていてもよい。アドレスとは、通信ネットワークを介して通信する際に、通信ネットワークに接続される装置を特定する情報である。
図４は、ルーティングテーブル１１の一構造例を示している。なお、図４の例では、ルーティングテーブル１１はサクセッサのアドレスを有しているが、ルーティングテーブル１１はサクセッサのアドレスを有していなくともよい。ルーティングテーブル１１がサクセッサのアドレスを有していない場合にサクセッサのアドレスが必要となった際には、分散処理装置１０は、例えば外部からサクセッサのアドレスを取得する。
算出部１３は、基点キーＳを算出する機能を備えている。その基点キーＳとは、ルーティングテーブル１１に格納するサクセッサの識別子を決定する際にキー空間において基点となるキーである。
この第１実施形態では、算出部１３は、互いに異なる２つの算出手法をそれぞれ利用して基点キーＳを算出する。その算出手法の一つは、例えば、非特許文献１に記載されているようなＣｈｏｒｄと呼ばれる技術である。
もう一つの算出手法は、キー空間を等間隔あるいは略等間隔に分割する分割位置に対応するキーを基点キーＳとして算出する手法（ここでは、分割手法と呼ぶ）である。
なお、算出部１３は、基点キーＳを算出する手法として、Ｃｈｏｒｄに代えて、分散処理システムで採用される他の基点キー算出手法を利用してもよい。
初期化部１４は、次のような初期化処理を実行する機能を有している。すなわち、初期化部１４は、初期化処理の一つとして、ルーティングテーブル１１に格納するサクセッサの識別子を取得するために、検索要求データを転送部１２に出力する。検索要求データは、算出部１３により算出された各基点キーＳ毎に作成されるデータである。当該検索要求データは、算出部１３により算出された基点キーＳと、サクセッサ（Ｓ）を検索する要求（指令）と、自装置１０のアドレスとを含む。サクセッサとは、イベントデータを処理する分散処理装置である。この第１実施形態では、サクセッサ（Ｓ）は、基点キーＳからの距離が最も短い識別子（キー）を持つ分散処理装置１０である。
初期化部１４は、さらに別の初期化処理として、転送部１２を介して検索要求データを受け取ると、検索応答データを生成する。なお、後述するように、転送部１２は、外部から受信した検索要求データに含まれている検索対象のサクセッサ（Ｓ）が自装置１０であることを検知した場合のみ、検索要求データを初期化部１４に出力する。
検索応答データは、検索要求データに含まれている基点キーＳと、自装置１０の識別子およびアドレス（つまり、サクセッサ（Ｓ）の識別子およびアドレス）と、検索要求データを発信した要求元のアドレスとを含んでいる。初期化部１４は、生成した検索応答データを転送部１２に出力する。当該検索応答データは転送部１２によって要求元のアドレスに向けて外部に送信される。
初期化部１４は、さらに、別の初期化処理として、外部から転送部１２を介して検索応答データを受け取ると、当該検索応答データに基づいて、レコードをルーティングテーブル１１に登録する。そのレコードは、検索応答データに含まれている基点キーＳと、サクセッサ（Ｓ）の識別子（キー）およびアドレスとの組み合わせを有している。
転送部１２は、データを受信した場合に、そのデータに含まれる情報やルーティングテーブル１１の情報に基づいて定まる送信先に向けて、受信したデータを送信する機能を備えている。転送部１２が受信するデータは、自装置１０の外部から送信されてくる場合もあるし、自装置１０の内部の他の構成部から送信されてくる場合もある。
具体的には、転送部１２は、外部からイベントデータを受信した場合には、自装置１０がそのイベントデータを処理する装置（サクセッサ）であるか否かを判断する。そして、転送部１２は、自装置１０がサクセッサであると判断した場合には、当該イベントデータを処理する処理部（図示せず）に送信する。当該処理部は、記憶装置１００４に予め与えられているアプリケーションプログラムに従ってイベントデータを処理する。
転送部１２は、自装置１０がサクセッサでないと判断した場合には、ルーティングテーブル１１に格納されているサクセッサの情報を利用して、イベントデータを送信（転送）する。当該イベントデータを転送する宛先は、例えば、分散ハッシュテーブル技術を利用して決定することができる。
また、転送部１２は、初期化部１４から検索要求データを受信した場合には、検索要求データを他の分散処理装置１０の一つに向けて送信（転送）する。その転送先も、上記同様に、例えば分散ハッシュテーブル技術を利用して決定することができる。なお、ルーティングテーブル１１に他の分散処理装置１０の情報（サクセッサの情報）が登録されていない場合がある。この場合には、検索要求データを送信する前に、分散処理装置１０は、他の分散処理装置１０のアドレスを取得する。この取得したアドレスを利用して、転送部１２は、検索要求データを送信する。
さらに、転送部１２は、外部（他の分散処理装置１０）から検索要求データを受信した場合には、その検索要求データに含まれている検索対象のサクセッサ（Ｓ）が自装置１０であるか否かを判断する。例えば、転送部１２は、その判断に、自装置１０に対するプレディセッサの識別子を利用する。プレディセッサとは、キー空間において、自装置１０が持つ識別子としてのキーから距離が最も遠いキーを識別子として持つ分散処理装置１０である。当該プレディセッサの識別子（キー）は、予め定められた手法によって自装置１０が他の分散処理装置１０に問い合わせすることによって、取得できる。ここでは、その取得手法の説明は省略する。
転送部１２は、検索要求データに含まれている基点キーＳが、キー空間においてプレディセッサの識別子（キー）から時計回りに回って自装置１０の識別子（キー）に至るまでの範囲内に入っている場合には、自装置１０がサクセッサ（Ｓ）であると判断する。
転送部１２は、自装置１０がサクセッサ（Ｓ）であると判断した場合には、受信した検索要求データを初期化部１４に出力する。これにより、前述したように、初期化部１４が検索応答データを生成する。
転送部１２は、初期化部１４から検索応答データを受信した場合には、検索応答データに含まれている送信先のアドレス（つまり、検索要求データを発信した要求元のアドレス）に基づいて、検索応答データを送信（返信）する。
転送部１２は、外部（他の分散処理装置１０）から検索応答データを受信した場合には、その検索応答データに含まれている情報の中から予め指定されたデータを初期化部１４に出力する。
以下に、分散処理装置１０の動作例を図５−図８を参照して説明する。なお、図５−図８に示されるフローチャートは、分散処理装置１０のＣＰＵ１００１が実行するコンピュータプログラムの制御手順を表す。
例えば、分散処理装置１０が新規に分散処理システム１に参加する場合には、まず、算出部１３が動作する。図５は、算出部１３の動作例を示すフローチャートである。図５に示されるように、算出部１３（ＣＰＵ１００１）は、まず、例えばＣｈｏｒｄ技術を利用して基点キーＳを算出する（ステップＳ１）。次に、算出部１３は、分割手法を利用して、基点キーＳを算出する（ステップＳ２）。さらに、算出部１３は、算出した基点キーＳを初期化部１４に出力する（ステップＳ３）。
算出部１３の動作が終了した後には、初期化部１４が動作する。図６は、初期化部１４の動作例を示すフローチャートである。図６に示されるように、初期化部１４（ＣＰＵ１００１）は、算出部１３から基点キーＳを取得すると（ステップＳ１１）、各基点キーＳ毎に、検索要求データを生成し、続いて検索要求データを転送部１２に出力する（ステップＳ１２）。検索要求データを生成してから送信するまでの処理は、各基点キーＳ毎に、順次繰り返し実行される。
転送部１２は、検索要求データを受け取ると、ルーティングテーブル１１にアドレスが格納されている分散処理装置１０の中から、例えば分散ハッシュテーブル技術を利用して、送信先を決定する。そして、転送部１２は、その決定した送信先のアドレスをルーティングテーブル１１から取得し、当該アドレスに基づいて、検索要求データを送信（転送）する。なお、前述したように、ルーティングテーブル１１に分散処理装置１０のアドレスが格納されていない場合（ルーティングテーブル１１が空の状態である場合）がある。この場合には、分散処理装置１０は、分散処理システム１を構成する他の分散処理装置１０のアドレスを予め定めた手法によって取得し、当該取得したアドレスを利用して、検索要求データを送信（転送）する。
然る後に、分散処理装置１０は、検索要求データに対して返信された検索応答データを受信すると、次のように動作する。図８は、検索応答データを受信した場合における分散処理装置１０の動作例を示すフローチャートである。図８に示されるように、転送部１２は、検索応答データを受信すると（ステップＳ３１）、その検索応答データの中から予め指定されたデータ（例えば、基点キーＳとサクセッサ（Ｓ）の識別子（キー）とサクセッサ（Ｓ）のアドレス）を初期化部１４に出力する。初期化部１４は、受け取ったデータ（基点キーＳとサクセッサ（Ｓ）の識別子（キー）とサクセッサ（Ｓ）のアドレスとの組み合わせ）をレコードとしてルーティングテーブル１１に登録（格納）する（ステップＳ３２）。
分散処理装置１０が新規に分散処理システム１に参加する場合には、当該分散処理装置１０は、上記のような処理を実行する。
次に、分散処理装置１０が検索要求データを受信した場合の動作例を述べる。図７は、分散処理装置１０が検索要求データを受信した場合の動作例を示すフローチャートである。図７に示されるように、転送部１２は、検索要求データを受信すると（ステップＳ２１）、検索要求データに含まれている基点キーＳに基づいて、自装置１０がサクセッサ（Ｓ）であるか否かを判断する（ステップＳ２２）。具体的には、例えば、前述したように、転送部１２は、基点キーＳが、キー空間においてプレディセッサの識別子（キー）から時計回りに回って自装置１０の識別子（キー）に至るまでの範囲内に入っているか否かを判断する。
転送部１２は、自装置１０がサクセッサ（Ｓ）であると判断した場合には、検索要求データを初期化部１４に出力する。これにより、初期化部１４は、検索要求データに基づいて検索応答データを生成する。その検索応答データは、基点キーＳと、サクセッサ（Ｓ）である自装置１０の識別子（キー）およびアドレスと、検索要求データを発信した分散処理装置１０のアドレス（つまり、宛先のアドレス）とを含んでいる。初期化部１４は、その生成した検索応答データを転送部１２に出力する。転送部１２は、その検索応答データに含まれている宛先のアドレスに基づいて、検索応答データを返信（送信）する（ステップＳ２４）。
一方、転送部１２は、自装置１０がサクセッサ（Ｓ）でないと判断した場合には、ルーティングテーブル１１に格納されているアドレスを利用して、分散処理システム１を構成する他の分散処理装置１０に検索応答データを転送する（ステップＳ２３）。
以下に、新規に分散処理装置１０が分散処理システム１に参加する場合における分散処理システム１の処理の流れを述べる。図９は、その分散処理システム１の処理フローを示すシーケンス図である。
まず、新規に参加する分散処理装置（以下、新規の分散処理装置と記す）１０の算出部１３が基点キーＳを算出する（ステップＳ１）。そして、当該新規の分散処理装置１０の初期化部１４は、その算出した基点キーＳに基づいて検索要求データを生成する。そして、転送部１２は、その検索要求データを、分散処理システム１を構成する他の分散処理装置１０に送信する（ステップＳ１２）。
検索要求データを受信した分散処理装置１０は、受信した検索要求データに含まれている基点キーＳに基づいて、自装置１０がサクセッサ（Ｓ）であるか否かを判断する。そして、分散処理装置１０は、サクセッサ（Ｓ）でないと判断した場合には、検索要求データを他の分散処理装置１０に送信（転送）する（ステップＳ２３）。
このように検索要求データが転送されることによって、サクセッサ（Ｓ）である分散処理装置１０に検索要求データが配送される。そして、サクセッサ（Ｓ）が検索要求データを受信すると（ステップＳ２１）、当該サクセッサ（Ｓ）は、検索応答データを生成する。そして、サクセッサ（Ｓ）は、その検索応答データを、新規の分散処理装置１０（検索要求データを発信した分散処理装置１０）に向けて送信（転送）する（ステップＳ２４）。
新規の分散処理装置１０は、検索応答データを受信すると（ステップＳ３１）、その検索応答データに基づいて基点キーＳと、サクセッサ（Ｓ）の識別子（キー）およびアドレスとの組み合わせをレコードとしてルーティングテーブル１１に登録する（ステップＳ３２）。
なお、図９の例では、検索要求データは、新規の分散処理装置１０から１つの他の分散処理装置１０を介してサクセッサ（Ｓ）に送信されている。これに対して、検索要求データは、新規の分散処理装置１０から直接にサクセッサ（Ｓ）に送信される場合がある。また、検索要求データは、新規の分散処理装置１０から複数の他の分散処理装置１０を介してサクセッサ（Ｓ）に送信される場合がある。
以下に、第１実施形態の分散処理システム１および分散処理装置１０から得られる効果を述べる。
すなわち、第１実施形態では、分散処理装置１０（ルーティングテーブル生成装置１００）が持つ算出部１３は、例えばＣｈｏｒｄ技術によって基点キーＳを算出するだけでなく、分割手法によっても基点キーＳを算出する。例えば、キー空間において隣り合う分散処理装置１０の識別子（キー）間の距離が、何れにおいても等しい又は略等しいとする。この場合に、分割手法においてキー空間を分割する分割数が分散処理装置１０の個数以上の数値とすれば、隣り合う分散処理装置１０の識別子（キー）間に必ず少なくとも１つの基点キーＳが設定されることになる。これにより、分散処理装置１０（ルーティングテーブル生成装置１００）は、分散処理システム１を構成する他の全ての分散処理装置１０の識別子をサクセッサ（Ｓ）の識別子としてルーティングテーブル１１に登録できる。このため、分散処理装置１０はメモリリソースを十分に活用できる。換言すれば、分散処理装置１０（ルーティングテーブル生成装置１００）は、メモリリソースを十分に活用できるルーティングテーブル１１を生成できる。
また、この第１実施形態では、分散処理装置１０が上記のようなルーティングテーブル１１を生成するタイミングは、分散処理システム１に新規に参加するときである。このために、分散処理装置１０は、イベントデータを送信（転送）する際に、ルーティングテーブル１１にアドレスを追加する処理やアドレスを削除する処理を行わなくて済む。さらに、分散処理装置１０は、上記のようなルーティングテーブル１１を保持するので、イベントデータを直接に最終宛先の分散処理装置１０（つまり、当該イベントデータを処理するサクセッサ（Ｓ））に転送（配送）できる。上記のようなことから、この第１実施形態の分散処理システム１および分散処理装置１０は、イベントデータ配送性能を向上できる。
（第２実施形態）
以下に、本発明に係る第２実施形態を説明する。なお、この第２実施形態の説明において、第１実施形態と重複する部分の説明は省略する。
図１０は、第２実施形態の分散処理装置の構成を示すブロック図である。この第２実施形態の分散処理装置２０は、図２に示されるような第１実施形態の分散処理装置１０と同様のハードウェア構成を有する。また、この第２実施形態の分散処理装置２０を構成するＣＰＵ１００１は、その機能として、転送部２２と、算出部２３と、初期化部２４と、アプリケーション部２９とを有している。さらに、分散処理装置２０を構成する記憶装置１００４は、ルーティングテーブル２１を保持している。この第２実施形態では、算出部２３と、初期化部２４と、ルーティングテーブル２１とによって、ルーティングテーブル生成装置２００が構成される。この第２実施形態においても、複数の分散処理装置２０は、第１実施形態と同様に、通信ネットワークを介して分散処理システムを構築する。
この第２実施形態の分散処理装置２０は、第１実施形態の分散処理装置１０と同様に、自装置の識別子としてのキーをＲＡＭ１００２あるいは記憶装置１００４に保持している。そのキーは、例えば、ｍ（ｍは正の整数）ビットのハッシュ値である。
ルーティングテーブル２１は、第１実施形態のルーティングテーブル１１と同様の構成を有している。アプリケーション部２９は、記憶装置１００４に予め与えられているアプリケーションプログラムに従った処理を実行する機能を有している。
算出部２３は、例えばＣｈｏｒｄ技術により基点キーＳを算出する。具体的には、算出部２３は、例えば、キー空間において自装置２０の識別子（キー）からの距離が２ｊ−１（ｊ＝１，２，・・・，ｍ）であるキーを基点キーＳとして算出する。
さらに、算出部２３は、第１実施形態における算出部１３と同様に、分割手法によっても基点キーＳを算出する。ここでは、分割手法のより具体例を示す。例えば、算出部２３は、キー空間において、予め定めた起点値Ｃ１からの距離が２ｍ×Ｋ／Ｃ２（Ｋは１，２，・・・，Ｃ２であり、Ｃ２は予め定めた分割数であり、／は除算を表す）であるキーを基点キーＳとして算出する。ここで、起点値Ｃ１は、例えば、自装置２０の識別子（キー）とする。また、隣り合うキー間の距離が、高い確率でＢ以上になると想定される場合には、Ｃ２は２ｍ／Ｂとしてもよい。
なお、起点値Ｃ１からの距離が２ｍ×Ｋ／Ｃ２である値がキー値でない場合には、算出部２３は、近似処理（例えば切り上げ処理）により算出された近似値（キー）を基点キーＳとして算出する。
転送部２２は、第１実施形態における転送部１２と同様の機能を有する。第２実施形態においても、第１実施形態と同様に、転送部２２が転送するデータには、検索要求データや、検索応答データや、イベントデータというような複数種のデータがあるが、この第２実施形態では、単にデータとも記す。転送部２２が転送するデータは、次のような構成を有する。つまり、転送部２２が転送するデータは、キー情報と、サービス識別情報と、メッセージとを含んでいる。
そのサービス識別情報とは、自装置２０の内部におけるデータの送信先（例えば初期化部２４やアプリケーション部２９）を示す情報である。例えば、送信先が初期化部２４である場合には、サービス識別情報は、“初期化”である。また、送信先がアプリケーション部２９である場合には、サービス識別情報は、“アプリケーション”である。
上記メッセージの一例としては、例えば、第１実施形態で述べた検索指令、つまり、サクセッサ（Ｓ）を検索する要求である。検索指令がメッセージとして含まれているデータは、第１実施形態における検索要求データに相当する。
ここで、転送部２２がデータを転送する転送先の分散処理装置２０を決定する手法の一例を説明する。例えば、転送部２２が、キー情報であるキーＱを含むデータを他の分散処理装置２０に転送する場合には、まず、自装置２０の識別子（ここでは、キーＲとする）からキーＱまでの距離ＬＲ−Ｑを求める。そして、転送部２２は、ルーティングテーブル２１に格納されているサクセッサ（Ｓ）の識別子（キー）の中から、キーＱまでの距離が前記距離ＬＲ−Ｑよりも短いキー（ここでは、キーＵとする）を検索する。さらに、転送部２２は、その検索されたキーＵが一つである場合には、そのキーＵを転送先の識別子（キーＰ）として抽出する。また、転送部２２は、複数のキーＵが検索された場合には、それらキーＵの中から、自装置２０のキーＲからの距離が最も長いキーＵを転送先の識別子（キーＰ）として抽出する。転送部２２は、その識別子（キーＰ）を持つ分散処理装置２０を転送先として決定する。
なお、キーＵが検索されなかった場合には、転送部２２は、自装置２０が、キーＱに対応するプレディセッサであると判断する。この場合には、自装置２０の識別子（キーＲ）に対応するサクセッサ（Ｒ）は、キーＱを識別子として持つ分散処理装置２０である。
一方、転送部２２がデータを自装置２０内の構成部に転送する場合には、転送部２２は、データに含まれているサービス識別情報を参照し、転送先を決定する。つまり、転送部２２は、データに含まれているサービス識別情報が、“初期化”である場合には、転送先を初期化部２４であると決定する。転送部２２は、データに含まれているサービス識別情報が、“アプリケーション”である場合には、転送先をアプリケーション部２９であると決定する。
転送部２２は、上記のように決定した転送先にデータを転送する。
初期化部２４は、第１実施形態における初期化部１４と同様の機能を有する。この第２実施形態では、初期化部２４から転送部２２に出力する検索要求データは、キー情報である基点キーＳと、サービス識別情報である“初期化を示す情報”と、サクセッサ（Ｓ）を検索する要求（検索指令）と、自装置２０のアドレスとを含んでいる。
この初期化部２４の機能によって、第１実施形態と同様に、サクセッサ（Ｓ）の情報がルーティングテーブル２１に登録される。また、分散処理装置２０は、サクセッサ（Ｓ）の情報を取得した後に、プレディセッサの情報を取得する機能を有する。例えば、分散処理装置２０は、サクセッサ（Ｓ）がプレディセッサとして保持している分散処理装置２０の情報を、サクセッサ（Ｓ）の情報を取得した場合と同様に、他の分散処理装置２０に問い合わせることにより、プレディセッサの情報として取得する。また、新規の分散処理装置２０からの検索要求データを受信した場合に、自装置２０がサクセッサ（Ｓ）であると判断した場合には、前述したように、分散処理装置２０は、その新規の分散処理装置２０を自装置２０に対するプレディセッサであると判断する。そして、分散処理装置２０は、その新規の分散処理装置２０の情報をプレディセッサの情報として保持する。
以下に、第２実施形態の分散処理装置２０を構成する転送部２２がデータ（検索要求データ、イベントデータなど）を他の分散処理装置２０に転送する場合における転送部２２の動作例を説明する。図１１は、その転送部２２の動作例を示すフローチャートである。なお、図１１に示すフローチャートは、ＣＰＵ１００１が実行する制御手順を示す。
まず、転送部２２は、キー情報であるキーＱを含むデータを受信すると（ステップＳ５１）、当該データの転送先を次のように決定する。例えば、転送部２２は、前述したように、自装置２０の識別子（キーＲ）からキーＱまでの距離ＤＲ−Ｑを求める。そして、転送部２２は、ルーティングテーブル２１に格納されているサクセッサ（Ｓ）の識別子（キー）の中から、キーＱまでの距離が前記距離ＬＲ−Ｑよりも短いキーＵを検索する。（ステップＳ５２）。
転送部２２は、その検索に基づいて、キーＵが有るか否かを判断する（ステップＳ５３）。キーＵが複数有る場合には、転送部２２は、自装置２０のキーＲからの距離が最も長いキーＵを転送先の識別子（キーＰ）として決定する。また、キーＵが一つである場合には、転送部２２は、そのキーＵを転送先の識別子（キーＰ）として決定する。そして、転送部２２は、そのキーＰを識別子として持つ分散処理装置２０にデータを転送する（ステップＳ５４）。
一方、キーＵが無かった場合には、転送部２２は、ルーティングテーブル２１に登録されているサクセッサである分散処理装置２０の一つにデータを転送（配送）する（ステップＳ５５）。例えば、その転送先の分散処理装置２０は、自装置２０の識別子（キーＲ）に１を加算した基点キーＳに対応するサクセッサ（Ｓ）である。
以下に、転送部２２がデータ（検索要求データ、検索応答データ、イベントデータなど）を自装置２０内の他の構成部に転送する場合における転送部２２の動作例を説明する。図１２は、その転送部２２の動作例を示すフローチャートである。なお、図１２に示すフローチャートは、ＣＰＵ１００１が実行する制御手順を示す。
まず、転送部２２は、データを受信すると（ステップＳ６１）、受信したデータに含まれているサービス識別情報を参照する。そして、転送部２２は、サービス識別情報に基づいて転送先を決定する。例えば、サービス識別情報が“初期化”である場合には、転送部２２は、転送先を初期化部２４と決定する。サービス識別情報が“アプリケーション”である場合には、転送部２２は、転送先をアプリケーション部２９と決定する。その後、転送部２２は、その決定した転送先にデータを出力（転送）する（ステップＳ６２）。
以下に、分散処理システムに新規に参加する新規の分散処理装置２０の動作例を図１３−図１６の各フローチャートを参照して説明する。なお、図１３−図１６に示される各フローチャートは、ＣＰＵ１００１が実行する制御手順を示す。
図１３は新規の分散処理装置２０を構成する算出部２３の動作例を示すフローチャートである。分散処理装置２０が新規に分散処理システムに参加する場合には、まず、算出部２３が基点キーＳを次のように算出する。図１３に示されるように、算出部２３は、空の基点キーリストを作成する（ステップＳ７１）。次に、算出部２３は、キー空間において自装置２０の識別子（キー）からの距離が２ｊ−１（ｊ＝１，２，・・・，ｍ）であるキーを算出する。算出部２３は、算出したキーを基点キーＳとして基点キーリストに登録する（ステップＳ７２）。
次に、算出部２３は、分割手法を利用して、基点キーＳを算出する。つまり、算出部２３は、キー空間において予め定めた起点値Ｃ１（例えば自装置２０の識別子（キーＲ））からの距離が２ｍ×Ｋ／Ｃ２（Ｋは１，２，・・・，Ｃ２であり、Ｃ２は予め定めた分割数である）であるキーを算出する。算出部２３は、算出したキーを基点キーＳとして基点キーリストに登録（追加）する（ステップＳ７３）。
その後、算出部２３は、基点キーリストを初期化部２４に出力する（ステップＳ７４）。
基点キーリストを受けて、初期化部２４が次のように動作する。図１４は、その初期化部２４の動作例を示すフローチャートである。図１４に示すように、初期化部２４は、基点キーリストを取得すると（ステップＳ８１）、基点キーリストに登録されている各基点キーＳ毎に、検索要求データを生成する。検索要求データは、キー情報としての基点キーＳと、サービス識別情報としての“初期化”と、メッセージとしての検索指令とを含んでいる。
続いて、初期化部２４は、その生成した検索要求データを転送部２２に出力する（ステップＳ８２）。転送部２２は、受信した検索要求データを前述したように他の分散処理装置２０に転送する。なお、転送部２２は、検索要求データを受信してから転送するまでの処理を各検索要求データ毎に、順次実行する。
以下に、検索要求データを受け取った他の分散処理装置２０における初期化部２４の動作例を説明する。図１５は、その初期化部２４の動作例を示すフローチャートである。新規の分散処理装置２０から検索要求データを受信した転送部２２が、自装置２０がサクセッサであると判断した場合には、初期化部２４は、転送部２２から、検索要求データに含まれている基点キーＳと発信元の新規の分散処理装置２０のアドレスとを受け取る（ステップＳ９１）。これにより、初期化部２４は、検索応答データを生成する。この検索応答データは、基点キーＳと、新規の分散処理装置２０のアドレスと、自装置（つまり、サクセッサ（Ｓ））２０の識別子（キー）およびアドレスとを含んでいる。
そして、初期化部２４は、その検索応答データを転送部２２に出力する（ステップＳ９２）。転送部２２は、受け取った検索応答データに含まれている新規の分散処理装置２０のアドレスに基づいて、検索応答データを新規の分散処理装置２０に返信する。
以下に、新規の分散処理装置２０が検索応答データを受信した場合の初期化部２４の動作例を説明する。図１６は、その初期化部２４の動作例を示すフローチャートである。
転送部２２が検索応答データを受信すると、初期化部２４は、転送部２２から、検索応答データに含まれている基点キーＳと、サクセッサ（Ｓ）の識別子（キー）およびアドレスとを受け取る（ステップＳ１０１）。そして、初期化部２４は、受け取った情報の組み合わせをレコードとしてルーティングテーブル２１に登録する（ステップＳ１０２）。
初期化部２４は、検索応答データを受信する度に、図１６に示す動作を実行し、サクセッサ（Ｓ）の情報を含むレコードをルーティングテーブル２１に順次登録していく。
そのルーティングテーブル２１の一例が図１７に示されている。ここでは、４つの分散処理装置２０（２０ａ，２０ｂ，２０ｃ，２０ｄ）が分散処理システムを構成していることを想定している。また、キー空間を決定するｍは、ｍ＝８としている。さらに、各分散処理装置２０（２０ａ〜２０ｄ）が持つ識別子（キー）は、それぞれ、２１，６０，１３１，１９２としている。
この第２実施形態では、各分散処理装置２０（２０ａ〜２０ｄ）を構成する算出部２３は、それぞれ、Ｃｈｏｒｄ技術によって自装置２０の識別子からの距離が２ｊ−１（ｊ＝１，２，・・・，ｍ）であるキーを基点キーＳとして算出する。具体例を述べると、キー６０を識別子として持つ分散処理装置２０の算出部２３は、識別子（キー）６０からの距離が２ｊ−１（２１，・・・，２８）である値、つまり、６０＋２ｊ−１＝６１，６２，６４，６８，７６，９２，１２４，１８８を基点キーＳとして算出する。
さらに、算出部２３は、さらに、分割手法を利用する。つまり、算出部２３は、予め定めた起点値Ｃ１からの距離が２ｍ×Ｋ／Ｃ２であるキーを基点キーＳとして算出する。Ｋは１，２，・・・，Ｃ２であり、Ｃ２は、キー空間を分割する予め定めた分割値（ここでは８とする）である。具体例を述べると、キー６０を識別子として持つ分散処理装置２０の算出部２３は、起点値Ｃ１（ここでは、識別子（キー６０）とする）からの距離が２ｍ×Ｋ／Ｃ２である値、つまり、６０＋２８×Ｋ／８＝９２，１２４，１５６，１８８，２２０，２５２，２８，６０を基点キーＳとして算出する。
上記のように算出部２３は、２つの手法を利用して基点キーＳを算出する。
図１７に示されるルーティングテーブル２１では、算出部２３により算出された基点キーＳと、初期化部２４によって取得されたサクセッサ（Ｓ）の情報（識別子としてのキー）とが、初期化部２４によって登録されている。
ここで、図１７に示されているルーティングテーブル２１と、図２８に示されているルーティングテーブル７５とを比較する。なお、図１７と図２８の各例において、分散処理システムの基本構成は同様である。
図２８の例では、キー６０を識別子として持つ分散処理装置ＩＤ６０では、サクセッサ（Ｓ）の情報として、２つの分散処理装置ＩＤ１３１，ＩＤ１９２の情報を有している。これに対して、図１７の例（第２実施形態）では、キー６０を識別子として持つ分散処理装置２０ｂは、サクセッサ（Ｓ）の情報として、分散処理システムを構成する他の全ての分散処理装置（２０ａ，２０ｃ，２０ｄ）の情報を有している。つまり、図２８に示される分散処理装置は、Ｃｈｏｒｄ技術によって基点キーＳを算出する構成を有する。図１７に示す第２実施形態の分散処理装置２０は、Ｃｈｏｒｄ技術に加えて分割手法によっても基点キーＳを算出する構成を有する。この第２実施形態の分散処理装置２０は、図２８に示される分散処理装置よりもメモリリソースをより活用できる。
この第２実施形態では、上記の如く、算出部２３は、第１実施形態における算出部１３と同様に、Ｃｈｏｒｄ技術に加えて分割手法によっても基点キーＳを算出する。これにより、第２実施形態の分散処理装置２０および分散処理システムは、第１実施形態と同様の効果を得ることができる。つまり、第２実施形態の分散処理装置２０は、イベントデータを転送する場合に、サクセッサのアドレスを追加したり、削除するというようなアドレス処理を行わなくて済むという効果を得ることができる。また、第２実施形態の分散処理システムは、イベントデータを転送する回数を削減することができる。これにより、第２実施形態の分散処理システムは、イベントデータ配送性能を向上できる。
例えば、算出部２３が、分割手法として、起点値Ｃ１からの距離が２ｍ×Ｋ／Ｃ２である値を基点キーＳとして算出する場合に、分散処理システムを構成する分散処理装置２０の個数が分割数Ｃ２以下であるとする。この場合に、分散処理システムを構成する各分散処理装置２０の識別子がキー空間において等間隔で配置している場合には、分散処理装置２０は、分散処理システムを構成する他の分散処理装置２０の情報（識別子やアドレス）をサクセッサ（Ｓ）の情報として保持できる。この場合には、外部から分散処理システムに入力したイベントデータは、高々１回転送されるだけで、当該イベントデータを処理するサクセッサとしての分散処理装置２０に送信される。
また、分散処理システムを構成する分散処理装置２０の個数が分割数Ｃ２よりも大きい場合であっても、分散処理システムは、オーダｌｏｇ（ｎ）回の転送でイベントデータをサクセッサとしての分散処理装置２０に送信できる。
Ｃｈｏｒｄ技術を利用する場合には、分散処理装置の識別子は、分散処理装置が保持する固有の値に基づいたハッシュ値となっている。分散処理装置の識別子の分布は、厳密には、分散処理装置が保持する固有の値と、ハッシュ値を求めるハッシュ関数によるため、識別子の値は等間隔に配置していない。しかしながら、ハッシュ関数により求めた識別子の集合が、特定の値に偏ることはないと考えられる。このことから、隣り合う識別子同士の距離が、高い確率でＢ以上になると想定する。すると、第２実施形態の分散処理装置２０は、Ｃ２を２ｍ／Ｂとすることで、高い確率で他の全ての分散処理装置のアドレスを記憶することができる。
さらに、第２実施形態では、算出部２３は、基点キーＳを算出する場合に利用するＣ１＋２ｍ×Ｋ／Ｃ２のうちの起点値Ｃ１を自装置２０の識別子としている。これにより、キー空間を分割することによって算出された基点キーＳのうち、Ｃｈｏｒｄ技術によって設定した基点キーＳと一致するキーが多くなる。これにより、分散処理装置２０は、ルーティングテーブル２１が冗長になることを防止できる。さらに、分割値Ｃ２を２Ｃ３（Ｃ３はｍ以下の予め定めた整数）とすることにより、２ｍ×Ｋ／Ｃ２はキー空間のキーと一致する。これにより、算出部２３は、２ｍ×Ｋ／Ｃ２に関し、近似処理（例えば切り上げ処理）が不要となる。
なお、分散処理システムにおいてイベントデータの転送回数をより少なくするためには、上記Ｃ３は、ｍを越えない範囲で、大きい値であることが好ましい。一方で、ルーティングテーブル２１のサイズを小さくする観点では、Ｃ３は、小さい値であることが好ましい。つまり、Ｃ３が関わるイベントデータの転送回数と、ルーティングテーブル２１のサイズとはトレードオフの関係にある。それらイベントデータの転送回数およびルーティングテーブル２１のサイズを考慮して、Ｃ３は適宜に設定される。
（第３実施形態）
以下に、本発明に係る第３実施形態を説明する。なお、第３実施形態の説明において、第１や第２の実施形態における説明と重複する部分の説明は省略する。
図１８は、第３実施形態における分散処理装置の構成を示すブロック図である。第３実施形態の分散処理装置３０は、第１や第２の実施形態における分散処理装置１０，２０と同様のハードウェア構成を有している。
分散処理装置３０において、記憶装置１００４は、ルーティングテーブル３１を保持している。ルーティングテーブル３１は、第１や第２の実施形態におけるルーティングテーブル１１，２１と同様な構成を有している。ただ、この第３実施形態では、ルーティングテーブル３１には、非重複レコード数の上限値Ｆが設定されている。非重複レコード数とは、ルーティングテーブル３１に格納されている全てのレコード数から、他のレコードとサクセッサ（Ｓ）の識別子が重複しているレコードを除いたレコードの数である。
ＣＰＵ１００１は、その機能として、転送部３２と、算出部３３と、初期化部３４と、更新要求部（更新要求手段）３５と、更新部（更新手段）３６と、アプリケーション部３９とを有する。この第３実施形態では、ルーティングテープル３１と、算出部３３と、初期化部３４と、更新要求部３５と、更新部３６とによって、ルーティングテーブル生成装置３００が構成されている。
算出部３３は、第２実施形態における算出部２３の機能に加えて、算出した基点キーＳに優先順位を設定する機能を有する。基点キーＳに優先順位を設定するアルゴリズムは様々に考えられる。ここでは、それらアルゴリズムの中から適宜なアルゴリズムが採用される。そのアルゴリズムの例を以下に説明する。
例えば、算出部３３は、Ｃｈｏｒｄ技術により算出した基点キーＳを、分割手法により算出した基点キーＳよりも優先順位を高く設定する。この場合、例えば、算出部３３は、分割手法によって算出した基点キーＳのうち、キー空間を分割している任意数の基点キーを選択してその優先順位を、該選択された基点キーＳ間にある残りの基点キーＳの優先順位より高く設定する。そして、算出部３３は、さらに残りの基点キーＳのうち、キー空間を略等分している任意数の基点キーを選択してその優先順位を、該選択された基点キーＳ間にある残りの基点キーＳの優先順位より高く設定する。このような処理を算出部３３は繰り返す。このような場合に、算出部３３は、優先順位が同一となる基点キーＳがあれば、例えば、そのうち予め定めた起点値からの距離がより小さい基点キーＳの優先順位をより高く設定する。すなわち、算出部３３は、分割手法によって算出した基点キーＳのうち、粗い分割位置に位置する基点キーＳの優先順位を、細かい分割位置に位置する基点キーＳの優先順位より高く設定する。
より具体例を述べると、算出部３３は、空の基点キーリストに、自装置３０の識別子（キーＲ）からの距離が２ｊ−１（ｊ＝１，２，．．．，ｍ）である基点キーＳを登録する。その次に、算出部３３は、変数ｎ，ｄの初期値を共に１として、Ｃ２×ｎ／ｄの小数点以下を切り上げた整数値をＥとして算出する。そして、算出部３３は、予め定めた起点値Ｃ１からの距離が２ｍ×Ｐ／Ｃ２である基点キーＳを基点キーリストに追加する。このとき、算出部３３は、基点キーリストに新たに登録する基点キーＳを、登録済みの基点キーＳよりも後の順番となるように登録する。その後、算出部３３は、ｎがｄに等しければ、次のｎを１とし、ｄ×２を次のｄとし、変更後のｎとｄに基づいて整数値Ｅを算出する。また、算出部３３は、ｎがｄに等しくなければ、ｎ＋１を次のｎの値とし、変更後のｎとｄに基づいて整数値Ｅを算出する。そして、算出部３３は、前記同様に、起点値Ｃ１からの距離が２ｍ×Ｐ／Ｃ２である基点キーＳを基点キーリストに追加する。算出部３３は、上記のような処理を、算出済みＥの集合に１からＣ２までの全ての整数値が少なくとも１つずつ含まれるまで繰り返す。これにより、算出部３３は、優先順位の高い順に基点キーＳを並べた基点キーリストを生成する。
初期化部３４は、第２実施形態における初期化部２４の機能に加えて、次のような機能を有する。その機能とは、ルーティングテーブル３１に格納されている非重複レコード数が上限値（閾値）Ｆを越えた場合に、ルーティングテーブル３１にレコードを追加しないという機能である。
初期化部３４は、ルーティングテーブル３１にレコードを登録する場合に、算出部３３によって設定された優先順位の高い基点キーＳから順に、非重複レコード数が上限値Ｆに達するまでレコードを登録する機能を有する。レコードは、第１や第２の実施形態と同様に、基点キーＳと、サクセッサ（Ｓ）の識別子（キー）とを含んでいる。
更新要求部３５は、初期化処理によってルーティングテーブル３１にレコードが登録された以降に、更新要求データを転送部３２に出力する機能を有している。更新要求データとは、他の分散処理装置３０に対して、自装置３０の識別子を持つレコードをルーティングテーブル３１に登録することを要求するデータである。当該更新要求データは、自装置３０（発信元）の識別子（キー）およびアドレスと、当該データの送付先に関わる情報と、ルーティングテーブルを更新することを要求するメッセージとを含んでいる。この更新要求データの送付先は、例えば、更新要求データの発信元（自装置３０）が持つ識別子（キー）までの距離が予め定めた距離ＧとなるキーＪに対するプリディセッサである。その予め定めた距離Ｇとは、例えば、更新要求データの発信元（自装置３０）の識別子（キー）から、算出部３３が算出した基点キーＳまでの距離である。基点キーＳは、複数算出されるから、更新要求データの送付先は、複数である。この場合、更新要求部３５は、更新要求データの送付先毎に、データの送付先に関わる情報として距離ＧとキーＪの情報を含む更新要求データを生成し、これら複数の更新要求データを転送部３２に出力する。
転送部３２は、更新要求データを当該データの最終送付先に配送するために、次の転送先を決定する機能を有する。例えば、転送部３２は、更新要求データに含まれている情報に基づいて、ルーティングテーブル３１の中から、自装置３０の識別子よりもキーＪに近いサクセッサ（Ｓ）の識別子（自装置３０の識別子からキーＪまでの距離よりもキーＪまでの距離が短いサクセッサ（Ｓ）の識別子）を検索する。そして、転送部３２は、その検索した識別子の中から、キー空間において最も自装置３０の識別子からの距離が遠いサクセッサ（Ｓ）の識別子を送付先の識別子Ｐとして抽出する。そして、転送部３２は、その識別子Ｐを持つ分散処理装置３０に向けて更新要求データを送信する。このようにして転送部３２は、更新要求データを順次、他の分散処理装置３０に向けて送信する。
また、転送部３２は、受信した更新要求データに含まれているキーＪに基づいた識別子Ｐをルーティングテーブル３１から検索できなかった場合には、自装置３０が、キーＪに対するプレディセッサであると判断する。この場合には、転送部３２は、更新要求データを更新部３６に向けて出力する。さらに、転送部３２は、他の分散処理装置３０から受信した更新要求データも更新部３６に出力する。
更新部３６は、転送部３２から更新要求データを受信した場合に、その更新要求データに基づいてルーティングテーブル３１を更新する機能を有する。例えば、更新部３６は、更新要求データに含まれている距離Ｇを参照し、自装置３０の識別子から距離Ｇ離れたキーが基点キーＳとしてルーティングテーブル３１に含まれている場合には、その基点キーＳを含むレコード（更新対象であるレコード）を次のように更新する。すなわち、更新部３６は、自装置３０の識別子から、その更新対象であるレコードに含まれているサクセッサ（Ｓ）の識別子までの距離よりも、自装置３０の識別子から更新要求データを発信した更新要求元の分散処理装置３０の識別子までの距離が短い（近い）場合がある。この場合には、更新部３６は、更新対象のレコードに含まれている基点キーＳに、更新要求元の分散処理装置３０の識別子およびアドレスを関連付けて更新対象のレコードを更新する。
また、更新部３６は、自装置３０からの距離が距離Ｇとなる基点キーＳをルーティングテーブル３１から検索できなかった場合には、その基点キーＳに、更新要求元の分散処理装置３０の識別子およびアドレスを関連付けた新規のレコードを生成する。そして、更新部３６は、そのレコードをルーティングテーブル３１に登録する。
さらに、更新部３６は、ルーティングテーブル３１に登録されている非重複レコード数が上限値（閾値）Ｆを超えていることを検知した場合には、非重複レコード数が上限値Ｆ以下になるようにレコードを削減する。この場合、更新部３６は、基点キーリストに基づいて、優先順位の低い基点キーを含むレコードから順に削減する。
以下に、第３実施形態における分散処理装置３０の動作例を図１９−図２３を参照して説明する。なお、図１９−図２３に示されているフローチャートは、分散処理装置３０のＣＰＵ１００１が実行するコンピュータプログラムの制御手順である。
図１９は、第３実施形態における分散処理装置３０を構成する算出部３３の動作例を示すフローチャートである。算出部３３は、分散処理装置３０が新規に分散処理システムに参加する際に、次のような算出動作を実行する。
算出部３３は、まず、空の基点キーリストを作成する（ステップＳ７１）。その後、算出部３３は、自装置３０の識別子（キーＲ）からの距離が２ｊ−１（ｊ＝１，２，・・・，ｍ）となるキーを算出し、当該算出したキーを基点キーＳとして基点キーリストに登録する（ステップＳ７２）。
次に、算出部３３は、変数ｎ，ｄの各初期値を１に設定する（ステップＳ１１１）。そして、算出部３３は、Ｃ２×ｎ／ｄの小数点以下を切り上げた整数値をＥとして算出する。Ｃ２は予め定められた分割数である。さらに、算出部３３は、予め定められた起点値Ｃ１からの距離が２ｍ×Ｐ／Ｃ２であるキーを算出し、当該算出したキーを基点キーＳとして基点キーリストに追加する（ステップＳ１１２）。
その後、算出部３３は、変数ｎが変数ｄに等しいか否かを判断する（ステップＳ１１３）。そして、算出部３３は、変数ｎが変数ｄに等しくないと判断した場合には、ｎ＋１の値を変数ｎとして更新する（ステップＳ１１４）。一方、算出部３３は、変数ｎが変数ｄに等しいと判断した場合には、変数ｎの値を１に更新し、ｄ×２の値を変数ｄとして更新する（ステップＳ１１５）。
その後、算出部３３は、前記算出した整数値Ｅ（Ｅ＝Ｃ２×ｎ／ｄ（小数点以下を切り上げ））の中に、１から分割数Ｃ２までの全ての整数値が含まれているか否かを判断する（ステップＳ１１６）。そして、算出部３３は、全ての整数値が含まれていないと判断した場合には、前記ステップＳ１１２以降の動作を繰り返す。例えば、ここで、ｍ＝８、Ｃ２＝８、Ｃ１＝０であると仮定する。算出部３３は、ステップＳ１１２を繰り返す度に、整数値Ｅ（Ｅ＝Ｃ２×ｎ／ｄ）として、８×１／１＝８，８×１／２＝４，８×２／２＝８，８×１／４＝２，８×２／４＝４，８×３／４＝６，８×４／４＝８，・・・を算出していく。つまり、算出部３３は、まず、キー空間を１つに分割した位置の基点キー０を算出する。次に、算出部３３は、ステップＳ１１６からステップＳ１１２に戻って当該ステップＳ１１２の動作を行った場合には、２つに分割した位置の基点キー１２８，０を算出し、その後、算出部３３は、同様にステップＳ１１２の動作を繰り返すことによって、４つに分割した位置の基点キー６４，１２８，１９２，０を算出する。このように、算出部３３は、基点キーＳを順に算出し、基点キーリストに登録していく。つまり、算出部３３は、優先順位の高い順に基点キーを並べた基点キーリストを作成する。なお、算出部３３は、基点キーリストに登録されている基点キーと重複する基点キーを算出した場合には、その重複する基点キーを基点キーリストに追加する動作を省略してもよい。
一方、算出部３３は、前記ステップＳ１１６の判断動作によって、全ての整数値が含まれていると判断した場合には、基点キーリストを初期化部３４に出力する（ステップＳ１１７）。
以下に、第３実施形態における分散処理装置３０を構成する初期化部３４の動作例を説明する。図２０は、その初期化部３４の動作例を示すフローチャートである。
例えば、初期化部３４は、算出部３３から基点キーリストを取得すると（ステップＳ８１）、ルーティングテーブル３１に含まれている非重複レコード数が上限値（閾値）Ｆ以下であるか否かを判断する（ステップＳ１２１）。そして、初期化部３４は、非重複レコード数が上限値Ｆ以下であると判断した場合には、第２実施形態における初期化部２４と同様に、検索要求データを生成する。その検索要求データは、キー情報としての基点キーＳと、サービス識別情報としての“初期化”と、メッセージとしてのサクセッサ（Ｓ）を検索することを要求する指令および自装置３０の識別子とを含んでいる。初期化部３４は、その生成した検索要求データを転送部３２に出力する（ステップＳ８２）。
一方、初期化部３４は、前記ステップＳ１２１の判断動作によって、ルーティングテーブル３１の非重複レコード数が上限値を超えていると判断した場合には、動作を終了する。
上記のように初期化部３４から出力された検索要求データに応じて、サクセッサ（Ｓ）としての他の分散処理装置３０から検索応答データが返信されてくる。これにより、初期化部３４は、その検索応答データに基づいて、第２実施形態における初期化部２４と同様に、ルーティングテーブル３１に情報を登録する。このような初期化部３４の動作によって、新規のルーティングテーブル３１に情報が登録される。
以下に、第３実施形態の分散処理装置３０を構成する更新要求部３５の動作例を説明する。図２１は、その更新要求部３５の動作例を示すフローチャートである。
例えば、更新要求部３５は、まず、上記のような初期化部３４の動作が終了したことを検知すると、算出部３３が算出した基点キーリストを初期化部３４を介して取得する（ステップＳ１３１）。そして、更新要求部３５は、基点キーリストに含まれている基点キーＳについて、基点キーリストの先頭から順に（優先順位が高い基点キーから順に）、自装置３０の識別子から各基点キーＳまでの距離Ｇを算出する（ステップＳ１３２）。
次に、更新要求部３５は、自装置３０の識別子までの距離が距離ＧであるキーＪに基づいて導き出されるプレディセッサに向けて、更新要求データを転送部３２に出力する。更新要求データは、キー情報としてキーＪと、自装置３０（発信元）の識別情報およびアドレスと、距離Ｇとを含んでいる。この更新要求データは、基点キーリストに含まれている各基点キーＳに関し、個別に対応して生成され、更新要求部３５から転送部３２に出力される。
以下に、転送部３２が更新要求データを送信（転送）する際の動作例を説明する。図２２は、その転送部３２の動作例を示すフローチャートである。
まず、転送部３２は、更新要求データを受信すると（ステップＳ１４１）、送付先の識別子Ｐを次のように検索する（ステップＳ１４２）。つまり、転送部３２は、自装置３０の識別子からキーＪまでの距離よりも、キーＪまでの距離が近いサクセッサ（Ｓ）の識別子を、ルーティングテーブル３１から検索する。そして、転送部３２は、検索した識別子の中から、最も自装置３０の識別子から離れているキーを送付先の識別子Ｐとして抽出（検索）する。
転送部３２は、自装置３０の識別子からキーＪまでの距離よりも、キーＪまでの距離が短いサクセッサ（Ｓ）の識別子を、ルーティングテーブル３１から検索できない（該当する識別子が無い）場合がある。この場合には、転送部３２は、次に、送付先の識別子Ｐが存在するか否かを判断するステップＳ１４３において、送付先の識別子Ｐは存在しないと判断する。その後、転送部３２は、更新部３６に向けて更新要求データを出力する。
これに対して、転送部３２は、送付先の識別子Ｐを検索できた場合には、その識別子Ｐを持つ分散処理装置３０に向けて更新要求データを送信する。
以下に、更新部３６の動作例を説明する。図２３は、その更新部３６の動作例を示すフローチャートである。例えば、更新部３６は、転送部３２を介して、自装置３０の更新要求部３５あるいは他の分散処理装置３０から更新要求データを受け取ると（ステップＳ１５１）、更新要求データに基づいて、更新対象のレコードがルーティングテーブル３１に格納されているか否かを判断する（ステップＳ１５２）。つまり、更新部３６は、自装置３０の識別子から、更新要求データに含まれている距離Ｇ離れた位置にあるキーを基点キーＳとして含むレコード（更新対象のレコード）がルーティングテーブル３１にあるか否かを判断する。
更新部３６は、更新対象のレコードがないと判断した場合には、上記基点キーＳと、更新要求データに含まれている発信元の分散処理装置３０の識別子およびアドレスとを含む新規のレコードをルーティングテーブル３１に格納する（ステップＳ１５３）。
一方、更新部３６は、更新対象のレコードがあると判断した場合には、その更新対象のレコードに含まれているサクセッサ（Ｓ）の識別子を取得する。そして、更新部３６は、自装置３０の識別子からそのサクセッサ（Ｓ）の識別子までの距離Ｌａよりも、自装置３０の識別子から発信元の分散処理装置３０の識別子までの距離Ｌｂが短いか否かを判断する（ステップＳ１５４）。これにより、更新部３６は、距離Ｌａよりも距離Ｌｂが短いと判断した場合には、更新対象のレコードに含まれているサクセッサ（Ｓ）の識別子を、更新要求データに含まれている発信元の分散処理装置３０の識別子に変更する（ステップＳ１５５）。
また、更新部３６は、距離Ｌａよりも距離Ｌｂが短くないと判断した場合、あるいは、ステップＳ１５５の動作が終了した後に、ルーティングテーブル３１の非重複レコード数が上限値Ｆ以下であるか否かを判断する（ステップＳ１５６）。そして、更新部３６は、ルーティングテーブル３１の非重複レコード数が上限値Ｆを超えていると判断した場合には、非重複レコード数が上限値Ｆ以下となるように、ルーティングテーブル３１のレコードを削除する（ステップＳ１５７）。
更新部３６は、更新要求データを受信する度に、上記ステップＳ１５１以降の動作を繰り返す。
以下に、上記のような分散処理装置３０によって構成される分散処理システムに新規に分散処理装置３０が参加する場合における分散処理システムの処理フローの一例を説明する。図２４は、その分散処理システムにおける処理フローの例を説明するシーケンス図である。
まず、新規の分散処理装置３０を構成する算出部３３が基点キーリストを生成する。その後、新規の分散処理装置３０を構成する初期化部３４が、ルーティングテーブル３１の非重複レコード数が上限値Ｆ以下であるか否かを判断する（ステップＳ１２１）。そして、初期化部３４がルーティングテーブル３１の非重複レコード数が上限値Ｆを超えていると判断した場合には、ルーティングテーブル３１に情報を登録する動作を終了する。これに対して、初期化部３４は、ルーティングテーブル３１の非重複レコード数が上限値Ｆ以下であると判断した場合には、検索要求データを出力する。この検索要求データを転送部３２が受ける。これにより、転送部３２は、検索要求データを、分散処理システムを構成する他の分散処理装置３０に転送する。
検索要求データを受けた他の分散処理装置３０を構成する転送部３２は、検索要求データに基づいて、自装置３０がサクセッサ（Ｓ）であるか否かを判断する。そして、転送部３２は、自装置３０がサクセッサ（Ｓ）でないと判断した場合には、検索要求データをサクセッサに向けて送信（転送）する（ステップＳ５１，Ｓ５４）。
新規の分散処理装置３０に対するサクセッサとして機能する分散処理装置３０は、検索要求データを受信すると、その検索要求データに応じた検索応答データを生成する。その後、サクセッサは、検索応答データを、新規の分散処理装置３０に向けて送信（返信）する（ステップＳ９２）。
新規の分散処理装置３０における初期化部３４は、その検索応答データを受信すると、検索応答データに基づいたレコードをルーティングテーブル３１に登録する（ステップＳ１０２）。
以下に、新規の分散処理装置３０が分散処理システムに参加する場合に、他の分散処理装置３０におけるルーティングテーブル３１の更新に関わる処理フローを説明する。図２５は、その処理フローを示すシーケンス図である。
例えば、まず、新規の分散処理装置３０を構成する更新要求部３５は、算出部３３により生成された基点キーリストに登録されている各基点キーＳについて、自装置３０の識別子から基点キーまでの距離Ｇを算出する。そして、更新要求部３５は、自装置３０の識別子までの距離が、上記算出した距離ＧであるキーＪを持つ分散処理装置３０に対するプレディセッサを算出する。さらに、更新要求部３５は、そのプレディセッサの情報を含む更新要求データを生成し、転送部３２に出力する。転送部３２は、更新要求データを受け取ると、当該更新要求データに基づいて当該データの送信先を決定する。そして、転送部３２は、その決定した送信先に更新要求データを送信する（ステップＳ１３２，Ｓ１３３）。
その更新要求データを受信した他の分散処理装置３０における転送部３２が、当該更新要求データに基づいて、自装置がサクセッサでないと判断した場合には、更新要求データをさらに別の分散処理装置３０に送信（転送）する。
プレディセッサとして機能する分散処理装置３０における転送部３２が更新要求データを受信すると、更新部３６が、その更新要求データに基づいて、ルーティングテーブル３１を更新する（ステップＳ）。その更新後に、更新部３６は、ルーティングテーブル３１の非重複レコード数は上限値Ｆ以下か否かを判断する（ステップＳ１５６）。更新部３６は、非重複レコード数は上限値Ｆ以下であると判断した場合には、処理を終了する。また、更新部３６は、非重複レコード数が上限値Ｆを超えていると判断した場合には、ルーティングテーブル３１の一部のレコードを削除する。これにより、更新部３６は、ルーティングテーブル３１の非重複レコード数を上限値Ｆ以下にする。
上記のような処理によって、新規の分散処理装置３０が分散処理システムに参加する場合に、当該分散処理システムを構成する他の分散処理装置３０はルーティングテーブル３１を更新する。
なお、図２４および図２５の例では、新規の分散処理装置３０から送信された検索要求データや更新要求データがサクセッサやプレディセッサに至るまでに、一つの分散処理装置３０を通っている。これに対して、検索要求データや更新要求データは、他の分散処理装置３０を介さずに直接に、サクセッサやプレディセッサに至る場合もある。また、検索要求データや更新要求データは、２つ以上の他の分散処理装置３０を介してサクセッサやプレディセッサに至る場合もある。
以下に、第３実施形態の効果を説明する。この第３実施形態における分散処理装置３０は、第１や第２の各実施形態を構成する算出部と同様な機能を有する算出部を備えている。これにより、第１や第２の実施形態と同様の効果を得ることができる。つまり、分散処理装置３０は、イベントデータを転送する際に、メモリにデータを登録したり、削除するというような処理を行わなくて済むという効果を得ることができる。また、分散処理装置３０は、イベントデータの転送回数を減少できる。
さらに、この第３実施形態では、分散処理装置３０は、登録可能な上限値を超えてレコードをルーティングテーブル３１に登録しない構成を有しているので、メモリリソースの過剰な活用を抑制できる。また、分散処理装置３０は、ルーティングテーブル３１の非重複レコード数が上限値Ｆを超えている場合に、その上限値を超えた分のレコードを削除する。当該分散処理装置３０は、そのレコードを削除するタイミングを、新規の分散処理装置３０に起因してルーティングテーブル３１を更新するタイミングとしている。これにより、上記レコードを削除する処理が、ルーティングテーブル３１やメモリリソースを利用する他の処理に及ぼす悪影響を小さく抑えることができる。
なお、第２や第３の各実施形態は、非特許文献１に記載されている技術を含む分散処理装置に本発明を適用する例を示している。これに対し、本発明は、他の分散ハッシュテーブルの技術を採用した分散処理装置に適用することもできる。
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
なお、この出願は、２０１１年３月１７日に出願された日本出願特願２０１１−０５９５５６を基礎とする優先権を主張し、その開示の全てをここに取り込む。
また、上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）
並び順が定められた値を持つ複数のキーがその順にしたがって配置されたキー空間における前記キーを識別子として保持する分散処理装置に備えられ、前記キー空間において任意の２つのキー間の距離が定義されている場合、
前記キー空間における他のキーを識別子とする他の分散処理装置の前記識別子を含むレコードを記憶するルーティングテーブルと、
前記ルーティングテーブルに格納する前記他の分散処理装置を決定する際に前記キー空間において基点となるキーを表す基点キーを算出する算出手段であって、あらかじめ規定された手段により基点キーを算出することに加えて、前記キー空間を等間隔あるいは略等間隔に分割し、分割後の各キー範囲の端点のキーを基点キーとして算出する算出手段と、
前記算出手段によって算出された前記各基点キーについて、前記キー空間における他のキーを識別子とする他の分散処理装置のうち該基点キーからの距離が最も小さい識別子を有する分散処理装置であるサクセッサの識別子および前記基点キーを含むレコードを前記ルーティングテーブルに登録する初期化手段と、
を備えたルーティングテーブル生成装置。
（付記２）
前記キーがｍ（ｍは正の整数）ビットの値であり、前記キー空間において任意のキーｋからの距離がｄであるキーの値が（ｋ＋ｄ）ｍｏｄ  ２ｍであると定義されるとき、
前記算出手段は、前記あらかじめ規定された手段に基づく基点キーとして、自装置の識別子からの距離が２ｊ−１（ｊ＝１，２，．．．，ｍ）である各キーを基点キーとして算出することに加えて、所定の起点値Ｃ１からの距離が２ｍ×ｋ／Ｃ２（Ｃ２は所定の分割数）（ｋ＝１，２，．．．，Ｃ２）である各値を基点キーとして算出する付記１に記載のルーティングテーブル生成装置。
（付記３）
前記初期化手段は、前記ルーティングテーブルに登録されているレコードのうち、前記識別子の重複を除いたレコード数を表す非重複レコード数が上限値に達している場合に、前記ルーティングテーブルにレコードを追加しない付記１または付記２に記載のルーティングテーブル生成装置。
（付記４）
前記算出手段は、算出した各基点キーに所定の優先順位を設定し、
前記初期化手段は、前記算出手段によって設定された前記優先順位の高い基点キーから順に前記非重複レコード数が前記上限値に達するまで、前記基点キーおよびそのサクセッサの識別子を含むレコードを前記ルーティングテーブルに登録する付記３に記載のルーティングテーブル生成装置。
（付記５）
前記算出手段は、前記算出手段によって算出された基点キーのうち、前記あらかじめ規定された手段に基づく基点キーの優先順位を他の基点キーの優先順位より高く設定し、次に、前記キー空間を等間隔あるいは略等間隔に分割して得られた基点キーのうち、前記キー空間を等分あるいは略等分している数の基点キーを選択してその優先順位を、該選択された基点キー間にある残りの基点キーの優先順位より高く設定し、さらに残りの基点キーのうち前記キー空間を等分あるいは略等分している数の基点キーを選択してその優先順位を、該選択された基点キー間にある残りの基点キーの優先順位より高く設定していく処理を繰り返し、優先順位が同一となる基点キーがあれば、そのうち所定の起点値からの距離がより小さい基点キーの優先順位をより高く設定する付記４に記載のルーティングテーブル生成装置。
（付記６）
前記キーがｍ（ｍは正の整数）ビットの値であり、前記キー空間において任意のキーｋからの距離がｄであるキーの値が（ｋ＋ｄ）ｍｏｄ  ２ｍと定義され、前記キー空間の前記分割数がＣ２であるとき、
前記算出手段は、自装置の識別子からの距離が２ｊ−１（ｊ＝１，２，．．．，ｍ）である基点キーを空の基点キーリストに追加し、次に、変数ｎおよび変数ｄの初期値を共に１として、Ｃ２×ｎ／ｄの小数点以下を切り上げた整数値をＰとして、所定の起点値Ｃ１からの距離が２ｍ×Ｐ／Ｃ２である基点キーを前記基点キーリストの後ろに追加し、以降、変数ｎが変数ｄに等しければ、変数ｎの値を１に更新し、変数ｄの値をｄ×２に更新し、変数ｎが変数ｄに等しくなければ、変数ｎの値をｎ＋１に更新し、変更後の変数ｎおよび変数ｄから前記整数値Ｐを算出し、前記起点値Ｃ１からの距離が２ｍ×Ｐ／Ｃ２である基点キーを前記基点キーリストの後ろに追加する処理を、算出済み整数値Ｐの集合に１からＣ２までの全ての整数値が含まれるまで繰り返すことにより前記基点キーリストを生成し、
前記初期化手段は、前記基点キーリストの先頭から順に各基点キーに対応するサクセッサの識別子を含むレコードを、前記非重複レコード数が前記上限値に達するまで、前記ルーティングテーブルに登録する付記５に記載のルーティングテーブル生成装置。
（付記７）
自装置の識別子を含むレコードを他の分散処理装置の前記ルーティングテーブルに登録することを要求する更新要求データを、自装置の識別子までの距離に基づいて選択される他の分散処理装置に送信する更新要求手段と、
前記更新要求データを受信すると、当該更新要求データおよび前記ルーティングテーブルに基づいて前記ルーティングテーブルを更新する必要があると判断した場合に前記ルーティングテーブルを更新するとともに、更新後の前記ルーティングテーブルに登録されているレコードのうち、前記非重複レコード数が上限値を超えている場合に、前記基点キーに設定された前記優先順位が低いものから順に、前記非重複レコード数が前記上限値以下になるまで、該基点キーを含むレコードを削除する更新手段と、
をさらに備える付記４から付記６のいずれか一つに記載のルーティングテーブル生成装置。
（付記８）
前記更新要求手段は、自装置までの距離があらかじめ定められた所定距離ｄとなるキーについて、前記他の分散処理装置のうち該キーからの距離が前記キー空間上で最も大きい識別子を有する分散処理装置を、前記更新要求データの最終的な送信先として選択し、
前記更新手段は、前記更新要求データの受信に応じて、前記ルーティングテーブルに、自装置の識別子からの距離が前記所定距離ｄとなる基点キーを含むレコードがある場合、自装置の識別子から該レコードに含まれる他の分散処理装置の識別子までの距離より、自装置の識別子から前記更新要求データの送信元の分散処理装置の識別子までの距離が小さければ、前記送信元の分散処理装置の識別子を含むよう該レコードを更新し、自装置の識別子からの距離が前記所定距離ｄとなる基点キーを含むレコードが前記ルーティングテーブルに登録されていない場合、該基点キーおよび前記更新要求データの送信元の分散処理装置の識別子を含むレコードを新たに登録することにより、前記ルーティングテーブルの更新を行う付記７に記載のルーティングテーブル生成装置。
（付記９）
前記ルーティングテーブルは、前記基点キーと、前記基点キーに対応するサクセッサの識別子と、前記サクセッサを通信ネットワーク上で特定するためのアドレスとを含む前記レコードを記憶する付記１から付記８のいずれか一つに記載のルーティングテーブル生成装置。
（付記１０）
前記算出手段は、前記起点値Ｃ１を自装置の識別子とする付記２から付記９のいずれか一つに記載のルーティングテーブル生成装置。
（付記１１）
前記算出手段は、２Ｃ３（ただし、Ｃ３は１〜ｍまでの整数）を前記分割数Ｃ２とする付記２から付記１０のいずれか一つに記載のルーティングテーブル生成装置。
（付記１２）
付記１から付記１１のいずれか一つに記載のルーティングテーブル生成装置と、
自装置の他の部および外部装置のいずれかからデータが入力されると、前記データに含まれる情報および前記ルーティングテーブルに基づいて、前記ルーティングテーブルに記憶された前記他の分散処理装置および自装置の他の部のいずれかを前記データの転送先として決定し、決定した転送先に前記データを転送する転送手段と、
を備え、
前記初期化手段は、前記サクセッサの検索要求を表す検索要求データを、前記サクセッサに最終的に配送されるよう前記転送手段に転送させ、前記転送手段を介して前記サクセッサから前記サクセッサの識別子および前記基点キーを含む検索応答データを受信することにより、前記レコードを前記ルーティングテーブルに登録する分散処理装置。
（付記１３）
付記１２に記載の複数の分散処理装置を備えることにより、前記複数の分散処理装置のうち新規の分散処理装置のルーティングテーブルを初期化する分散処理システム。
（付記１４）
付記１３に記載の分散処理システムを用いて、
前記新規の分散処理装置における前記算出手段は、あらかじめ規定された手段により基点キーを算出することに加えて、前記キー空間を等間隔あるいは略等間隔に分割し、分割後の各キー範囲の端点のキーを基点キーとして算出し、
前記新規の分散処理装置における初期化手段は、前記各基点キーについて前記検索要求データを生成し、
前記新規の分散処理装置における転送手段は、前記複数の分散処理装置のうち前記各基点キーのサクセッサの分散処理装置に対して前記検索要求データが最終的に配送されるよう次の転送先となる他の分散処理装置に対して前記検索要求データを転送し、
前記サクセッサの分散処理装置の転送手段は、前記検索要求データを受信し、
前記サクセッサの分散処理装置の初期化手段は、前記検索要求データに応答するために自装置の識別子を含む検索応答データを生成し、
前記サクセッサの分散処理装置における転送手段は、前記検索応答データを前記新規の分散処理装置に返信し、
前記新規の分散処理装置における転送手段は、前記検索応答データを受信し、
前記新規の分散処理装置における初期化手段は、前記検索応答データに含まれる前記サクセッサの識別子および前記基点キーを含むレコードを前記ルーティングテーブルに登録する分散処理方法。
（付記１５）
前記新規の分散処理装置における前記初期化手段は、前記ルーティングテーブルに登録されているレコードのうち、前記識別子の重複を除いたレコード数を表す非重複レコード数が上限値に達している場合に、前記ルーティングテーブルにレコードを追加しない付記１４に記載の分散処理方法。
（付記１６）
前記新規の分散処理装置における更新要求手段は、自装置の識別子を含むレコードを他の分散処理装置の前記ルーティングテーブルに登録するよう、自装置までの距離に基づいて選択される他の分散処理装置に対して要求する更新要求データを生成し、
前記新規の分散処理装置における転送手段は、前記更新要求データが、前記選択された他の分散処理装置に最終的に配送されるよう、次の転送先となる他の分散処理装置を前記ルーティングテーブルに基づいて決定し、決定した転送先に対して前記更新要求データを転送し、
前記選択された他の分散処理装置における前記転送手段は前記更新要求データを受信し、
前記選択された他の分散処理装置の更新手段は、前記更新要求データおよび前記ルーティングテーブルに基づいて前記ルーティングテーブルを更新する必要があると判断した場合に前記ルーティングテーブルを更新し、更新後の前記ルーティングテーブルに登録されているレコードのうち、前記非重複レコード数が上限値を超えている場合に、前記基点キーに設定された所定の優先順位が低いものから順に、前記非重複レコード数が上限値以下になるまで、該基点キーを含むレコードを削除する付記１５に記載の分散処理方法。
（付記１７）
並び順が定められた値を持つ複数のキーがその順にしたがって配置されたキー空間における前記キーを識別子として保持する分散処理装置が実行するルーティングテーブル生成方法であって、前記キー空間において任意の２つのキー間の距離が定義されている場合、
前記キー空間における他のキーを識別子とする他の分散処理装置のうち、ルーティングテーブルに格納する他の分散処理装置を決定する際に基点となるキーを表す基点キーとして、あらかじめ規定された手段により基点キーを算出することに加えて、前記キー空間を等間隔あるいは略等間隔に分割し、分割後の各キー範囲の端点のキーを前記基点キーとしてさらに算出し、
算出した前記各基点キーについて、前記キー空間における他のキーを識別子とする他の分散処理装置のうち該基点キーからの距離が最も小さい識別子を有する分散処理装置であるサクセッサの識別子および前記基点キーを含むレコードを前記ルーティングテーブルに登録する、ルーティングテーブル生成方法。
（付記１８）
前記ルーティングテーブルに登録されているレコードのうち、前記識別子の重複を除いたレコード数を表す非重複レコード数が上限値に達している場合に、前記ルーティングテーブルにレコードを追加しない付記１７に記載のルーティングテーブル生成方法。
（付記１９）
並び順が定められた値を持つ複数のキーがその順にしたがって配置されたキー空間におけるキーを識別子として保持する分散処理装置に実行させるコンピュータプログラムを記憶する記憶媒体であって、
前記キー空間において任意の２つのキー間の距離が定義されている場合、
前記キー空間における他のキーを識別子とする他の分散処理装置のうち、ルーティングテーブルに格納する他の分散処理装置を決定する際に基点となるキーを表す基点キーとして、あらかじめ規定された手段により基点キーを算出する処理と、
前記キー空間を等間隔あるいは略等間隔に分割し、分割後の各キー範囲の端点のキーを前記基点キーとしてさらに算出する処理と、
算出した前記各基点キーについて、前記キー空間における他のキーを識別子とする他の分散処理装置のうち該基点キーからの距離が最も小さい識別子を有する分散処理装置であるサクセッサの識別子および前記基点キーを含むレコードを前記ルーティングテーブルに登録する処理と、
を実現する制御手順を含むコンピュータプログラムを記憶している記憶媒体。
（付記２０）
前記ルーティングテーブルに登録されているレコードのうち、前記識別子の重複を除いたレコード数を表す非重複レコード数が上限値に達している場合に、前記ルーティングテーブルにレコードを追加しない処理を実現する制御手順をさらに含むコンピュータプログラムを記憶している付記１９に記載の記憶媒体。
【産業上の利用可能性】
【０００９】
本発明は、分散処理を実行する分散処理システムに適用する。
【符号の説明】
【００１０】
１，２，３  分散処理システム
１０，２０，３０  分散処理装置
１００，２００，３００  ルーティングテーブル生成装置
１１，２１，３１  ルーティングテーブル
１２，２２，３２  転送部
１３，２３，３３  算出部
１４，２４，３４  初期化部
３５  更新要求部
３６  更新部
【図１】
2012124448.tif 000003
【図２】
2012124448.tif 000004
【図３】
2012124448.tif 000005
【図４】
2012124448.tif 000006
【図５】
2012124448.tif 000007
【図６】
2012124448.tif 000008
【図７】
2012124448.tif 000009
【図８】
2012124448.tif 000010
【図９】
2012124448.tif 000011
【図１０】
2012124448.tif 000012
【図１１】
2012124448.tif 000013
【図１２】
2012124448.tif 000014
【図１３】
2012124448.tif 000015
【図１４】
2012124448.tif 000016
【図１５】
2012124448.tif 000017
【図１６】
2012124448.tif 000018
【図１７】
2012124448.tif 000019
【図１８】
2012124448.tif 000020
【図１９】
2012124448.tif 000021
【図２０】
2012124448.tif 000022
【図２１】
2012124448.tif 000023
【図２２】
2012124448.tif 000024
【図２３】
2012124448.tif 000025
【図２４】
2012124448.tif 000026
【図２５】
2012124448.tif 000027
【図２６】
2012124448.tif 000028
【図２７】
2012124448.tif 000029
【図２８】
2012124448.tif 000030
【国際調査報告】
2012124448.tif 000031
2012124448.tif 000032