(57)【要約】【課題】データ管理システムに新たなデータ管理装置が追加される際にも、データ管理システムの安定性を保つように適切な処理を行うことができるデータ管理装置を提供する。【解決手段】データ管理システムに新たに追加される新規データ管理装置が、論理空間上で自身に隣接する各データ管理装置の情報を自身の経路表記憶部１３に格納した後に、論理空間上で新規データ管理装置に隣接する各データ管理装置が、自身の経路表記憶部１３に格納されている情報を新規データ管理装置の情報に更新する。これによって、論理空間上の任意の位置に対応するデータ管理装置が常に存在する状態が保たれる。【選択図】図１
2007334638.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータネットワーク上に分散するデータを複数のデータ管理装置で管理するデータ管理システムを構成し、前記複数のデータ管理装置が配置された論理空間における所定範囲に対応したデータを管理するデータ管理装置において、
前記論理空間上で自身に隣接する他のデータ管理装置の情報を記憶する第１の記憶手段と、
前記データ管理システムに新たに追加される新規データ管理装置として動作する場合に、第１および第２のデータ管理装置の情報を前記第１の記憶手段に格納する第１の処理手段と、
前記第１のデータ管理装置として動作する場合に、前記新規データ管理装置が前記第１のデータ管理装置の情報を前記第１の記憶手段に格納した後で、前記第１の記憶手段に格納されている前記他のデータ管理装置の情報を前記新規データ管理装置の情報に更新する第２の処理手段と、
前記第２のデータ管理装置として動作する場合に、前記新規データ管理装置が前記第２のデータ管理装置の情報を前記第１の記憶手段に格納した後で、前記第１の記憶手段に格納されている前記他のデータ管理装置の情報を前記新規データ管理装置の情報に更新する第３の処理手段と、
を備えたことを特徴とするデータ管理装置。
【請求項２】
前記論理空間における所定範囲に対応したデータの情報を記憶する第２の記憶手段をさらに備え、
前記第１の処理手段はさらに、前記所定範囲に対応したデータの情報を前記第１または第２のデータ管理装置から受信して前記第２の記憶手段に格納する
ことを特徴とする請求項１に記載のデータ管理装置。
【請求項３】
前記第１の処理手段は、前記新規データ管理装置の情報を通知するための第１の情報通知メッセージを前記第１のデータ管理装置へ送信する処理と、前記第１のデータ管理装置の情報を前記第１の記憶手段に格納した後で、設定完了を通知するための第１の設定完了通知メッセージを前記第１のデータ管理装置へ送信する処理とを実行し、
前記第２の処理手段は、前記第１の設定完了通知メッセージを受信した場合に、前記第１の記憶手段に格納されている前記他のデータ管理装置の情報を、受信した前記第１の情報通知メッセージが示す前記新規データ管理装置の情報に更新する
ことを特徴とする請求項１または請求項２に記載のデータ管理装置。
【請求項４】
前記第２の処理手段はさらに、前記新規データ管理装置の情報を通知するための第２の情報通知メッセージを前記第２のデータ管理装置へ送信し、
前記第３の処理手段は、前記第２の情報通知メッセージを受信した場合に、前記第２のデータ管理装置の情報を通知するための第３の情報通知メッセージを前記新規データ管理装置へ送信し、
前記第１の処理手段はさらに、受信した前記第３の情報通知メッセージが示す前記第２のデータ管理装置の情報を前記第１の記憶手段に格納した後で、設定完了を通知するための第２の設定完了通知メッセージを前記第２のデータ管理装置へ送信し、
前記第３の処理手段は、前記第２の設定完了通知メッセージを受信した場合に、前記第１の記憶手段に格納されている前記他のデータ管理装置の情報を、前記第３の情報通知メッセージが示す前記新規データ管理装置の情報に更新する
ことを特徴とする請求項３に記載のデータ管理装置。
【請求項５】
前記第１の処理手段は、前記新規データ管理装置の情報を通知するための第２の情報通知メッセージを前記第２のデータ管理装置へ送信する処理と、前記第２のデータ管理装置の情報を前記第１の記憶手段に格納した後で、設定完了を通知するための第２の設定完了通知メッセージを前記第２のデータ管理装置へ送信する処理とを実行し、
前記第３の処理手段は、前記第２の情報通知メッセージを受信する処理と、前記第２の設定完了通知メッセージを受信した場合に、前記第１の記憶手段に格納されている前記他のデータ管理装置の情報を、前記第２の情報通知メッセージが示す前記新規データ管理装置の情報に更新する処理とを実行する
ことを特徴とする請求項３に記載のデータ管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータネットワーク上に分散するデータを複数のデータ管理装置で管理するデータ管理システムを構成するデータ管理装置に関する。
【背景技術】
【０００２】
特定のサーバによらず、継続的あるいは一時的にネットワークに接続した計算機群によって構成される分散型のデータ管理システムがある。このシステムを利用して、例えばユーザ側ではデータの名前は分かっているが、そのデータのネットワーク上の存在場所が分からない場合に、そのデータを所持している計算機の情報を、ユーザからの要求に応じてユーザに通知するというデータの名前解決サービスを提供することができる。分散型データ管理システムとして、米国MIT大学のThe Chord Projectによるシステム（Chordシステム）が良く知られている（非特許文献１参照）。
【０００３】
Chordシステムでは、データ、およびそれを管理するデータ管理装置には、それぞれ160bitのユニークな識別子が付与されている。データに付与される識別子に関しては、データの内容によらずデータ毎に識別子がユニークであるか、データの内容毎に識別子がユニークである（つまり同一内容のデータが同一の識別子を有する）ものとする。160bitの識別子として、SHA-1（Secure Hash Algorithm 1）と呼ばれるハッシュ関数の出力値（ハッシュ値）が一般的に用いられている（非特許文献２参照）。各々の識別子は、循環する論理上の識別子空間を構成する（図１４参照）。データの管理は、識別子空間上で当該データの識別子から正の方向（図１４中の矢印Ａの方向）に見て、次に現れる識別子を持つデータ管理装置が担当することになる。以下、簡単のため、データ管理装置「x」またはデータ「x」の識別子をID(x)として説明する。
【０００４】
例として、p台のデータ管理装置でq個のデータを管理するシステムを想定する。データ管理装置の識別子を ID(s1)，ID(s2)，・・・，ID(sp)、データの識別子を ID(d1)，ID(d2)，・・・，ID(dq)とすると、識別子ID(s1)を持つデータ管理装置は、ID(sp) ＜ x ≦ 2160-1および0 ≦ x ＜ ID(s1)の範囲の識別子を有するデータを管理する。また、識別子ID(s2)を持つデータ管理装置は、ID(s1) ＜ x ＜ ID(s2)の範囲の識別子を有するデータを管理する。このように、各データ管理装置の管理範囲を示す識別子の数値範囲はデータ管理装置毎に異なっており、各数値範囲が重ならないようになっている。
【０００５】
システムを構成する各データ管理装置は、識別子空間上で自身の識別子から正の方向（図１４中の矢印Ａの方向）に見て、次に現れる識別子を持つデータ管理装置を、自らのSUCCESSORとして認識している。「認識している」とは、SUCCESSORのIPアドレスとポート番号とを保持しており、SUCCESSORとの間でメッセージを送受信可能であることを表す。同様に、各データ管理装置は、識別子空間上で自身の識別子から負の方向（図１４中の矢印Ｂの方向）に見て、次に現れる識別子を持つデータ管理装置を、自らのPREDECESSORとして認識している。また、各データ管理装置は、自身がSUCCESSORとして認識しているデータ管理装置に対して、そのPREDECESSORの情報を定期的に確認する。これにより、各データ管理装置は、SUCCESSORおよびPREDECESSORの情報を常に正しく保つ。
【０００６】
次に、図１５を用いて、動作中のデータ管理システムに新たなデータ管理装置（新規データ管理装置）が追加される際のプロセスを説明する。なお、図の横軸は識別子空間の一部を示し、Succ(X)，Pred(X)はそれぞれ、データ管理装置Xが認識しているSUCCESSORおよびPREDECESSORを示す。新規データ管理装置が追加される前のデータ管理システムでは、各データ管理装置は互いにSUCCESSOR/PREDECESSORを認識している（図１５（ａ））。
【０００７】
続いて、データ管理装置nがシステムに新しく追加される。このとき、データ管理装置nの識別子は既知であり、かつデータ管理装置nは動作中の少なくとも１台のデータ管理装置を認識しているものとする。また、初期状態ではSucc(X) ＝ Null，Pred(X) = Nullとする。データ管理装置nは、認識している既存のデータ管理装置に対して、自身の識別子を管理範囲内とする（つまり自分にとってSUCCESSORとなる）データ管理装置を尋ね、データ管理装置nsが当該装置であるとの通知を受け、SUCCESSORとしてデータ管理装置nsを認識する（図１５（ｂ））。
【０００８】
続いて、データ管理装置nは、SUCCESSORであるデータ管理装置nsに対して、自身がデータ管理装置nsにとってPREDECESSORであることを通知する。通知を受けたデータ管理装置nsは、自身のPREDECESSORに関する情報を更新し、新たにデータ管理装置nをPREDECESSORとして認識する（図１５（ｃ））。一方、データ管理装置npは、自身がSUCCESSORとして認識しているデータ管理装置に対して、そのPREDECESSORの情報を定期的に確認する。なお、この確認処理（Stabilization処理）は全てのデータ管理装置が定期的に行っているが、ここでは説明の煩雑さを避けるため、データ管理装置npについてのみ触れることとする。
【０００９】
データ管理装置npからの確認要求を受信したデータ管理装置nsは、自身のPREDECESSORがデータ管理装置nであることを通知する。ここで、本来であれば「SUCCESSORにとってのPREDECESSOR」＝「自身」であるべきところが、「SUCCESSORにとってのPREDECESSOR」≠「自身」であることを検知したデータ管理装置npは、自身のSUCCESSORに関する情報を更新し、SUCCESSORとしてデータ管理装置nを認識する（図１５（ｄ））。
【００１０】
SUCCESSORとして新たにデータ管理装置nを認識したデータ管理装置npは、自身（np）がPREDECESSORであることをデータ管理装置nに通知する。通知を受けたデータ管理装置nは、自身のPREDECESSORに関する情報を更新し、PREDECESSORとしてデータ管理装置npを認識する（図１５（ｅ））。以上のプロセスにより、全データ管理装置のSUCCESSOR/PREDECESSORが正しく更新される。
【非特許文献１】I. Stoica，et. al.，“Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications”，Proceedings of the 2001 ACM SIGCOMM Conference，2001
【非特許文献２】FIPS 180-1，“Secure Hash Standard”，U.S. Department of Commerce/NIST，National Technical Information Service，Springfield，VA，Apr. (1995)
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかし、上記のような従来のデータ管理装置の追加プロセスでは、当該追加プロセスが終了するまでの間、ある範囲の識別子を管理するデータ管理装置が一時的にシステムに存在しない状態が生じる。例えば図１５の例では、図１５（ｃ）および（ｄ）の時点において、ID(np)からID(n)までの範囲がどのデータ管理装置の担当でもない状態となる。これは、各データ管理装置が、PREDECESSORの識別子から自身の識別子までの領域を担当しているからである。このため、図１４（ｃ）および（ｄ）の時点において、ID(np)からID(n)までの範囲の識別子について、新規データ情報の登録やデータの名前解決が不可能となり、データ管理システムが不安定となるという問題があった。
【００１２】
本発明は、上述した問題点に鑑みてなされたものであって、データ管理システムに新たなデータ管理装置が追加される際にも、データ管理システムの安定性を保つように適切な処理を行うことができるデータ管理装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、上記の課題を解決するためになされたもので、コンピュータネットワーク上に分散するデータを複数のデータ管理装置で管理するデータ管理システムを構成し、前記複数のデータ管理装置が配置された論理空間における所定範囲に対応したデータを管理するデータ管理装置において、前記論理空間上で自身に隣接する他のデータ管理装置の情報を記憶する第１の記憶手段（図１の経路表記憶部１３に対応）と、前記データ管理システムに新たに追加される新規データ管理装置として動作する場合に、第１および第２のデータ管理装置の情報を前記第１の記憶手段に格納する第１の処理手段（図１の処理部１１に対応しており、特に後述する第１の動作例ではJoin処理部１１０に対応）と、前記第１のデータ管理装置として動作する場合に、前記新規データ管理装置が前記第１のデータ管理装置の情報を前記第１の記憶手段に格納した後で、前記第１の記憶手段に格納されている前記他のデータ管理装置の情報を前記新規データ管理装置の情報に更新する第２の処理手段（図１の処理部１１に対応しており、特に後述する第１の動作例ではメッセージ処理部１１２に対応）と、前記第２のデータ管理装置として動作する場合に、前記新規データ管理装置が前記第２のデータ管理装置の情報を前記第１の記憶手段に格納した後で、前記第１の記憶手段に格納されている前記他のデータ管理装置の情報を前記新規データ管理装置の情報に更新する第３の処理手段（図１の処理部１１に対応しており、特に後述する第１の動作例ではStabilization処理部１１１に対応）とを備えたことを特徴とするデータ管理装置である。
【００１４】
また、本発明のデータ管理装置は、前記論理空間における所定範囲に対応したデータの情報を記憶する第２の記憶手段（図１のデータ管理表記憶部１４に対応）をさらに備え、前記第１の処理手段はさらに、前記所定範囲に対応したデータの情報を前記第１または第２のデータ管理装置から受信して前記第２の記憶手段に格納する（後述する第１の動作例（特に図５のステップＳ１０５）、第２の動作例、第３の動作例に対応）ことを特徴とする。
【００１５】
また、本発明のデータ管理装置において、前記第１の処理手段は、前記新規データ管理装置の情報を通知するための第１の情報通知メッセージを前記第１のデータ管理装置へ送信する処理（後述する第１の動作例（特に図５のステップＳ１０２）、第２の動作例、第３の動作例に対応）と、前記第１のデータ管理装置の情報を前記第１の記憶手段に格納した後で、設定完了を通知するための第１の設定完了通知メッセージを前記第１のデータ管理装置へ送信する処理（後述する第１の動作例（特に図５のステップＳ１０４）、第２の動作例、第３の動作例に対応）とを実行し、前記第２の処理手段は、前記第１の設定完了通知メッセージを受信した場合に、前記第１の記憶手段に格納されている前記他のデータ管理装置の情報を、受信した前記第１の情報通知メッセージが示す前記新規データ管理装置の情報に更新する（後述する第１の動作例（特に図５のステップＳ２０５）、第２の動作例、第３の動作例に対応）ことを特徴とする。
【００１６】
また、本発明のデータ管理装置において、前記第２の処理手段はさらに、前記新規データ管理装置の情報を通知するための第２の情報通知メッセージを前記第２のデータ管理装置へ送信し（後述する第１の動作例（特に図５のステップＳ２０４）、第２の動作例に対応）、前記第３の処理手段は、前記第２の情報通知メッセージを受信した場合に、前記第２のデータ管理装置の情報を通知するための第３の情報通知メッセージを前記新規データ管理装置へ送信し（後述する第１の動作例（特に図５のステップＳ３０３）、第２の動作例に対応）、前記第１の処理手段はさらに、受信した前記第３の情報通知メッセージが示す前記第２のデータ管理装置の情報を前記第１の記憶手段に格納した後で、設定完了を通知するための第２の設定完了通知メッセージを前記第２のデータ管理装置へ送信し（後述する第１の動作例（特に図５のステップＳ１０４）、第２の動作例に対応）、前記第３の処理手段は、前記第２の設定完了通知メッセージを受信した場合に、前記第１の記憶手段に格納されている前記他のデータ管理装置の情報を、前記第３の情報通知メッセージが示す前記新規データ管理装置の情報に更新する（後述する第１の動作例（特に図５のステップＳ３０４）、第２の動作例に対応）ことを特徴とする。
【００１７】
また、本発明のデータ管理装置において、前記第１の処理手段は、前記新規データ管理装置の情報を通知するための第２の情報通知メッセージを前記第２のデータ管理装置へ送信する処理と、前記第２のデータ管理装置の情報を前記第１の記憶手段に格納した後で、設定完了を通知するための第２の設定完了通知メッセージを前記第２のデータ管理装置へ送信する処理とを実行し、前記第３の処理手段は、前記第２の情報通知メッセージを受信する処理と、前記第２の設定完了通知メッセージを受信した場合に、前記第１の記憶手段に格納されている前記他のデータ管理装置の情報を、前記第２の情報通知メッセージが示す前記新規データ管理装置の情報に更新する処理とを実行することを特徴とする。この発明は、後述する第３の動作例に対応している。
【００１８】
上記において、括弧で括った部分の記述は、後述する本発明の実施形態と本発明の構成要素とを便宜的に対応付けるためのものであり、この記述によって本発明の内容が限定されるわけではない。
【発明の効果】
【００１９】
上記のように、データ管理システムに新たに追加される新規データ管理装置が、論理空間上で自身に隣接する各データ管理装置の情報を自身の第１の記憶手段に格納した後に、論理空間上で新規データ管理装置に隣接する各データ管理装置が、自身の第１の記憶手段に格納されている情報を新規データ管理装置の情報に更新する。これによって、論理空間上の任意の位置に対応するデータ管理装置が常に存在する状態が保たれる。したがって、本発明のデータ管理装置によれば、データ管理システムに新たなデータ管理装置が追加される際にも、データ管理システムの安定性を保つように適切な処理を行うことができるという効果が得られる。
【発明を実施するための最良の形態】
【００２０】
以下、図面を参照し、本発明の実施形態を説明する。図１は、本発明の一実施形態による分散型のデータ管理システムの構成を示している。図１において、複数のデータ管理装置１、ユーザ端末２、データファイル蓄積装置３が、通信ネットワーク４００を介して互いに通信を行うことが可能なように接続されている。データ管理装置１、ユーザ端末２、およびデータファイル蓄積装置３は共にコンピュータである。各々のデータ管理装置１、ユーザ端末２、およびデータファイル蓄積装置３では、データの加工や演算を行う処理装置、データを保存するための記憶装置、ユーザがコンピュータへの指示を入力するための入力装置、および処理結果を出力する出力装置等のハードウェアと、コンピュータを制御する手順や命令をまとめたソフトウェア（プログラム）とが協働して動作することによって、所望の機能が実現される。
【００２１】
データ管理装置１において、通信処理部１０は、他のデータ管理装置１やユーザ端末２、データファイル蓄積装置３との通信を制御し、各種メッセージの送信や受信を行う。処理部１１は、データ管理に係る様々な処理を実行する。一時記憶部１２は、処理中の情報を一時的に記憶する。経路表記憶部１３は経路表を記憶し、データ管理表記憶部１４はデータ管理表を記憶する。経路表およびデータ管理表の詳細は後述する。経路表記憶部１３とデータ管理表記憶部１４は異なる記録媒体で構成されていてもよいし、同一の記録媒体内の異なる記録領域で構成されていてもよい。
【００２２】
処理部１１において、Join処理部１１０は、自身のデータ管理装置１がデータ管理システムに新たに追加される場合に、経路表記憶部１３に格納される経路表に対する情報の設定に係る処理を実行する。Stabilization処理部１１１は、自身のデータ管理装置１がSUCCESSORとして認識している他のデータ管理装置１に対して、そのPREDECESSORの情報を定期的に確認するStabilization処理を実行する。メッセージ処理部１１２は、他のデータ管理装置１やユーザ端末２から受信されたメッセージに基づいて様々な処理を実行する。
【００２３】
経路表記憶部１３が記憶する経路表には、他のデータ管理装置１との通信に必要な情報（例えばIPアドレスおよびポート番号）が含まれている。図２は経路表の一例を示している。経路表は、SUCCESSORおよびPREDECESSORを管理する２つのエントリと、「SUCCESSOR List」または「Finger Table」と呼ばれる部分とから成る。
【００２４】
SUCCESSORを管理するエントリには、SUCCESSORとなる他のデータ管理装置１の識別子（装置識別子）と、そのデータ管理装置１のIPアドレスおよびポート番号とが含まれている。PREDECESSORを管理するエントリには、PREDECESSORとなる他のデータ管理装置１の識別子（装置識別子）と、そのデータ管理装置１のIPアドレスおよびポート番号とが含まれている。「SUCCESSOR List」または「Finger Table」には、m台分（m≧0）のデータ管理装置１の識別子（装置識別子）と、それらのデータ管理装置１のIPアドレスおよびポート番号とが含まれている。
【００２５】
データ管理表記憶部１４が記憶するデータ管理表には、自身のデータ管理装置１が管理する所定の数値範囲内の識別子が付与されたデータについての情報が含まれている。図３はデータ管理表の一例を示している。図３が示すようにデータ管理表には、個々のデータについて、各データに付与されている識別子（データ識別子）、および各データが保存されているデータファイル蓄積装置３のIPアドレスとポート番号を示す情報が含まれている。
【００２６】
図１に示される各装置は、必要に応じて各種メッセージの送受信を行う。図４はメッセージの一例を示している。宛先IPアドレスフィールド５０１、宛先ポート番号フィールド５０２には、それぞれメッセージの宛先である装置のIPアドレス、ポート番号が記録されている。送信元IPアドレスフィールド５０３、送信元ポート番号フィールド５０４には、それぞれメッセージの送信元である装置のIPアドレス、ポート番号が記録されている。処理対象識別子フィールド５０５には、処理対象となる識別子が記録されている。メッセージ内容フィールド５０６には、後述する４種類のメッセージ内容のうちのいずれか１つが記録されている。発信元IPアドレスフィールド５０７、発信元ポート番号フィールド５０８には、それぞれメッセージを作成し、最初に発信した装置のIPアドレス、ポート番号が記録されている。
【００２７】
メッセージを最初に発信する装置は、送信元IPアドレスフィールド５０３と発信元IPアドレスフィールド５０７、送信元ポート番号フィールド５０４と発信元ポート番号フィールド５０８にそれぞれ同一の情報を記録する。また、他装置から受信したメッセージを転送する装置は、送信元IPアドレスフィールド５０３と送信元ポート番号フィールド５０４を自身の情報に書き換えると共に、宛先IPアドレスフィールド５０１と宛先ポート番号フィールド５０２を転送先の装置の情報に書き換えてメッセージを送信する。
【００２８】
メッセージ内容は、「担当装置確認要求」、「PREDECESSOR通知」、「PREDECESSOR確認要求」、「設定完了通知」のいずれかである。「担当装置確認要求」は、処理対象識別子で示されるデータの管理を担当しているデータ管理装置１の情報の確認を要求することを示している。「PREDECESSOR通知」は、PREDECESSORの情報を通知することを示している。「PREDECESSOR確認要求」は、PREDECESSORの情報の確認を要求することを示している。「設定完了通知」は、新しくデータ管理システムに追加されたデータ管理装置１のSUCCESSOR/PREDECESSOR両エントリの設定完了を通知することを示している。
【００２９】
メッセージ内容が「担当装置確認要求」の場合、処理対象識別子フィールドには、確認対象となるデータの識別子が記録されている。メッセージ内容が「PREDECESSOR通知」の場合、処理対象識別子フィールドには、メッセージの宛先にとって新たなPREDECESSORとなるデータ管理装置１の識別子が記録されている。メッセージ内容が「PREDECESSOR確認要求」および「設定完了通知」の場合、処理対象識別子フィールドは使用されない。
【００３０】
次に、本実施形態によるデータ管理システムの動作を説明する。まず、図５および図６を参照し、新たなデータ管理装置がデータ管理システムに追加される場合のデータ管理装置の動作（第１の動作例）を説明する。本動作例では、データ管理装置npとnsの間にデータ管理装置nが新しく追加される場合を想定する。データ管理装置nが追加される前のデータ管理システムでは、各データ管理装置は互いにSUCCESSORとPREDECESSORを認識している。データ管理装置Xが認識しているSUCCESSORおよびPREDECESSORをそれぞれSucc(X)，Pred(X)とすると、初期状態ではSucc(np) = ns，Pred(ns) = npである。また、Pred(np) = n1，Succ(ns) = n2とする（図６（ａ））。
【００３１】
まず、新しくシステムに加入するデータ管理装置n（Succ(n) = Null，Pred(n) = Null）は、あらかじめ認識しているデータ管理装置に対して、自身の識別子（ID(n)）を担当するデータ管理装置（つまりID(n)にとってのSUCCESSOR）を尋ねる。具体的には、データ管理装置nのJoin処理部１１０は、ID(n)を担当するデータ管理装置を問い合わせるため、メッセージ内容が「担当装置確認要求」を示すメッセージを生成し、通信処理部１０へ出力する。通信処理部１０は、あらかじめ認識しているデータ管理装置へメッセージを送信する（ステップＳ１００）。そのデータ管理装置からメッセージの返信があった場合、通信処理部１０は、受信したメッセージをJoin処理部１１０へ出力する。Join処理部１１０はメッセージの内容を解析し、ID(n)を担当するデータ管理装置が存在するか否かを判断する（ステップＳ１０１）。
【００３２】
ID(n)を担当するデータ管理装置が存在しない場合には処理が終了する。また、ID(n)を担当するデータ管理装置が存在する場合、Join処理部１１０はそのデータ管理装置の情報（識別子、IPアドレス、ポート番号）をメッセージから抽出して一時記憶部１２に保存すると共に、経路表記憶部１３にその情報を格納し、経路表のSUCCESSORとして設定する。また、Join処理部１１０は、そのSUCCESSOR（データ管理装置ns）に対して、自身の情報（識別子、IPアドレス、ポート番号）と、自身がPREDECESSORであることとを通知するため、メッセージ内容が「PREDECESSOR通知」を示すメッセージ（本発明の第１の情報通知メッセージに対応）を生成し、通信処理部１０を介してメッセージを送信する（ステップＳ１０２）。
【００３３】
通知を受けたデータ管理装置nsは、その情報を一時記憶部１２に保存する。すなわち、メッセージ処理部１１２は、通信処理部１０を介してデータ管理装置nからのメッセージを受信し、メッセージに含まれるデータ管理装置nの情報を一時記憶部１２に保存する（ステップＳ２００）。この時点では、Succ(n) = ns，Pred(n) = Nullである（図６（ｂ））。
【００３４】
続いて、データ管理装置npは、自身がSUCCESSORとして認識しているデータ管理装置に対して、PREDECESSORの情報を定期的に確認する。具体的には、Stabilization処理部１１１は、メッセージ内容が「PREDECESSOR確認要求」を示すメッセージを生成し、通信処理部１０を介してデータ管理装置nsへメッセージを送信する（ステップＳ３００）。なお、この確認処理（Stabilization処理）は全てのデータ管理装置が定期的に行っているが、ここでは説明の煩雑さを避けるため、データ管理装置npについてのみ触れることとする。
【００３５】
データ管理装置npからのメッセージを受信したデータ管理装置nsは、自身が保有するPREDECESSORの情報をデータ管理装置npに通知する。具体的には、まずメッセージ処理部１１２は、通信処理部１０を介してメッセージを受信する（ステップＳ２０１）。続いて、メッセージ処理部１１２は、ステップＳ２００で保存したPREDECESSORの情報を一時記憶部１２から読み出すと共に、経路表記憶部１３内の経路表からPREDECESSORの情報を読み出し、両者を比較する（ステップＳ２０２）。
【００３６】
比較の結果、両者が異なる場合には、メッセージ処理部１１２は、一時記憶部１２のPREDECESSORの情報を含むメッセージ（本発明の第２の情報通知メッセージに対応）を生成し、通信処理部１０を介してメッセージをデータ管理装置npへ送信する（ステップＳ２０３）。また、ステップＳ２０２での比較の結果、両者が同一の場合には、メッセージ処理部１１２は、経路表のPREDECESSORの情報を含むメッセージを生成し、通信処理部１０を介してメッセージをデータ管理装置npへ送信する（ステップＳ２０４）。本例では、一時記憶部１２のPREDECESSORの情報と経路表のPREDECESSORの情報が異なるため、一時記憶部１２に記録されているPREDECESSORの情報（データ管理装置nの情報）がデータ管理装置npに通知される。
【００３７】
データ管理装置npにおいて、Stabilization処理部１１１は、通信処理部１０を介してSUCCESSORからのメッセージを受信し、メッセージに含まれる情報を一時記憶部１２にノード情報として保存する（ステップＳ３０１、図６（ｃ））。続いて、Stabilization処理部１１１は、一時記憶部１２に保存したノード情報を自身のノード情報と比較する（ステップＳ３０２）。
【００３８】
比較の結果、両者が同一であった場合、Stabilization処理部１１１は、「SUCCESSORにとってのPREDECESSOR」＝「自身」と正しく設定されていると判断し、処理を終了する。また、比較の結果、両者が異なる場合、Stabilization処理部１１１は、「SUCCESSORにとってのPREDECESSOR」≠「自身」であると判断し、一時記憶部１２に保存されているノード情報に対応するデータ管理装置（データ管理装置n）に対して、自身の情報（識別子、IPアドレス、ポート番号）と、自身がPREDECESSORであることとを通知するためのメッセージ（本発明の第３の情報通知メッセージに対応）を生成し、通信処理部１０を介してメッセージを送信する（ステップＳ３０３）。
【００３９】
データ管理装置nにおいて、Join処理部１１０は、通信処理部１０を介してデータ管理装置npからのメッセージを受信し、メッセージに含まれる情報を一時記憶部１２に保存すると共に、経路表記憶部１３にその情報を格納し、経路表のPREDECESSORとして設定する（ステップＳ１０３）。この時点では、Succ(n) = ns，Pred(n) = npである（図６（ｄ））。データ管理装置nは、SUCCESSORおよびPREDECESSOR両エントリの設定が完了したため、両エントリに対応するデータ管理装置に対して、設定完了を通知する。具体的には、Join処理部１１０は、設定完了を通知するため、メッセージ内容が「設定完了通知」を示すメッセージ（本発明の設定完了通知メッセージに対応）を生成し、通信処理部１０を介して、データ管理装置nsおよびnpへメッセージを送信する（ステップＳ１０４）。
【００４０】
データ管理装置nからのメッセージを受信したデータ管理装置nsおよびnpは、それぞれ一時記憶部１２に保存されていた情報で経路表を更新する。具体的には、データ管理装置nsにおいて、メッセージ処理部１１２は、通信処理部１０を介してデータ管理装置nからのメッセージを受信し、設定完了を示すそのメッセージに基づいて、ステップＳ２００で保存した情報（データ管理装置nの情報）を一時記憶部１２から読み出し、経路表記憶部１３内の経路表に格納されているPREDECESSORエントリの情報を、一時記憶部１２から読み出した情報に書き換える（ステップＳ２０５）。
【００４１】
また、データ管理装置npにおいて、Stabilization処理部１１１は、通信処理部１０を介してデータ管理装置nからのメッセージを受信し、設定完了を示すそのメッセージに基づいて、ステップＳ３０１で保存した情報（データ管理装置nの情報）を一時記憶部１２から読み出し、経路表記憶部１３内の経路表に格納されているSUCCESSORエントリの情報を、一時記憶部１２から読み出した情報に書き換える（ステップＳ３０４）。
【００４２】
上記の処理に続いて、データ管理表の設定処理および更新処理が行われる。データ管理装置nsのメッセージ処理部１１２は、データ管理表記憶部１４内のデータ管理表に格納されている情報のうち、識別子が (np, n] （np+1以上かつn以下）であるエントリの情報を含むメッセージを生成する。メッセージ処理部１１２は、通信処理部１０を介して、PREDECESSORとして認識しているデータ管理装置nへメッセージを送信し、上記のエントリをデータ管理表から削除する（ステップＳ２０６）。
【００４３】
データ管理装置nのJoin処理部１１０は、通信処理部１０を介してメッセージを受信し、メッセージに含まれる上記のエントリの情報をデータ管理表に格納する（ステップＳ１０５）。この時点では、Succ(np) = n，Pred(ns) = nであり（図６（ｅ））、各データ管理装置における経路表およびデータ管理表に係る処理が終了する。
【００４４】
上記の動作によれば、データ管理装置が新しくデータ管理システムに追加される動作の途中においても、任意の識別子に対して、常に当該識別子を担当するデータ管理装置が存在するため、任意の識別子に対して常に新規データ情報の登録やデータの名前解決が可能となる。
【００４５】
図５では、メッセージ処理部１１２の動作のうち、新規データ管理装置の追加に関係する動作しか示されていない。そこで、図７を参照し、メッセージ処理部１１２全体の動作を説明する。通信処理部１０は、メッセージの宛先IPアドレスおよび宛先ポート番号が自身を指すメッセージのみ受信し、メッセージ処理部１１２へメッセージを出力する（ステップＳ４００ ）。メッセージ処理部１１２はメッセージを参照し、メッセージ内容を判断する（ステップＳ４０１）。この判断結果に応じて、ステップＳ４０２〜Ｓ４０５のいずれかの処理が行われる。
【００４６】
メッセージ内容が担当装置確認要求であった場合には、処理Aが行われ（ステップＳ４０２）、メッセージ内容がPREDECESSOR通知であった場合には、処理Bが行われ（ステップＳ４０３）、メッセージ内容がPREDECESSOR確認であった場合には、処理Cが行われ（ステップＳ４０４）メッセージ内容が設定完了通知であった場合には、処理Dが行われる（ステップＳ４０５）。
【００４７】
次に、ステップＳ４０２〜Ｓ４０５の処理の詳細を説明する。図８は処理Aの内容を示している。データの管理を担当しているデータ管理装置１の情報の確認がメッセージの発信元から要求されている場合、メッセージ処理部１１２はメッセージ内の処理対象識別子を確認し、その処理対象識別子が、自身の担当する識別子の範囲に含まれるか否かを判定する（ステップＳ５０１）。処理対象識別子が、自身の担当する識別子の範囲に含まれる場合、メッセージ処理部１１２は、発信元に対して、自身のデータ管理装置１が担当装置であることを通知するためのメッセージを生成し、通信処理部１０を介してメッセージを発信元へ送信する（ステップＳ５０２）。
【００４８】
また、処理対象識別子が、自身の担当する識別子の範囲に含まれていない場合、メッセージ処理部１１２は経路表記憶部１３から経路表を読み出し（ステップＳ５０３）、経路表内のデータ管理装置１の識別子と処理対象識別子を比較して、メッセージの転送先となるデータ管理装置１を決定する（ステップＳ５０４）。続いて、メッセージ処理部１１２はメッセージの宛先IPアドレスおよび宛先ポート番号を転送先のデータ管理装置１のIPアドレスおよびポート番号に書き換えると共に、送信元IPアドレスおよび送信元ポート番号を自身のIPアドレスおよびポート番号に書き換え、通信処理部１０を介してメッセージを転送する（ステップＳ５０５）。
【００４９】
図９は処理Bの内容を示している。メッセージが宛先にとっての新たなPREDECESSORを通知している場合、メッセージ処理部１１２は、メッセージに含まれる新規PREDECESSORの識別子、IPアドレス、ポート番号の情報（メッセージ中の処理対象識別子、発信元IPアドレス、発信元ポート番号の各情報）を一時記憶部１２に保存する（ステップＳ６００）。
【００５０】
図１０は処理Cの内容を示している。自身のPREDECESSORの情報がメッセージの発信元から要求されている場合、メッセージ処理部１１２は、図９のステップＳ６００で保存したPREDECESSORの情報を一時記憶部１２から読み出すと共に、経路表記憶部１３内の経路表からPREDECESSORの情報を読み出し、両者を比較する（ステップＳ７００）。
【００５１】
比較の結果、両者が異なる場合には、メッセージ処理部１１２は、一時記憶部１２に保存されているPREDECESSORの情報を含むメッセージを生成し、通信処理部１０を介してメッセージを発信元へ送信する（ステップＳ７０１）。また、ステップＳ７００での比較の結果、両者が同一の場合には、メッセージ処理部１１２は、経路表に格納されているPREDECESSORの情報を含むメッセージを生成し、通信処理部１０を介してメッセージを発信元へ送信する（ステップＳ７０２）。
【００５２】
図１１は処理Dの内容を示している。新しくデータ管理システムに追加されたデータ管理装置１のSUCCESSOR/PREDECESSOR両エントリの設定完了が通知された場合、メッセージ処理部１１２は、図９のステップＳ６００で保存したPREDECESSORの情報を一時記憶部１２から読み出し、経路表記憶部１３内の経路表に格納されているPREDECESSORエントリの情報を、一時記憶部１２から読み出した情報に書き換えることによって、経路表の内容を更新する（ステップＳ８００）。
【００５３】
続いて、メッセージ処理部１１２は、データ管理表記憶部１４内のデータ管理表に格納されている情報のうち、新しくデータ管理システムに追加されたデータ管理装置が担当すべき識別子が格納されているエントリの情報を含むメッセージを生成する。メッセージ処理部１１２は、通信処理部１０を介して、PREDECESSORとして認識しているデータ管理装置１へメッセージを送信し、上記のエントリをデータ管理表から削除する（ステップＳ８０１）。
【００５４】
次に、図１２を参照し、新たなデータ管理装置がデータ管理システムに追加される場合のデータ管理装置の動作の変形例（第２の動作例）を説明する。第２の動作例は、上述した第１の動作例におけるSUCCESSORとPREDECESSORの役割を逆にしたものであり、第２の動作例でも第１の動作例と同様の効果が得られる。本動作例でも、データ管理装置npとnsの間にデータ管理装置nが新しく追加される場合を想定する。
【００５５】
データ管理装置nが追加される前のデータ管理システムでは、各データ管理装置は互いにSUCCESSORとPREDECESSORを認識しており、初期状態ではSucc(np) = ns，Pred(ns) = npである（図１２（ａ））。新しくシステムに加入するデータ管理装置n（Succ(n) = Null，Pred(n) = Null）は、あらかじめ認識しているデータ管理装置に対して、自身の識別子（ID(n)）を担当するデータ管理装置の経路表上のPREDECESSOR（つまりID(n)にとってのPREDECESSOR）を尋ねる。
【００５６】
具体的には、データ管理装置nのJoin処理部１１０は、問い合わせのためのメッセージを生成し、通信処理部１０を介して、あらかじめ認識しているデータ管理装置へメッセージを送信する。そのデータ管理装置からメッセージの返信があり、ID(n)にとってのPREDECESSORが見つかった場合、Join処理部１１０はPREDECESSORの情報（識別子、IPアドレス、ポート番号）をメッセージから抽出して一時記憶部１２に保存すると共に、経路表記憶部１３にその情報を格納し、経路表のPREDECESSORとして設定する。
【００５７】
また、Join処理部１１０は、PREDECESSOR（データ管理装置np）に対して、自身の情報（識別子、IPアドレス、ポート番号）と、自身がSUCCESSORであることとを通知するためのメッセージ（本発明の第１の情報通知メッセージに対応）を生成し、通信処理部１０を介してメッセージを送信する。データ管理装置npのメッセージ処理部１１２は、通信処理部１０を介してデータ管理装置nからのメッセージを受信し、メッセージに含まれるデータ管理装置nの情報を一時記憶部１２に保存する。この時点では、Succ(n) = Null，Pred(n) = npである（図１２（ｂ））。
【００５８】
続いて、データ管理装置nsは、自身がPREDECESSORとして認識しているデータ管理装置に対して、SUCCESSORの情報を確認するためのメッセージを定期的に送信する。具体的には、データ管理装置nsのStabilization処理部１１１は、SUCCESSOR確認用のメッセージを生成し、通信処理部１０を介してデータ管理装置npへメッセージを送信する。なお、この確認処理は全てのデータ管理装置が定期的に行っているが、ここでは説明の煩雑さを避けるため、データ管理装置nsについてのみ触れることとする。
【００５９】
データ管理装置nsからのメッセージを受信したデータ管理装置npは、自身が保有するSUCCESSORの情報をデータ管理装置npに通知する。具体的には、データ管理装置npのメッセージ処理部１１２は、SUCCESSORの情報を一時記憶部１２から読み出すと共に、経路表記憶部１３内の経路表からSUCCESSORの情報を読み出し、両者を比較する。比較の結果、両者が異なる場合には、メッセージ処理部１１２は、一時記憶部１２のSUCCESSORの情報を含むメッセージ（本発明の第２の情報通知メッセージに対応）を生成し、通信処理部１０を介してメッセージをデータ管理装置nsへ送信する。
【００６０】
また、比較の結果、両者が同一の場合には、メッセージ処理部１１２は、経路表のSUCCESSORの情報を含むメッセージを生成し、通信処理部１０を介してメッセージをデータ管理装置nsへ送信する。本例では、一時記憶部１２のSUCCESSORの情報と経路表のSUCCESSORの情報が異なるため、一時記憶部１２に記録されているSUCCESSORの情報（データ管理装置nの情報）がデータ管理装置nsに通知される。データ管理装置nsにおいて、Stabilization処理部１１１は、通信処理部１０を介してデータ管理装置npからのメッセージを受信し、メッセージに含まれる情報を一時記憶部１２にノード情報として保存する（図１２（ｃ））。
【００６１】
続いて、Stabilization処理部１１１は、一時記憶部１２に保存したノード情報を自身のノード情報と比較する。比較の結果、両者が同一であった場合、Stabilization処理部１１１は、「PREDECESSORにとってのSUCCESSOR」＝「自身」と正しく設定されていると判断し、処理を終了する。また、比較の結果、両者が異なる場合、Stabilization処理部１１１は、「PREDECESSORにとってのSUCCESSOR」≠「自身」であると判断し、一時記憶部１２に保存されているノード情報に対応するデータ管理装置（データ管理装置n）に対して、自身の情報（識別子、IPアドレス、ポート番号）と、自身がSUCCESSORであることとを通知するためのメッセージ（本発明の第３の情報通知メッセージに対応）を生成し、通信処理部１０を介してメッセージを送信する。
【００６２】
データ管理装置nにおいて、Join処理部１１０は、通信処理部１０を介してデータ管理装置nsからのメッセージを受信し、メッセージに含まれる情報を一時記憶部１２に保存すると共に、経路表記憶部１３にその情報を格納し、経路表のSUCCESSORとして設定する。この時点では、Succ(n) = ns，Pred(n) = npである（図１２（ｄ））。データ管理装置nは、SUCCESSORおよびPREDECESSOR両エントリの設定が完了したため、両エントリに対応するデータ管理装置に対して、設定完了を通知する。具体的には、Join処理部１１０は、設定完了を通知するためのメッセージ（本発明の設定完了通知メッセージに対応）を生成し、通信処理部１０を介して、データ管理装置nsおよびnpへメッセージを送信する。
【００６３】
データ管理装置nからのメッセージを受信したデータ管理装置nsおよびnpは、それぞれ一時記憶部１２に保存されていた情報で経路表を更新する。具体的には、データ管理装置nsにおいて、Stabilization処理部１１１は、通信処理部１０を介してデータ管理装置nからのメッセージを受信し、設定完了を示すそのメッセージに基づいて、データ管理装置nの情報を一時記憶部１２から読み出し、経路表記憶部１３内の経路表に格納されているPREDECESSORエントリの情報をデータ管理装置nの情報に書き換える。
【００６４】
また、データ管理装置npにおいて、メッセージ処理部１１２は、通信処理部１０を介してデータ管理装置nからのメッセージを受信し、設定完了を示すそのメッセージに基づいて、データ管理装置nの情報を一時記憶部１２から読み出し、経路表記憶部１３内の経路表に格納されているSUCCESSORエントリの情報をデータ管理装置nの情報に書き換える。
【００６５】
上記の処理に続いて、データ管理表の設定処理および更新処理が行われる。データ管理装置nsのStabilization処理部１１１は、データ管理表記憶部１４内のデータ管理表に格納されている情報のうち、識別子が (np, n] （np+1以上かつn以下）であるエントリの情報を含むメッセージを生成する。Stabilization処理部１１１は、通信処理部１０を介して、PREDECESSORとして認識しているデータ管理装置nへメッセージを送信し、上記のエントリをデータ管理表から削除する。
【００６６】
データ管理装置nのJoin処理部１１０は、通信処理部１０を介してメッセージを受信し、メッセージに含まれる上記のエントリの情報をデータ管理表に格納する。この時点では、Succ(np) = n，Pred(ns) = nであり（図１２（ｅ））、各データ管理装置における経路表およびデータ管理表に係る処理が終了する。
【００６７】
上記の動作によれば、データ管理装置が新しくデータ管理システムに追加される動作の途中においても、任意の識別子に対して、常に当該識別子を担当するデータ管理装置が存在するため、任意の識別子に対して常に新規データ情報の登録やデータの名前解決が可能となる。
【００６８】
次に、図１３を参照し、新たなデータ管理装置がデータ管理システムに追加される場合のデータ管理装置の動作の他の変形例（第３の動作例）を説明する。第１および第２の動作例では、データ管理装置nが、あらかじめ認識しているデータ管理装置に対して、ID(n)にとってのSUCCESSORとPREDECESSORのどちらか一方を尋ねるが、第３の動作例ではそれらの両方を尋ねる。
【００６９】
データ管理装置nが追加される前のデータ管理システムでは、各データ管理装置は互いにSUCCESSORとPREDECESSORを認識しており、初期状態ではSucc(np) = ns，Pred(ns) = npである（図１３（ａ））。新しくシステムに加入するデータ管理装置n（Succ(n) = Null，Pred(n) = Null）は、あらかじめ認識しているデータ管理装置に対して、自身の識別子（ID(n)）に対するSUCCESSORおよびPREDECESSORの両方を尋ねる。
【００７０】
具体的には、データ管理装置nのJoin処理部１１０は、問い合わせのためのメッセージを生成し、通信処理部１０を介して、あらかじめ認識しているデータ管理装置へメッセージを送信する。そのデータ管理装置からメッセージの返信があり、ID(n)にとってのSUCCESSORおよびPREDECESSORが見つかった場合、Join処理部１１０はSUCCESSORおよびPREDECESSORの情報（識別子、IPアドレス、ポート番号）をメッセージから抽出して一時記憶部１２に保存すると共に、経路表記憶部１３にその情報を格納し、経路表のSUCCESSORおよびPREDECESSORとして設定する。
【００７１】
続いて、Join処理部１１０は、SUCCESSOR（データ管理装置ns）に対して、自身の情報（識別子、IPアドレス、ポート番号）と、自身がPREDECESSORであることとを通知するためのメッセージ（本発明の第１の情報通知メッセージに対応）を生成し、通信処理部１０を介してメッセージを送信する。同様に、Join処理部１１０は、PREDECESSOR（データ管理装置np）に対して、自身の情報（識別子、IPアドレス、ポート番号）と、自身がSUCCESSORであることとを通知するためのメッセージ（本発明の第２の情報通知メッセージに対応）を生成し、通信処理部１０を介してメッセージを送信する。
【００７２】
データ管理装置nsおよびnpのメッセージ処理部１１２は、通信処理部１０を介してデータ管理装置nからのメッセージを受信し、メッセージに含まれるデータ管理装置nの情報を一時記憶部１２に保存する。この時点では、Succ(n) = ns，Pred(n) = npである（図１３（ｂ））。
【００７３】
データ管理装置nは、SUCCESSORおよびPREDECESSOR両エントリの設定が完了したため、両エントリに対応するデータ管理装置に対して、設定完了を通知する。具体的には、Join処理部１１０は、設定完了を通知するためのメッセージ（本発明の設定完了通知メッセージに対応）を生成し、通信処理部１０を介して、データ管理装置nsおよびnpへメッセージを送信する。
【００７４】
データ管理装置nからのメッセージを受信したデータ管理装置nsおよびnpは、それぞれ一時記憶部１２に保存されていた情報で経路表を更新する。具体的には、データ管理装置nsにおいて、メッセージ処理部１１２は、通信処理部１０を介してデータ管理装置nからのメッセージを受信し、設定完了を示すそのメッセージに基づいて、データ管理装置nの情報を一時記憶部１２から読み出し、経路表記憶部１３内の経路表に格納されているPREDECESSORエントリの情報をデータ管理装置nの情報に書き換える。
【００７５】
また、データ管理装置npにおいて、メッセージ処理部１１２は、通信処理部１０を介してデータ管理装置nからのメッセージを受信し、設定完了を示すそのメッセージに基づいて、データ管理装置nの情報を一時記憶部１２から読み出し、経路表記憶部１３内の経路表に格納されているSUCCESSORエントリの情報をデータ管理装置nの情報に書き換える。
【００７６】
上記の処理に続いて、データ管理表の設定処理および更新処理が行われる。データ管理装置nsのメッセージ処理部１１２は、データ管理表記憶部１４内のデータ管理表に格納されている情報のうち、識別子が (np, n] （np+1以上かつn以下）であるエントリの情報を含むメッセージを生成する。メッセージ処理部１１２は、通信処理部１０を介して、PREDECESSORとして認識しているデータ管理装置nへメッセージを送信し、上記のエントリをデータ管理表から削除する。
【００７７】
データ管理装置nのJoin処理部１１０は、通信処理部１０を介してメッセージを受信し、メッセージに含まれる上記のエントリの情報をデータ管理表に格納する。この時点では、Succ(np) = n，Pred(ns) = nであり（図１３（ｃ））、各データ管理装置における経路表およびデータ管理表に係る処理が終了する。
【００７８】
上記の動作によれば、データ管理装置が新しくデータ管理システムに追加される動作の途中においても、任意の識別子に対して、常に当該識別子を担当するデータ管理装置が存在するため、任意の識別子に対して常に新規データ情報の登録やデータの名前解決が可能となる。
【００７９】
第３の動作例における最初の段階では、SUCCESSORとPREDECESSORの両方を探索するため、どちらか一方しか探索しない第１および第２の動作例と比較して処理時間を要する。しかし、第３の動作例におけるSUCCESSORとPREDECESSOR両方の探索が終了した段階（図１３（ｂ））が、第１および第２の動作例における図６（ｄ）および図１２（ｄ）の段階に相当するため、ほぼStabilizationプロトコルの待ち時間分だけ処理時間が短縮される。このため、処理全体で比較した場合、第３の動作例では第１および第２の動作例と比較して、処理時間が短縮されるという効果が得られる。また、第３の動作例はStabilizationプロトコルを必要としないため、新規分散データ管理装置の追加処理に要する時間がほぼ一定であるという効果がある（第１および第２の動作例では、最大でStabilizationプロトコルの実行間隔分だけ処理時間がばらつく）。
【００８０】
上述したように、本実施形態では、データ管理システムに新たに追加される新規データ管理装置が、識別子空間上で自身に隣接する各データ管理装置の情報を経路表に格納した後で、識別子空間上で新規データ管理装置に隣接する各データ管理装置が経路表の情報を新規データ管理装置の情報に更新する。これによって、識別子空間上の任意の位置の識別子に対応するデータ管理装置が常に存在する状態が保たれるため、データ管理システムに新たなデータ管理装置が追加される際にも、新規データ情報の登録等が可能となる。このように、本実施形態によるデータ管理装置は、データ管理システムの安定性を保つように適切な処理を行うことができる。
【００８１】
また、経路表に対する情報の設定および更新に伴って、データ管理装置がデータ管理表に対する情報の設定および更新を行うことによって、データ管理システムに新たなデータ管理装置が追加される際にも、データの名前解決等が可能となる。
【００８２】
以上、図面を参照して本発明の実施形態について詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。例えば、図５において、経路表の設定完了が通知された後に新規データ管理装置のデータ管理表の設定が行われているが、図５において、経路表の設定完了が通知される前に新規データ管理装置のデータ管理表の設定が行われるようにしてもよい。
【図面の簡単な説明】
【００８３】
【図１】本発明の一実施形態によるデータ管理システムの構成を示すブロック図である。
【図２】本発明の一実施形態における経路表の内容を示す参考図である。
【図３】本発明の一実施形態におけるデータ管理表の内容を示す参考図である。
【図４】本発明の一実施形態におけるメッセージの構造を示す参考図である。
【図５】本発明の一実施形態によるデータ管理装置の新規データ管理装置の追加時における動作（第１の動作例）の手順を示すフローチャートである。
【図６】本発明の一実施形態における新規データ管理装置の追加時の動作（第１の動作例）を説明するための説明図である。
【図７】本発明の一実施形態によるデータ管理装置が備えるメッセージ処理部の動作の手順を示すフローチャートである。
【図８】本発明の一実施形態によるデータ管理装置が備えるメッセージ処理部の動作（処理A）の手順を示すフローチャートである。
【図９】本発明の一実施形態によるデータ管理装置が備えるメッセージ処理部の動作（処理B）の手順を示すフローチャートである。
【図１０】本発明の一実施形態によるデータ管理装置が備えるメッセージ処理部の動作（処理C）の手順を示すフローチャートである。
【図１１】本発明の一実施形態によるデータ管理装置が備えるメッセージ処理部の動作（処理D）の手順を示すフローチャートである。
【図１２】本発明の一実施形態における新規データ管理装置の追加時の動作（第２の動作例）を説明するための説明図である。
【図１３】本発明の一実施形態における新規データ管理装置の追加時の動作（第３の動作例）を説明するための説明図である。
【図１４】循環する識別子空間における識別子の配置の様子を示す参考図である。
【図１５】従来の新規データ管理装置の追加時の動作を説明するための説明図である。
【符号の説明】
【００８４】
１・・・データ管理装置、２・・・ユーザ端末、３・・・データファイル蓄積装置、１０・・・通信処理部、１１・・・処理部、１２・・・一時記憶部、１３・・・経路表記憶部、１４・・・データ管理表記憶部、１１０・・・Join処理部、１１１・・・Stabilization処理部、１１２・・・メッセージ処理部、４００・・・通信ネットワーク
【図１】
2007334638.tif 000003
【図２】
2007334638.tif 000004
【図３】
2007334638.tif 000005
【図４】
2007334638.tif 000006
【図５】
2007334638.tif 000007
【図６】
2007334638.tif 000008
【図７】
2007334638.tif 000009
【図８】
2007334638.tif 000010
【図９】
2007334638.tif 000011
【図１０】
2007334638.tif 000012
【図１１】
2007334638.tif 000013
【図１２】
2007334638.tif 000014
【図１３】
2007334638.tif 000015
【図１４】
2007334638.tif 000016
【図１５】
2007334638.tif 000017