【手続補正書】
【提出日】平成18年10月26日(2006.10.26)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】  複数ノードのシステムでのノードに対する資源を支配するための方法であって、
１組の資源の中の各資源について、
第１のハッシュ関数を用いて特定のハッシュバケットに資源を対応付けるステップと、
第２のハッシュ関数を用いて特定のノードに特定のハッシュバケットを対応付けるステップと、
前記資源のマスタとなるよう前記特定のノードを選択するステップとによって資源を支配するノードを選択するステップと、
前記第１のハッシュ関数を変更することなしに前記第２のハッシュ関数を変更することによってエポック変更に応答するステップとを含み、
前記第２のハッシュ関数を変更するステップは、
前記エポック変更後に初期再構成を実行するステップを含み、前記初期再構成は、エポック変更後に存在するノードにエポック変更中に取除かれたノードに対応付けられた１組のバケットを再対応付するステップを含み、さらに、
前記初期再構成を実行した後、
複数ノードのシステムを一般的に利用可能にするステップと、
複数ノードのシステムが一般的に利用可能である一方で、不足ノードに割当てられたバケットの数がターゲットバケット数に等しくなるまで過剰ノードに現在対応付けられている１つ以上のバケットを不足ノードに移動するステップとを実行するステップを含み、
エポック変更は、複数ノードのシステムにおけるノードの数の変更であり、
不足ノードは、現在割当てられている範囲がターゲットバケット数より少ない数のバケットに及ぶ複数ノードのシステムにおけるノードであり、
過剰ノードは、現在割当てられている範囲がターゲットバケット数より大きい数のバケットに及ぶ複数ノードのシステムにおけるノードであり、
ターゲットバケット数は、バケットを複数ノードのシステムにおけるノード間で均等に分散するために複数ノードのシステムにおける各ノードが持たなければならないバケットの数である、方法。
【請求項２】  エポック変更前に、第１の数のノードを用いて前記資源の組からの資源を支配し、
エポック変更後に、第２の数のノードを用いて前記資源の組からの資源を支配し、
前記方法は前記第１のハッシュ関数を用いてある数のバケットに資源をハッシュするステップを含み、前記ある数のバケットは前記第１の数および前記第２の数のどちらよりも大きい、請求項１に記載の方法。
【請求項３】  前記第２のハッシュ関数はバケットからノードへの対応付情報を用いて実現され、
前記第２のハッシュ関数を変更するステップは、前記バケットからノードへの対応付情報のうち１つ以上のバケットからノードへの対応付を変更するステップを含む、請求項１に記載の方法。
【請求項４】  複数個のノードの各ノードがバケットからノードへの対応付情報のローカルコピーを維持し、
前記バケットからノードへの対応付情報のうち１つ以上のバケットからノードへの対応付を変更するステップは、前記複数個のノードの各々で並列に実行される、請求項３に記載の方法。
【請求項５】  前記１つ以上のバケットからノードへの対応付を変更するステップは、エポック変更前のバケットからノードへの対応付およびいくつのノードがエポック変更後に資源を支配するよう利用可能であるかに基づいて確定結果を生成する１組の規則を適用することによって実行される、請求項４に記載の方法。
【請求項６】  １つ以上のバケットからノードへの対応付を変更するステップは、
いくつのハッシュバケットが前記第１のハッシュ関数に関連付けられるかおよびいくつのノードがエポック変更後に資源を支配するよう利用可能であるかに基づいてターゲットバケット数を決定するステップと、
もし特定のノードがエポック変更後に資源を支配するよう利用可能であれば、エポック変更後に、
もしターゲットバケット数よりも多いバケットがエポック変更前に特定のノードに対応付けられていたならば、バケットからノードへの情報を修正してエポック変更前に特定のノードに対応付けられていた１つ以上のバケットを異なったノードに対応付けるステップと、
もしターゲットバケット数より少ないバケットがエポック変更前に特定のノードに対応付けられていたならば、バケットからノードへの情報を修正してエポック変更前に異なったノードに対応付けられていた１つ以上のバケットを特定のノードに対応付けるステップとを実行するステップとを含む、請求項３に記載の方法。
【請求項７】  移動するステップは、
過剰ノードが前記１つ以上のバケットに対応付けられる資源を支配するために必要な資源情報を不足ノードに送信するステップと、
過剰ノードが資源情報を送信し始めた後、前記資源に関する要求を過剰ノードにおいて受信するステップと、
前記資源情報を送信した後に、過剰ノードが前記要求を前記不足ノードに転送するステップとを含む、請求項１に記載の方法。
【請求項８】  不足ノードは、前記不足ノードが前記１つ以上のバケットに対応付けられる前記資源のマスタであることを示すメッセージをノードの組にブロードキャストするステップと、
前記ノードの組のノードは、前記第２のハッシュ関数を変更して前記１つ以上のバケットを前記不足ノードに対応付けることによって前記メッセージに応答するステップとを含む、請求項７に記載の方法。
【請求項９】  エポック変更中に複数ノードのシステムから取除かれる予定のノード上に現在支配されている資源をリマスタするための方法であって、
ノードは前記資源を支配するために必要な資源情報を別のノードに送信するステップと、
ノードが資源情報を送信し始めた後、前記資源に関する要求をノードにおいて受信するステップと、
前記資源情報を送信した後に、ノードは前記要求を前記他のノードに転送するステップとを含む、方法。
【請求項１０】  資源は、第１のハッシュ関数に関連付けられるハッシュバケットに対応付けられ、
ハッシュバケットは、第２のハッシュ関数に基づいて前記ノードに対応付けられ、
前記資源情報を受信した後に、前記他のノードは前記他のノードが前記資源のマスタであるというメッセージを送信し、
前記メッセージに応答して、前記第２のハッシュ関数は前記ハッシュバケットを前記他のノードに対応付けるよう変更される、請求項９に記載の方法。
【請求項１１】  他のノードは前記メッセージを複数個のノードにブロードキャストし、
第２のハッシュ関数は、前記複数個のノードの各ノードが前記各ノードで維持されるバケットからノードへの対応付情報を変更するようになることによって変更される、請求項１０に記載の方法。
【請求項１２】  複数ノードのシステムでのノードに対する資源を支配するための命令のシーケンスを担持するコンピュータ読出可能媒体であって、命令のシーケンスは、
１組の資源の中の各資源について、
第１のハッシュ関数を用いて特定のハッシュバケットに資源を対応付けるステップと、
第２のハッシュ関数を用いて特定のノードに特定のハッシュバケットを対応付けるステップと、
前記資源のマスタとなるよう前記特定のノードを選択するステップとによって資源を支配するノードを選択するステップと、
前記第１のハッシュ関数を変更することなしに前記第２のハッシュ関数を変更することによってエポック変更に応答するステップとを実行する命令を含み、
前記第２のハッシュ関数を変更するステップは、
前記エポック変更後に初期再構成を実行するステップを含み、前記初期再構成は、エポック変更後に存在するノードにエポック変更中に取除かれたノードに対応付けられた１組のバケットを再対応付するステップを含み、さらに、
前記初期再構成を実行した後、
複数ノードのシステムを一般的に利用可能にするステップと、
複数ノードのシステムが一般的に利用可能である一方で、不足ノードに割当てられたバケットの数がターゲットバケット数に等しくなるまで過剰ノードに現在対応付けられている１つ以上のバケットを不足ノードに移動するステップとを実行するステップを含み、
エポック変更は、複数ノードのシステムにおけるノードの数の変更であり、
不足ノードは、現在割当てられている範囲がターゲットバケット数より少ない数のバケットに及ぶ複数ノードのシステムにおけるノードであり、
過剰ノードは、現在割当てられている範囲がターゲットバケット数より大きい数のバケットに及ぶ複数ノードのシステムにおけるノードであり、
ターゲットバケット数は、バケットを複数ノードのシステムにおけるノード間で均等に分散するために複数ノードのシステムにおける各ノードが持たなければならないバケットの数である、コンピュータ読出可能媒体。
【請求項１３】  エポック変更前に、第１の数のノードを用いて前記資源の組からの資源を支配し、
エポック変更後に、第２の数のノードを用いて前記資源の組からの資源を支配し、
コンピュータ読出可能媒体は、前記第１のハッシュ関数を用いてある数のバケットに資源をハッシュするステップを実行する命令を含み、前記ある数のバケットは前記第１の数および前記第２の数のどちらよりも大きい、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１４】  前記第２のハッシュ関数はバケットからノードへの対応付情報を用いて実現され、
前記第２のハッシュ関数を変更するステップは、前記バケットからノードへの対応付情報のうち１つ以上のバケットからノードへの対応付を変更するステップを含む、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１５】  複数個のノードの各ノードがバケットからノードへの対応付情報のローカルコピーを維持し、
前記バケットからノードへの対応付情報のうち１つ以上のバケットからノードへの対応付を変更するステップは、前記複数個のノードの各々で並列に実行される、請求項１４に記載のコンピュータ読出可能媒体。
【請求項１６】  前記１つ以上のバケットからノードへの対応付を変更するステップは、エポック変更前のバケットからノードへの対応付およびいくつのノードがエポック変更後に資源を支配するよう利用可能であるかに基づいて確定結果を生成する１組の規則を適用することによって実行される、請求項１５に記載のコンピュータ読出可能媒体。
【請求項１７】  １つ以上のバケットからノードへの対応付を変更するステップは、
いくつのハッシュバケットが前記第１のハッシュ関数に関連付けられるかおよびいくつのノードがエポック変更後に資源を支配するよう利用可能であるかに基づいてターゲットバケット数を決定するステップと、
もし特定のノードがエポック変更後に資源を支配するよう利用可能であれば、エポック変更後に、
もしターゲットバケット数よりも多いバケットがエポック変更前に特定のノードに対応付けられていたならば、バケットからノードへの情報を修正してエポック変更前に特定のノードに対応付けられていた１つ以上のバケットを異なったノードに対応付けるステップと、
もしターゲットバケット数より少ないバケットがエポック変更前に特定のノードに対応付けられていたならば、バケットからノードへの情報を修正してエポック変更前に異なったノードに対応付けられていた１つ以上のバケットを特定のノードに対応付けるステップとを実行するステップとを含む、請求項１４に記載のコンピュータ読出可能媒体。
【請求項１８】  移動するステップは、
過剰ノードが前記１つ以上のバケットに対応付けられる資源を支配するために必要な資源情報を不足ノードに送信するステップと、
過剰ノードが資源情報を送信し始めた後、前記資源に関する要求を過剰ノードにおいて受信するステップと、
前記資源情報を送信した後に、過剰ノードが前記要求を前記不足ノードに転送するステップとを含む、請求項１２に記載のコンピュータ読出可能媒体。
【請求項１９】  不足ノードは、前記不足ノードが前記１つ以上のバケットに対応付けられる前記資源のマスタであることを示すメッセージをノードの組にブロードキャストするステップと、
前記ノードの組のノードは、前記第２のハッシュ関数を変更して前記１つ以上のバケットを前記不足ノードに対応付けることによって前記メッセージに応答するステップとを実行する命令をさらに含む、請求項１８に記載のコンピュータ読出可能媒体。
【請求項２０】  エポック変更中に複数ノードのシステムから取除かれる予定のノード上に現在支配されている資源をリマスタするシーケンスを担持するコンピュータ読出可能媒体であって、命令のシーケンスは、
ノードが前記資源を支配するために必要な資源情報を別のノードに送信するステップと、
ノードが資源情報を送信し始めた後、前記資源に関する要求をノードにおいて受信するステップと、
前記資源情報を送信した後に、ノードは前記要求を前記他のノードに転送するステップとを実行する命令を含む、コンピュータ読出可能媒体。
【請求項２１】  資源は、第１のハッシュ関数に関連付けられるハッシュバケットに対応付けられ、
ハッシュバケットは、第２のハッシュ関数に基づいて前記ノードに対応付けられ、
前記資源情報を受信した後に、前記他のノードは前記他のノードが前記資源のマスタであるというメッセージを送信し、
前記メッセージに応答して、前記第２のハッシュ関数は前記ハッシュバケットを前記他のノードに対応付けるよう変更される、請求項２０に記載のコンピュータ読出可能媒体。
【請求項２２】  他のノードは前記メッセージを複数個のノードにブロードキャストし、
第２のハッシュ関数は、前記複数個のノードの各ノードが前記各ノードで維持されるバケットからノードへの対応付情報を変更するようになることによって変更される、請求項２１に記載のコンピュータ読出可能媒体。