(57)【要約】【課題】オーセンティケータにセキュアファイル書き込みが伴う場合に、惨事発生後、セキュアファイル書き込みを行うためのシステムおよび方法をサーバーレス分散ファイルシステム内の認証されていないチャネル上で実装する。【解決手段】サーバーレス分散ファイルシステムは、ｆをシステムが許容できるフォールトの数を表す値として、少なくとも３ｆ＋１個の参加コンピュータメンバーを含む。グループは、ファイル作成およびファイルアップロード用に少なくとも１つのオーセンティケータを必要とする。メンバー間に格納されているファイルへの変更は、ファイル変更がオーセンティケータによりセキュリティ保護され、グループがオーセンティケータを検証することができる場合に、非認証チャネル上で行うことができる。【選択図】図９
2011008818.tif 000002
【特許請求の範囲】
【請求項１】
複数のメンバーが含まれている分散ディレクトリグループ内のファイルを安全に更新する方法であって、
ｎ個のオーセンティケータのうち１つを前記複数のメンバーの各メンバーが受信し、
安全でないチャネル上で、ファイル内容のハッシュとｎ個のオーセンティケータを使用して作成されたメッセージ認証コードのベクトルによりセキュリティ保護された１つまたは複数の更新ファイルを含む送信を受信し、
前記分散ディレクトリグループ内の予め定めた数のメンバーにメッセージ認証コードの前記ベクトル内の予め定めた数の前記メッセージ認証コードを検証することを要求することにより前記更新ファイルを認証する
ことを特徴とする方法。
【請求項２】
前記ｎ個のオーセンティケータは、ＵＭＡＣメッセージ認証コードであることを特徴とする請求項１に記載の方法。
【請求項３】
ユーザーは、前記分散ディレクトリグループの各メンバーとの対称鍵関係を確立することを特徴とする請求項１に記載の方法。
【請求項４】
前記予め定めた数のメッセージ認証コードを検証する必要があるメンバーの数はｆ＋１であり、前記予め定めた数のメッセージ認証コードは２ｆ＋１であり、ｆは前記分散ディレクトリグループにより許容可能なフォールトの個数であることを特徴とする請求項１に記載の方法。
【請求項５】
認証されたチャネルの外部にあるフォールトトレラントディレクトリグループへのファイル書き込みを許可する方法であって、
クライアントマシンからログを受け取り、前記ログは前記ファイル書き込みを含み、前記ログはメッセージ認証コードにより認証され、
前記メッセージ認証コードに関連付けられている秘密鍵を再構成し、前記再構成では前記フォールトトレラントディレクトリグループのいくつかのメンバーが前記秘密鍵の割り当て分を提供するよう要求し、前記数は、少なくとも１に前記フォールトトレラントディレクトリグループの許容可能なフォールトの個数を加えた数であることを特徴とする方法。
【請求項６】
前記フォールトトレラントディレクトリグループは、前記クライアントマシンを使用不能に陥らせる大惨事のため前記認証されたチャネルの外部で前記ログを受け取ることを特徴とする請求項５に記載の方法。
【請求項７】
前記フォールトトレラントディレクトリグループ内のメンバーの数は、前記フォールトトレラントディレクトリグループで許容できるフォールトの個数を少なくとも３倍して１を加えた値であることを特徴とする請求項５に記載の方法。
【請求項８】
コンピュータ実行可能命令を格納するコンピュータ可読媒体であって、前記命令は、
ｎ個のオーセンティケータのうち１つを複数のメンバーが含まれる分散ディレクトリグループの各メンバーが受信すること、
安全でないチャネル上で、ファイル内容のハッシュとｎ個のオーセンティケータを使用して作成されたメッセージ認証コードのベクトルによりセキュリティ保護された１つまたは複数の更新ファイルを含む送信を受信すること、
前記分散ディレクトリグループ内の予め定めた数のメンバーにメッセージ認証コードの前記ベクトル内の予め定めた数の前記メッセージ認証コードを検証することを要求することにより前記更新ファイルを認証することを含む処理を実行することを特徴とするコンピュータ可読媒体。
【請求項９】
前記ｎ個のオーセンティケータは、ＵＭＡＣメッセージ認証コードであることを特徴とする請求項８に記載のコンピュータ可読媒体。
【請求項１０】
ユーザーは、前記分散ディレクトリグループの各メンバーとの対称鍵関係を確立することを特徴とする請求項８に記載のコンピュータ可読媒体。
【請求項１１】
前記予め定めた数のメッセージ認証コードを検証する必要があるメンバーの数はｆ＋１であり、前記予め定めた数のメッセージ認証コードは２ｆ＋１であり、ｆは前記分散ディレクトリグループにより許容可能なフォールトの個数であることを特徴とする請求項８に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータネットワークおよびファイルシステムに関するものであり、特に、サーバーレス分散ファイルシステム（ｓｅｒｖｅｒｌｅｓｓ  ｄｉｓｔｒｉｂｕｔｅｄ  ｆｉｌｅ  ｓｙｓｔｅｍ）におけるセキュアリカバリ（ｓｅｃｕｒｅ  ｒｅｃｏｖｅｒｙ）に関するものである。
【背景技術】
【０００２】
ファイルシステムは、コンピュータシステム上に格納されているファイルおよびその他のデータオブジェクトを管理する。ファイルシステムは、もともと、ローカルにある常駐の記憶媒体に格納されているファイルにアクセスできるようにコンピュータのオペレーティングシステムに組み込まれていた。コンピュータがネットワーク化されるようになると、一部のファイルストレージ機能が個々のユーザーマシンから取り外され、ユーザーマシンに代わって大量のファイルを格納する特別なストレージサーバーに移された。ファイルが必要になった場合、ユーザーマシンは、ただ単にファイルをサーバーに要求した。このサーバーベースのアーキテクチャでは、ネットワーク上のリモートのストレージサーバーに格納されているファイルの管理およびアクセスを行えるようにファイルシステムの拡張が行われた。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
今日、ファイルストレージは、ファイルを中央のストレージサーバーに格納するのではなく、ネットワーク化されているさまざまなコンピュータ上に格納するモデルに移行しつつある。サーバーレスアーキテクチャでは、ファイルシステムに新たな問題が生じる。とりわけ問題の１つは、ファイルを管理すること、すなわち、ファイルを性をもって格納でき、またその時々に入れ替わり立ち替わりいくつかのコンピュータがアクセス不能になったとしてもファイルにアクセス可能で、しかもそれと同時に不正ユーザーによるファイルへのアクセスを防止するような方法で、多数の異なるコンピュータ上に分散されているファイルを管理することに関係する。特に重要なのは、コンピュータのハッカーや不正ユーザーがネットワーク接続されているコンピュータ内に格納されているデータを改ざんしたり、破壊したりするおそれのある惨事が万が一発生した場合のために、コンピュータに格納されているデータを保護する必要があるという点である。
【課題を解決するための手段】
【０００４】
本発明は、これらの問題点に対処し、サーバーレス分散ファイルシステムに有効な解決策を提示する。
【０００５】
サーバーレス分散ファイルシステムに生じた大惨事から復旧するための方法およびシステムについて説明する。より具体的には、オーセンティケータ（ａｕｔｈｅｎｔｉｃａｔｏｒ）にセキュアファイル書き込み（ｓｅｃｕｒｅ  ｆｉｌｅ  ｗｒｉｔｅｓ）が伴う場合に、大惨事発生後、セキュアファイル書き込みを行うためのシステムおよび方法をサーバーレス分散ファイルシステム内の認証されていないチャネル上で可能にすることができる。オーセンティケータは、期間制限のある委任証明書（ｐｏｗｅｒ−ｏｆ−ａｔｔｏｒｎｅｙ  ｃｅｒｔｉｆｉｃａｔｅ）、メッセージ認証コード（ＭＡＣ）のベクトル（ｖｅｃｔｏｒ  ｏｆ  ｍｅｓｓａｇｅ  ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｃｏｄｅｓ）、またはサーバーレス分散ファイルシステムのメンバー間で共有される秘密鍵でセキュリティ保護されている単一メッセージオーセンティケータコード（ＭＡＣ）である。サーバーレス分散ファイルシステムは、ｆをシステムが許容できるフォールトの数を表す値として、少なくとも３ｆ＋１個の参加コンピュータメンバーを含む。グループは、ファイル作成およびファイルアップロード用に少なくとも１つのオーセンティケータを必要とする。
【０００６】
一実施形態では、オーセンティケータは、委任証明書であり、この委任証明書には、予め定めた時間の間にファイルアップロードを許可する時間構成要素を含む予め定めた基準を有する。
【０００７】
他の実施形態では、オーセンティケータは、秘密鍵によりセキュリティ保護されたメッセージ認証コードである。グループはクライアントマシンからログを受け取る。このログにはファイル書き込みを含み、メッセージ認証コードにより認証される。秘密鍵は、メッセージ認証コードに関連付けられており、そのために、秘密鍵を再構成するためには、グループのｆ＋１個のメンバーが秘密鍵の割り当て分を提供する必要がある。
【０００８】
一実施形態では、オーセンティケータは、複数の秘密鍵によりセキュリティ保護されたＭＡＣのベクトルであり、グループの各メンバーは複数の秘密鍵のうちの１つを所有する。この実施形態では、グループは、アップロードを認証するために少なくともｆ＋１個のメンバーを必要とするように構成されている。特に、この実施形態では、各メンバーはｎ個のオーセンティケータのうちの１つを受け取り、後から、安全でないチャネルで、ファイル内容のハッシュによりセキュリティ保護されている１つまたは複数の更新ファイルを含む送信（データ）およびｎ個のオーセンティケータを使用して作成されたＭＡＣのベクトルとを受け取る。ｎ個のオーセンティケータは、ＵＭＡＣメッセージ認証コードとすることができる。
【０００９】
他の実施形態では、オーセンティケータは、サーバーレス分散ファイルシステムにより共有される複数の証明書のうちの１つであり、複数の証明書のそれぞれの証明書にシリアル番号が振られ、分散ファイルシステムは順序の狂っている証明書に対する認証を拒絶することで証明書の選択的選択を防止することができる。
【００１０】
一実施形態による方法では、ファイル書き込みを、認証されているチャネルの外部にあるフォールトトレラントディレクトリグループに送信し、少なくとも１つのオーセンティケータで１つまたは複数のファイル書き込みを識別する。少なくとも１つのオーセンティケータでは、ディレクトリグループが１つまたは複数のファイル書き込みを許可するために少なくとも１つの秘密鍵を再構成する必要がある。秘密鍵を再構成するために必要なフォールトトレラントディレクトリグループ内のメンバーの数は、フォールトトレラントディレクトリグループで許容できるフォールトの個数を少なくとも３倍して１を加えた値である。
【００１１】
他の実施形態は、認証されたチャネルの外部にあるフォールトトレラントディレクトリグループへのファイル書き込みの方法を対象とする。この方法では、クライアントマシンにログを作成し、このログはファイル書き込みを含み、メッセージ認証コードと関連付けられている秘密鍵によりセキュリティが保護されているメッセージ認証コードによりこのログを認証する。秘密鍵を再構成するには、フォールトトレラントディレクトリグループの一定数のメンバーが秘密鍵の割り当て分を提供する必要があり、メンバーの数は、少なくとも１にフォールトトレラントディレクトリグループの許容可能なフォールトの個数を加えた数である。この方法はさらに、認証されたチャネルの外部でログを送信することを含む。
【００１２】
一実施形態は、認証されたチャネルの外部にあるフォールトトレラントディレクトリグループへのファイル書き込みを可能にするコンピュータ実行可能命令を格納するコンピュータ可読媒体を対象とし、コンピュータ実行可能命令により、ファイル書き込みを含むログを作成する作業などの処理を実行する。ログは、メッセージ認証コードに関連付けられている秘密鍵によりセキュリティ保護されているメッセージ認証コードにより認証される。秘密鍵を再構成するには、フォールトトレラントディレクトリグループの３ｆ＋１の数のメンバーが秘密鍵の割り当て分を提供する必要があり、数ｆは、フォールトトレラントディレクトリグループの許容可能なフォールトの数である。命令により、さらに、クライアントマシンは認証されたチャネルの外部でログを送信することができる。本発明の他の特徴および利点は、添付図を参照して進められている例示的な実施形態の以下の詳細な説明から明白であろう。
【００１３】
付属の請求項で本発明の特徴を詳細に述べているが、本発明は、その目的および利点とともに、添付図面に関する以下の詳細な説明から最もよく理解できよう。
【００１４】
類似のコンポーネントおよび／または図を参照するため文書全体を通して同じ番号を使用する。
【図面の簡単な説明】
【００１５】
【図１】サーバーレス分散ファイルシステムをサポートするネットワーク環境例の図である。
【図２】分散ファイルシステムに参加している図１のデバイスのうちの１つを表すコンピューティングデバイス例の論理コンポーネントの図である。
【図３】図１の分散ファイルシステムを実装するために使用される、より一般的なコンピュータ環境の図である。
【図４】複数のサブツリーを持つ名前空間ルートを含む階層型名前空間の例を示す図である。
【図５】サーバーレス分散ファイルシステム内のファイルおよび対応するディレクトリエントリの格納例を示す図である。
【図６】サーバーレス分散ファイルシステム内でファイルを格納するプロセスの例を説明する流れ図である。
【図７】サーバーレス分散ファイルシステム内のファイルおよび証明書の格納例を示す図である。
【図８】委任証明書を使用するプロセスの例を説明する流れ図である。
【図９】サーバーレス分散ファイルシステム内で秘密鍵を使用するファイルの格納例を示す図である。
【図１０】秘密鍵共有の実施形態による更新ファイルをアップロードするプロセスの例を説明する流れ図である。
【図１１】秘密鍵共有の実施形態により更新ファイルを行えるようにするかどうかを決定するプロセスの例を説明する流れ図である。
【図１２】オーセンティケータのベクトルの実施形態により更新ファイルを行えるようにするかどうかを決定するプロセスの例を説明する流れ図である。
【図１３】ファイルの検証を行うプロセスの例を説明する流れ図である。
【図１４】再生攻撃を防止するプロセスの例を説明する流れ図である。
【発明を実施するための最良の形態】
【００１６】
サーバーレス分散ファイルシステム  図１は、サーバーレス分散ファイルシステムをサポートするネットワーク環境１００の例を示す図である。４つのクライアントコンピューティングデバイス１０２、１０４、１０６、および１０８は、データ通信ネットワーク１１０を介して共に結合されている。４つのコンピューティングデバイスが示されているが、ネットワーク環境１００に組み込むことができる数はそれと異なっていてもよい（４つよりも多くても少なくてもよい）。
【００１７】
ネットワーク１１０は、さまざまなデータ通信ネットワークを表す。ネットワーク１１０は、公開部分（たとえば、インターネット）、さらにプライベート部分（たとえば、社内ローカルエリアネットワーク（ＬＡＮ））、さらに公開部分とプライベート部分の組合せを含むことができる。ネットワーク１１０は、有線媒体および無線媒体の両方を含むさまざまな従来の通信媒体のうち１つまたは複数を使用して実装することができる。さまざまな通信プロトコルを使用して、公開プロトコルおよび専用プロトコルの両方を含めてネットワーク１１０を介してデータを通信することができる。このようなプロトコルの例として、ＴＣＰ／ＩＰ、ＩＰＸ／ＳＰＸ、ＮｅｔＢＥＵＩなどがある。
【００１８】
コンピューティングデバイス１０２〜１０８は、さまざまなコンピューティングデバイスを表し、それぞれのデバイスは同じであっても異なっていてもよい。たとえば、デバイス１０２〜１０８として、デスクトップコンピュータ、ラップトップコンピュータ、ハンドヘルドまたはポケットコンピュータ、パーソナルデジタルアシスタント（ＰＤＡ）、携帯電話、インターネット家電、家庭用電化製品、ゲーム機などがある。
【００１９】
デバイス１０２〜１０８のうち２つまたはそれ以上が、サーバーレス分散ファイルシステムを実装する処理をする。サーバーレス分散ファイルシステムに参加している実際のデバイスは、時間のたつうちに変わり、新しいデバイスがシステムに加わったり、システムから他のデバイスが除去されたりする。分散ファイルシステムを実装する（参加する）各デバイス１０２〜１０６は、ローカルストレージまたは分散ストレージとして使用するために割り当てられた大容量ストレージデバイス（たとえば、ハードディスクドライブ）の一部を備える。ローカルストレージは、ユーザーが、分散ファイルシステム構造にではなく、自分のローカルマシンに格納したいデータに使用される。分散ストレージ部分は、デバイス（または他のデバイス）のユーザーが分散ファイルシステム構造内に格納したいデータに使用される。
【００２０】
図１の図の例では、ネットワーク１１０に接続されているいくつかのデバイスは、分散部分とローカル部分の両方を含む１つまたは複数の大容量ストレージデバイスを備える。分散ストレージまたはローカルストレージに割り当てられる量はデバイスによって異なる。たとえば、デバイス１０２は、ローカル部分１２２に比べて分散システム部分１２０の方が割り当てられるパーセンテージが高く、デバイス１０４では、分散システム部分１２４はローカル部分１２６とほぼ同じであり、デバイス１０６は、ローカル部分１３０に比べて分散システム部分１２８の方が割り当てられるパーセンテージは低い。複数の部分へのストレージ分割は、ストレージデバイス毎に行われ（たとえば、一方のハードドライブを分散システムで使用するよう指定し、他方のハードドライブをローカル専用として指定する）、および／または単一ストレージデバイスで行うことも可能である（たとえば、一方のハードドライブの一部を分散システムで使用するように指定し、他方の部分をローカル使用に指定する）。分散ストレージまたはローカルストレージに割り当てられる量は時間によっても異なる。コンピューティングデバイス１０８などのネットワーク１１０に接続されている他のデバイスは、分散ファイルシステムをどれも実装することはできず、したがって、大容量ストレージデバイスを分散システム用に割り当てられない。したがって、デバイス１０８はローカル部分１３２しか持たない。
【００２１】
分散ファイルシステム１５０は、異なるコンピューティングデバイス１０２〜１０６にファイルの１つまたは複数のコピーを格納する処理をする。新しいファイルがコンピュータのユーザーによって作成された場合、ユーザーはファイルを自分のコンピューティングデバイスのローカル部分に格納するか、または別法として、分散ファイルシステム内に格納するかを選択することができる。ファイルが分散ファイルシステム１５０に格納される場合、ファイルはデバイス１０２〜１０６のうち１つまたは複数のデバイスの大容量ストレージデバイスの分散システム部分に格納されることになる。ファイルを作成したユーザーは、通常、デバイス１０２〜１０６のどれにファイルを格納するかを制御することはできず、またデバイス１０２〜１０６のどれにファイルが格納されているかも知ることはできない。さらに、ファイルの複製は、通常、保存されるため、ファイルが保存されているコンピューティングデバイス１０２〜１０６のうちの１つが使用不可能になったとしても（たとえば、停電、故障などが生じて）、ユーザーは後からファイルを取り出すことができる。
【００２２】
分散ファイルシステム１５０は、デバイス１０２〜１０６のそれぞれに搭載されている１つまたは複数のコンポーネントにより実装され、そのため、中央サーバーがファイルシステムの調整を行う必要がない。これらのコンポーネントは、特定のファイルがどこに格納されるか、異なるデバイスへの格納のためファイルのコピーをいくつ作成するかなどを判別する処理をする。厳密にどのファイルがどのデバイスに格納されるかは、分散ファイルシステム内のデバイスの個数、各デバイスからファイルシステムに割り当てられた記憶領域、保存するファイルのコピー数、暗号でセキュリティ対策した乱数、デバイス上にすでに格納されているファイルの個数など、さまざまな要因に左右される。したがって、分散ファイルシステムを使用すると、ユーザーは、ファイルが他のどのコンピューティングデバイスに格納されているかを正確に知ることなくファイルを（さらにはフォルダまたはディレクトリも）作成し、アクセスすることができる。
【００２３】
分散ファイルシステム１５０は、システム１５０内のコンピュータの増大に合わせて拡張可能なように設計されている。システム１５０のデバイス上のコンポーネントによって使用されるプロトコルおよびデータ構造は、設計上、システム内のコンピュータの台数に比例しないため、コンピュータ台数の増大に合わせて容易に拡張することができる。
【００２４】
ファイルシステムによって格納されるファイルは、さまざまなデバイス１０２〜１０６の間に分散され、暗号化の形態で格納される。新規ファイルが作成される場合、その新規ファイルが作成されるデバイスは、ファイルを格納のため他のデバイスに伝達するのに先立ってファイルを暗号化する。新しいファイルのディレクトリエントリ（ファイル名を含む）は、さらに、格納のため他のデバイスにも伝達されるが、暗号化されたファイルが格納されているデバイスと同じデバイスでなくてよいし、（通常は、同じでない）。さらに、新しいフォルダまたはディレクトリが作成される場合、ディレクトリエントリ（フォルダ名またはディレクトリ名を含む）も格納のため他のデバイスに伝達される。本明細書で使用しているように、ディレクトリエントリは、ファイル名とディレクトリ（またはフォルダ）名の両方を含む、ファイルシステムディレクトリに追加することができるエントリを指す。
【００２５】
分散ファイルシステム１５０は、不正ユーザーがデバイス１０２〜１０６のうちの１つに格納されているデータを読み込めないように設計されている。したがって、デバイス１０２によって作成され、デバイス１０４に格納されているファイルは、デバイス１０４のユーザーからは読み出すことができない（そのユーザーが読み取る権限を与えられていない限り）。このようなセキュリティを実装するために、ファイルの内容だけでなくディレクトリエントリ内のすべてのファイル名およびディレクトリ名も暗号化し、認証ユーザーのみに暗号解読鍵を提供する。したがって、デバイス１０４は、デバイス１０２によって作成されたファイルを格納することができるが、デバイス１０４のユーザーがファイルの認証ユーザーでない場合に、デバイス１０４のユーザーは、ファイルの内容またはそのディレクトリエントリ内のファイル名のいずれかを暗号解読することはできない（また、読み出すこともできない）。
【００２６】
分散ファイルシステム１５０は、１つまたは複数の名前空間ルートを持つとともに、各名前空間ルートの配下に複数のサブツリーを置く、階層型格納構造を採用している。異なるサブツリーの管理はコンピュータの異なるグループに委託されるので、名前空間ルートまたは特定のサブツリーを管理するコンピュータに負担がかかり過ぎることはない。
【００２７】
分散ファイルシステム１５０はさらに、ファイルおよびそれらのファイルに対応するディレクトリエントリの格納を異なる方法で管理する。システム１５０に格納されるファイルは複製され、システム内の複数の異なるコンピュータに保存される。さらに、そのファイルに対するディレクトリエントリが作成され、これもまた、システム内の複数の異なるコンピュータ上に保存される。保存されるディレクトリエントリのコピーは保存されるファイルコピーの個数よりも多い。一実施形態では、ディレクトリエントリは、後述のＢｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループの一部であるコンピュータ上に格納される。
【００２８】
分散ファイルシステム１５０は、さらに、ディレクトリおよびファイルの読み書きをする人の管理を行うディレクトリおよびファイルロックメカニズムも採用する。Ｂｙｚａｎｔｉｎｅグループ内のコンピュータで使用する場合、採用したこのロックメカニズムは、後述のように、ディレクトリグループによるアクションが行われなくてもローカルで実行できるオペレーションの数を増やすことによりパフォーマンスを向上させようとする。
【００２９】
分散ファイルシステム１５０内のすべてのコンピュータ１０２〜１０６には、３つの機能がある、つまり、ローカルユーザーに対するクライアントになれる、システム内に格納されているファイルの暗号化されたコピーに対するリポジトリになれる、および１つまたは複数のディレクトリを保持するコンピュータのグループのメンバーになれるという３つの機能がある。
【００３０】
一般に、コンピュータ１０２〜１０６のユーザーが所与のディレクトリ内のファイルを開く場合、コンピュータはＢｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔプロトコルを使用してそのディレクトリ（「Ｂｙｚａｎｔｉｎｅ  ｇｒｏｕｐ」または「ｄｉｒｅｃｔｏｒｙ  ｇｒｏｕｐ」という名前）をまとめて管理する一組のコンピュータ群に要求を送信する。Ｂｙｚａｎｔｉｎｅグループがコンピュータに対してファイルロックを許可すると、コンピュータはファイルに対してローカル更新を実行して（書き込みロックである場合）、これらの更新をＢｙｚａｎｔｉｎｅグループにプッシュして戻すことができる。コンピュータが最近このファイルにアクセスしている場合、おそらくローカルキャッシュ内にファイルコンテンツの暗号化されたコピーが置かれているであろうから、キャッシュされているコピーを取り出して暗号解読するだけで、そのファイルの読み書きを開始することができる。最近、ファイルの現行バージョンにアクセスしていなかった場合、コンピュータはそのファイルを格納しているコンピュータの１つからファイルの暗号化されているコピーを取り出す。コンピュータが保持しでいる現在のコピーに関する情報は、ロック許可とともにＢｙｚａｎｔｉｎｅグループにより与えられ、ファイル格納コンピュータのうちの１つまたは複数がダウンしている場合には、コンピュータは別のファイル格納コンピュータからファイルを取り出す。Ｂｙｚａｎｔｉｎｅグループはさらにファイル内容を暗号でハッシュし、コンピュータはその内容を使用して、フェッチするファイルの妥当性を確認する。
【００３１】
ファイル暗号化
ファイルの暗号化には、「収束暗号化（ｃｏｎｖｅｒｇｅｎｔ  ｅｎｃｒｙｐｔｉｏｎ）」と呼ばれる技術を使用する。収束暗号化には、以下の２つの特性がある。まず第１に、２つまたはそれ以上の暗号化可能オブジェクトが同一である場合、異なる暗号化鍵を使用してオブジェクトを暗号化し、個々の暗号オブジェクトを提供するとしても、暗号化鍵にアクセスして暗号化可能オブジェクトが同一であるということを暗号オブジェクトを調べることで判別する必要はない。第２に、２つまたはそれ以上の暗号化可能オブジェクトが同一であるが、異なる暗号化鍵で暗号化されている場合、暗号オブジェクトすべてを格納するために必要な領域全体は、単一の暗号化可能なオブジェクトを格納するのに必要な領域に、それぞれ異なる暗号化鍵の一定量の記憶を加えた物に比例する。
【００３２】
一般に、収束暗号化によれば、ファイルＦ（または他の種類の暗号化可能オブジェクト）は最初に、一方向ハッシュ関数ｈ（たとえば、ＳＨＡ、ＭＤ５など）を使用してハッシュを実行し、ハッシュ値ｈ（Ｆ）を出力する。次に、ハッシュ値を鍵とする対称暗号（たとえば、ＲＣ４、ＲＣ２など）、つまり、Ｅh(F)（Ｆ）を使用してファイルＦを暗号化する。次に、読み取りアクセス制御エントリを、暗号化されたファイルへの読み取りアクセス権が与えられている認証ユーザー毎に作成する。書き込みアクセス制御は、ファイルに対するディレクトリエントリを格納するディレクトリサーバーが取り扱う。読み取りアクセス制御エントリは、ファイルのハッシュ値ｈ（Ｆ）を任意個数の鍵Ｋ1、Ｋ2、．．．、Ｋmで暗号化し、ＥK1（ｈ（Ｆ））、ＥK2（ｈ（Ｆ））、．．．、ＥKm（ｈ（Ｆ））を得ることにより、形成される。一実施形態では、それぞれの鍵Ｋは、非対称暗号（たとえば、ＲＳＡ）の場合の公開／私的鍵ペアのユーザーの持つ公開鍵である。
【００３３】
収束暗号化では、ファイルの暗号化された１つのバージョンが、サーバーレス分散ファイルシステム１５０間で格納され、複製される。ファイルの暗号化バージョンとともに、アクセス権のある認証ユーザーの数に応じて１つまたは複数のアクセス制御エントリが格納される。したがって、分散ファイルシステム１５０内のファイルは以下の構造を持つ。
[Eh(F)(F), <EK1(h(F))>, <EK2(h(F))>, ..., <EKm(h(F))>]
【００３４】
収束暗号化の１つの利点は、暗号化されたファイルはファイルシステムによって評価され、暗号解読に頼らずとも（したがって、暗号化鍵を知らなくても）、他のファイルと同一であるかどうかを判別することができるという点である。不要な重複ファイルを削除するには、認証ユーザーアクセス制御エントリを残りのファイルに追加する。他の利点として、暗号化されたファイルは場合によっては数ギガバイトになることに比べ、アクセス制御エントリは数バイト程度でサイズが非常に小さいという点である。そのため、それぞれのファイルに格納されているオーバーヘッド情報の量は少ない。したがって、ファイルを格納するために使用する全領域は単一の暗号化されたファイルを格納するために必要な領域にファイルの各追加読み込み認証ユーザーの記憶域の一定量を加えた物に比例するという特性を持つ。
【００３５】
収束暗号化の詳細については、Ｍｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎに譲渡された、２０００年５月５日にＤｏｕｃｅｕｒ  ｅｔ  ａｌ．の名前で出願された「Encryption Systems and Methods for Identifying and Coalescing Identical Objects Encrypted with Different Keys」という表題の米国特許出願を参照されたい。この出願は、参照により本発明に組み込まれている。
【００３６】
ディレクトリエントリの暗号化
「排他的（ｅｘｃｌｕｓｉｖｅ）暗号化」と呼ばれるプロセスを使用してディレクトリエントリ内のファイルおよびディレクトリ名を暗号化する。排他的暗号化を使用することにより、ディレクトリエントリ内のファイルおよびディレクトリ名を暗号化形式で格納し、不正ユーザーがファイルまたはディレクトリの名前に基づいて情報を不正に取得するのを防止することができる。さらに、排他的暗号化には、以下の３つの特性がある。まず、ディレクトリ内の暗号化されたエントリのどの２つをとっても暗号解読した場合に同じ名前が得られることはない。第２に、ディレクトリ内の暗号化されたすべてのエントリは、暗号解読により構文的に正当な名前が得られる。第３に、ディレクトリを保持しているディレクトリグループは、エントリの平文の名前へのアクセス権を持たない。したがって、ファイルシステム１５０では、ディレクトリ内のどの２つのエントリも同じ名前を暗号化した物ではないこと、および、ディレクトリ内のすべてのエントリは、構文的に正当な名前を暗号化した物であることを保証することができ、それと同時に、ディレクトリを保持しているデバイスがエントリの平文の名前へのアクセス権を持たないことも保証される。
【００３７】
一般に、排他的暗号化によれば、平文名（ディレクトリエントリ内のファイル名またはディレクトリ名）は新しい名前にマッピングされる。マッピングされた名前は、任意選択により、ディケーシファイドされた（ｄｅｃａｓｉｆｉｅｄ）（大文字と小文字を区別しない）名前および対応する文字小文字区別の情報に変換され、重複名検出で大文字と小文字の区別をなくすことができる。その後、マッピングされた（および任意選択によりディケーシファイドされた）名前が符号化され、暗号化される。この暗号化された名前（および任意選択により、随伴する大文字小文字区別情報）は、ディレクトリエントリを管理する役割を持つディレクトリグループに転送される（たとえば、後述のように、パス名に基づいて）。
【００３８】
排他的暗号化の詳細については、本願出願人に譲渡された、２００１年１月１７日にＤｏｕｃｅｕｒ  ｅｔ  ａｌ．の名前で出願された「Exclusive Encryption for a Secure Directory Service」という表題の米国特許出願を参照されたい。この出願は、参照により本発明に組み込まれている。
【００３９】
ファイル形式
図１のサーバーレス分散ファイルシステム１５０のファイル形式は、一次データストリームとメタデータストリームの２つの部分からなる。一次データストリームは、複数のブロックに分けられたファイルを含む。各ブロックは、対称暗号（たとえば、ＲＣ４）および暗号化鍵としてブロックのハッシュを使用して暗号化される。メタデータストリームは、ヘッダ、一次データストリーム内の暗号化されたブロックにインデックスを付けるための構造、および何らかのユーザー情報を含む。
【００４０】
インデックス付けツリー構造により、ブロックのそれぞれのリーフノードが定義される。各リーフノードは、関連付けられているブロックの暗号解読に使用されるアクセス値および他のブロックとは無関係に暗号化されたブロックの検証を行うために使用される検証値からなる。一実施形態では、アクセス値を形成するために、ファイルブロックをハッシュし、対称暗号およびランダム生成鍵を使用して、その結果得られたハッシュ値を暗号化する。次に、鍵は、非対称暗号（たとえば、ＲＳＡ）および暗号化鍵としてユーザーの公開鍵を使用して暗号化される。検証値は、一方向ハッシュ関数（たとえば、ＳＨＡ）を使用して、関連付けられた暗号化されているブロックをハッシュすることにより形成される。
【００４１】
ファイルのサイズに応じて、インデックス付け構造は、リーフノードをツリーブロックにグループ化し、それぞれのツリーブロックのハッシュ値を計算することにより形成される中間ノードを含むことができる。これらの中間ノードを再び、ブロックにセグメント化し、各ブロックをハッシュして、次のノードを形成することができる。これは、ルートノードに到達するまで、好きなだけ繰り返すことができる。さらに、ルートノードをハッシュし、ハッシュ値をメタデータヘッダおよびユーザー情報とともに使用してファイル全体の検証値を出力する。一実施形態では、ファイル検証値全体にユーザーの署名を入れる。別法として、そのような署名なしでファイルを構成することもできる。
【００４２】
ファイル形式は、ランダム生成鍵またはユーザー鍵を知らなくても個別ファイルブロックの検証を行うことができる形式である。ファイルのブロックを検証するには、ファイルシステム側で任意選択により、ファイル全体の検証値（もし存在していれば）に関する署名を評価し、ファイル全体の検証値がルートブロック、メタデータヘッダ、およびユーザー情報のハッシュに一致しているかどうかを確認し、その後、ツリーをトラバースして検証すべきターゲットブロックに関連付けられた適切なリーフノードまでたどる。ファイルシステムは、ターゲットブロックをハッシュし、ハッシュがリーフノードに格納されているアクセス値に一致すれば、ブロックは信頼できる。
【００４３】
ファイル形式はさらに、他のブロックに干渉をすることなく、個々のブロックからの読み込みおよび個々のブロックへの書き込みをサポートする。ファイル形式は、さらに、非データの広範な領域を持つ疎ファイルでは役に立つ。
【００４４】
ファイル形式の詳細については、本願出願人に譲渡された、２００１年３月２１日にＢｏｌｏｓｋｙ  ｅｔ  ａｌ．の名前で出願された「On-Disk File Format for a Serverless Distributed File System」という表題の米国特許出願を参照されたい。この出願は、参照により本発明に組み込まれている。
【００４５】
コンピューティングデバイスのアーキテクチャ
図２は、分散ファイルシステム１５０に参加している図１のデバイス１０２〜１０６のうちの１つを表すコンピューティングデバイス２００の例の論理コンポーネントの図である。コンピューティングデバイス２００は、サーバーコンポーネント２０２、クライアントコンポーネント２０４、メモリ２０６、大容量ストレージデバイス２０８、および分散ファイルシステムインターフェイス２１０を備える。コンピューティングデバイス２００はさらに、追加コンポーネント（たとえば、プロセッサ）を備えるのが普通であるが、これらの追加コンポーネントは図面をわかりやすくするため図２には示されていない。さまざまなハードウェアおよびソフトウェアコンポーネントを使用するコンピュータアーキテクチャ全般については、図３を参照しながら以下で説明する。
【００４６】
メモリ２０６としては、ＲＡＭ、ＲＯＭ、フラッシュメモリなどのさまざまな従来の揮発性および／または不揮発性メモリを使用することができる。大容量ストレージデバイス２０８としては、磁気ディスク、光ディスク、フラッシュメモリなどのさまざまな従来の不揮発性ストレージデバイスを使用することができる。大容量ストレージデバイス２０８は、パーティション分割により、分散システム部分とローカル部分に分ける。図２には１つの大容量ストレージデバイス２０８しか示されていないが、コンピューティングデバイス２００は、複数のストレージデバイス２０８（種類は異なっていても、あるいはすべて同じ種類でもよい）を備えることができる。
【００４７】
コンピューティングデバイス２００は、サーバーレス分散ファイルシステム内で使用するようになっており、したがって、サーバーコンポーネント２０２とクライアントコンポーネント２０４の両方を含む。サーバーコンポーネント２０２は、デバイス２００がストレージデバイス２０８に格納されている（または格納される予定の）ファイルまたはディレクトリエントリを伴う要求に応答している場合に要求を処理するが、クライアントコンポーネント２０４は、分散ファイルシステムに格納されている（または格納される予定の）ファイルまたはディレクトリに関するデバイス２００による要求の発行を処理する。クライアントコンポーネント２０４およびサーバーコンポーネント２０２は、互いに独立に処理する。したがって、サーバーレス分散ファイルシステム１５０のせいで、クライアントコンポーネント２０４によって格納されるファイルがサーバーコンポーネント２０２により大容量ストレージデバイス２０８に格納される状況が生じる可能性がある。
【００４８】
クライアントコンポーネント２０４は、コンピューティングデバイス１５０に代わって、ファイルおよびディレクトリの作成、格納、取り出し、読み込み、書き込み、修正、および検証を行うため、インターフェイス２１０とともに、サーバーレス分散ファイルシステム１５０へのアクセスを管理する、格納および取り出し制御モジュール２２０を備える。制御モジュール２２０は、特定のファイルまたはディレクトリを管理する役割を持つディレクトリグループを識別するディレクトリグループ検索モジュール２２２、ファイルを暗号化するファイル暗号化モジュール２２６、ディレクトリエントリ内のファイル名およびディレクトリ名を暗号化するディレクトリ暗号化モジュール２２８を使用する。これらのモジュールの処理について、以下で詳述する。
【００４９】
サーバーコンポーネント２０２は、分散システム制御モジュール２５０、重複識別器２５２、およびサブツリー委任モジュール２５４を備える。分散システム制御モジュール２５０は、暗号化ファイル２４０へのアクセスを管理する。これは、大容量ストレージデバイス２０８と通信し、暗号化ファイル２４０の格納および取り出しを行う。分散システム制御モジュール２５０は、さらに、コンピューティングデバイス２００内に格納されている（あるいは、サーバーレス分散ファイルシステム内のどこかに格納されている）メモリ２０６および／または大容量ストレージデバイス２０８内のディレクトリエントリ（図に示されていない）の記録を保持する。サブツリー委任モジュール２５４は、後述のように、他のディレクトリグループにサブツリーを委任する処理をする。
【００５０】
重複識別器２５２は、分散ファイルシステム内の同一の暗号化ファイルを識別するのに使用される。重複識別器２５２がフォールトトレラントを目的とする意図的な複製ではない重複を見つけた場合、重複識別器２５２が制御モジュール２５０に通知し、重複ファイルを除去し、除去されたファイルへのアクセス制御エントリを残りのファイルに追加する。
【００５１】
図３は、分散ファイルシステムを実装するために使用される、より一般的なコンピュータ環境３００の図である。コンピュータ環境３００は、コンピューティング環境の一例にすぎず、コンピュータおよびネットワークアーキテクチャの使用または機能の範囲に関する限定を示唆しないことを意図している。またコンピュータ環境３００は、コンピュータ環境例３００に示されているコンポーネントの包含（または除外）またはコンポーネントの結合または組合せに関係する要件があると解釈してはならない。
【００５２】
コンピュータ環境３００は、コンピュータ３０２の形の汎用コンピューティングデバイスを備える。コンピュータ３０２のコンポーネントは、それだけに限らないが、１つまたは複数のプロセッサまたは処理ユニット３０４、システムメモリ３０６、およびシステムメモリ３０６にプロセッサ３０４をはじめとするさまざまなシステムコンポーネントを結合するシステムバス３０８を備える。
【００５３】
システムバス３０８は、メモリバスまたはメモリコントローラ、周辺機器バス、グラフィック専用高速ポート、およびさまざまなバスアーキテクチャを使用するプロセッサまたはローカルバスを含む、いくつかのタイプのバス構造のうちの１つまたは複数のバス構造を表している。たとえば、このようなアーキテクチャとしては、Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＳＡ）バス、Ｍｉｃｒｏ  Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ（ＭＣＡ）バス、Ｅｎｈａｎｃｅｄ  ＩＳＡ（ＥＩＳＡ）バス、Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ（ＶＥＳＡ）ローカルバス、およびＭｅｚｚａｎｉｎｅバスとも呼ばれるＰｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）バスがある。
【００５４】
コンピュータ３０２は通常、さまざまなコンピュータ可読媒体を含む。このようなメディアは、コンピュータ３０２からアクセス可能な使用可能媒体であればよく、揮発性および不揮発性媒体、取り外し可能および取り外し不可能媒体の両方を含む。
【００５５】
システムメモリ３０６は、ランダムアクセスメモリ（ＲＡＭ）３１０などの揮発性メモリおよび／または読み取り専用メモリ（ＲＯＭ）３１２などの不揮発性メモリの形式のコンピュータ可読媒体を備える。起動時などにコンピュータ３０２内の要素間の情報伝送を助ける基本ルーチンを含む基本入出力システム（ＢＩＯＳ）３１４は、ＲＯＭ  ３１２に格納される。通常、ＲＡＭ  ３１０には、処理ユニット３０４に直接アクセス可能な、および／または現在操作されているデータおよび／またはプログラムモジュールを格納する。
【００５６】
コンピュータ３０２はさらに、その他の取り外し可能／取り外し不可能な揮発性／不揮発性コンピュータ記憶媒体を備えることもできる。たとえば、図３は、取り外し不可能な不揮発性磁気媒体の読み書きを行うハードディスクドライブ３１６（図には示されていない）、取り外し可能な不揮発性磁気ディスク３２０（たとえば、「フロッピー（登録商標）ディスク」）の読み書きを行う磁気ディスクドライブ３１８、およびＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、またはその他の光媒体などの取り外し可能な不揮発性光ディスク３２４の読み書きを行う光ディスクドライブ３２２を示している。ハードディスクドライブ３１６、磁気ディスクドライブ３１８、および光ディスクドライブ３２２はそれぞれ、１つまたは複数のデータ媒体インターフェイス３２６によりシステムバス３０８に接続されている。別法として、ハードディスクドライブ３１６、磁気ディスクドライブ３１８、および光ディスクドライブ３２２はそれぞれ、１つまたは複数のインターフェイス（図に示されていない）によりシステムバス３０８に接続することもできる。
【００５７】
ディスクドライブおよび関連コンピュータ可読媒体は、コンピュータ３０２用のコンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータを格納する不揮発性ストレージを備える。例では、ハードディスク３１６、取り外し可能磁気ディスク３２０、および取り外し可能光ディスク３２４を示しているが、磁気カセットまたはその他の磁気ストレージデバイス、フラッシュメモリカード、ＣＤ−ＲＯＭ、デジタル多目的ディスク（ＤＶＤ）またはその他の光ストレージ、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、電気的消去可能プログラム可能読み取り専用メモリ（ＥＥＰＲＯＭ）などのコンピュータからアクセス可能なデータを格納できる他の種類のコンピュータ可読媒体が、例のコンピューティングシステムおよび環境の実装に使用できることも理解されるであろう。
【００５８】
ハードディスク３１６、磁気ディスク３２０、光ディスク３２４、ＲＯＭ  ３１２、および／またはＲＡＭ  ３１０には、たとえば、オペレーティングシステム３２６、１つまたは複数のアプリケーションプログラム３２８、その他のプログラムモジュール３３０、およびプログラムデータ３３２などのプログラムモジュールをいくつでも格納できる。このようなオペレーティングシステム３２６、１つまたは複数のアプリケーションプログラム３２８、その他のプログラムモジュール３３０、およびプログラムデータ３３２（またはその何らかの組合せ）のそれぞれにより、分散ファイルシステムをサポートする常駐コンポーネントの全部または一部を実装することができる。
【００５９】
ユーザーは、キーボード３３４およびポインティングデバイス３３６（たとえば、「マウス」）などの入力デバイスを介してコマンドおよび情報もコンピュータ３０２に入力することができる。他の入力デバイス３３８（図に特に示されてはいない）としては、マイク、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、シリアルポート、スキャナ、および／または類似の物などがある。これらの入力デバイスやその他の入力デバイスは、システムバス３０８に結合されている入出力インターフェイス３４０を介して処理ユニット３０４に接続されるが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）などの他のインターフェイスおよびバス構造により接続することもできる。
【００６０】
モニタ３４２やその他の種類の表示デバイスも、ビデオアダプタ３４４などのインターフェイスを介してシステムバス３０８に接続できる。モニタ３４２に加えて、他の出力周辺デバイスは、入出力インターフェイス３４０を介してコンピュータに接続することができるスピーカ（図に示されていない）およびプリンタ３４６などのコンポーネントを備えることができる。
【００６１】
コンピュータ３０２は、リモートコンピューティングデバイス３４８などの１つまたは複数のリモートコンピュータへの論理接続を使用してネットワーク環境で処理することができる。たとえば、リモートコンピューティングデバイス３４８は、パーソナルコンピュータ、携帯型コンピュータ、サーバー、ルーター、ネットワークコンピュータ、ピアデバイス、またはその他の共通ネットワークノードなどが考えられる。リモートコンピューティングデバイス３４８は、コンピュータ３０２に関して本明細書で説明している要素および特徴の多くまたはすべてを備えることができる携帯型コンピュータとして示されている。
【００６２】
コンピュータ３０２とリモートコンピュータ３４８との間の論理接続は、ローカルエリアネットワーク（ＬＡＮ）３５０および一般的なワイドエリアネットワーク（ＷＡＮ）３５２として示されている。このようなネットワーキング環境は、事務所、企業規模のコンピュータネットワーク、イントラネットおよびインターネットではよくある。
【００６３】
ＬＡＮネットワーキング環境に実装する場合、コンピュータ３０２はネットワークインターフェイスまたはアダプタ３５４を介してローカルネットワーク３５０に接続される。ＷＡＮネットワーキング環境に実装する場合、コンピュータ３０２は通常、モデム３５６またはワイドネットワーク３５２上で通信を確立するためのその他の手段を備える。モデム３５６は、コンピュータ３０２に内蔵でも外付けでもよいが、入出力インターフェイス３４０またはその他の適切なメカニズムを介してシステムバス３０８に接続できる。図に示されているネットワーク接続は例であり、コンピュータ３０２と３４８との間に通信リンクを確立する他の手段を使用できることは理解されるであろう。
【００６４】
ネットワーク環境では、コンピューティング環境３００、コンピュータ３０２に関して示されているプログラムモジュール、またはその一部とともに示されている物などをリモートのメモリストレージデバイスに格納することができる。たとえば、リモートアプリケーションプログラム３５８は、リモートコンピュータ３４８のメモリデバイスに常駐している。説明のため、アプリケーションプログラムおよび、オペレーティングシステムなどの他の実行可能なプログラムコンポーネントはここでは離散ブロックに示されているが、このようなプログラムおよびコンポーネントはさまざまな時期に、コンピューティングデバイス３０２の異なるストレージコンポーネント内に置かれ、コンピュータのデータプロセッサにより実行されることは理解されるであろう。
【００６５】
分散ファイルシステム１５０の一実施形態は、１つまたは複数のコンピュータまたは他のデバイスによって実行される、プログラムモジュールなどのコンピュータ実行可能命令の一般的文脈において説明できる。一般に、プログラムモジュールは、特定のタスクを実行するか、または特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。通常、さまざまな実施形態で、必要に応じて説明されているようにプログラムモジュールの機能を組み合わせるか、または分散させることができる。
【００６６】
暗号化ファイルのファイル形式の実装は、何らかの形式のコンピュータ可読媒体に格納または媒体を使って送信することができる。コンピュータ可読媒体は、コンピュータからアクセスできる使用可能な媒体とすることができる。たとえば、コンピュータ可読媒体は、「コンピュータ記憶媒体」および「通信媒体」を含むことができるが、それらには限定されない。
【００６７】
「コンピュータ記憶媒体」は、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータなどの情報を格納する方法または技術で実装される揮発性および不揮発性、取り外し可能および取り外し不可能媒体を含む。コンピュータ記憶媒体としては、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多目的ディスク（ＤＶＤ）またはその他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたはその他の磁気ストレージデバイス、または所望の情報を格納するために使用することができ、コンピュータによりアクセスできるその他の媒体があるが、それらには限定されない。
【００６８】
「通信媒体」は、通常、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータを搬送波またはその他のトランスポートメカニズムなどの変調データ信号で実現する。通信媒体は、任意の情報配信媒体も含む。「変調データ信号」という用語は、信号内の情報を符号化する方法でその特性のうち１つまたは複数を設定または変更した信号を意味する。たとえば、通信媒体としては、有線ネットワークまたは直接配線接続などの有線媒体、および、音響、ＲＦ、赤外線、およびその他の無線媒体などの無線媒体があるが、それらには限定されない。上記のいずれかの組合せもコンピュータ可読媒体の範囲に収まる。
【００６９】
階層型格納構造
分散ファイルシステム１５０は、１つまたは複数の名前空間ルートを含み、それぞれのルートがディレクトリまたはフォルダの１つまたは複数のサブツリーをサポートすることができ、それぞれのサブツリーは１つまたは複数の追加サブツリーをサポートすることができる、階層型ファイル格納構造を採用している。ディレクトリは、シミュレートされたファイルフォルダとみなすことができ、０個またはそれ以上のファイルおよび／または０個またはそれ以上の他のディレクトリを保持することができる。サブツリーは、１つまたは複数のディレクトリのことで、ルート（さらにこれは名前空間ルートも含むことができる）を含み、サブツリーのルートからそのサブツリーのすべてのメンバーへの経路がそのサブツリー自体の中にあるという特性を持つ。図４は、ディレクトリＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ、Ｊ、Ｉ、Ｍ、Ｋ、およびＬを含む複数のサブツリーを備える名前空間ルートを含む階層型名前空間４００の例を示している。通常、さらに多くのディレクトリが名前空間ルートのサブツリーに含まれるが、説明しやすくするため、図４にはごくわずかのディレクトリしか示されていない。
【００７０】
それぞれのサブツリーは、ディレクトリグループと呼ばれる１つまたは複数のコンピュータのグループにより管理される。本明細書では主に、サブツリーを管理するディレクトリグループとして説明しているが、別法として、１つまたは複数のディレクトリグループで名前空間内の任意の集まりのディレクトリを管理することができる。コンピュータの１つまたは複数のモジュールに対し、図２の制御モジュール２５０など、割り当てられているサブツリーを管理するためのディレクトリサービスを実装する役割が与えられる。一実施形態では、各ディレクトリグループは、後述のように、Ｂｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループ（または単にＢｙｚａｎｔｉｎｅグループと呼ぶ）である。しかし、ディレクトリグループは、Ｂｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループである必要はなく、他のグループを使用することもできる。
【００７１】
図４の実線は、どのディレクトリが他のどのディレクトリのサブディレクトリであるかを識別する、ディレクトリ間の関係を示している。たとえば、ディレクトリＣは、ディレクトリＢのサブディレクトリである。ディレクトリは、サブディレクトリから見てサブディレクトリの「親」ディレクトリとも呼ばれる。たとえば、ディレクトリＢは、ディレクトリＣの親ディレクトリと呼ばれる。
【００７２】
図４のそれぞれの点線のボックスは、特定の点線で囲まれているディレクトリを管理するディレクトリグループを示している。したがって、名前空間４００の例では、ルートの名前空間はディレクトリグループ４０２により管理され、ディレクトリＡ、Ｂ、Ｃ、ＦおよびＧはディレクトリグループ４０４により管理され、ディレクトリＤおよびＥはディレクトリグループ４０６により管理され、ディレクトリＨおよびＪはディレクトリグループ４０８により管理され、ディレクトリＫ、Ｉ、Ｌ、およびＭはディレクトリグループ４１０により管理される。
【００７３】
特定のディレクトリまたは名前空間を管理するディレクトリグループは、そのディレクトリに格納されている各ファイルのディレクトリエントリだけでなく、ディレクトリ内の各サブディレクトリのディレクトリエントリを保持する役割を持つ。ファイルの各ディレクトリエントリにより、ファイルが格納されている分散ファイルシステム１５０内の１つまたは複数のコンピュータが識別される。サブディレクトリの各ディレクトリエントリにより、そのサブディレクトリを管理する役割を持つディレクトリグループが識別される。ディレクトリエントリは、さらに、作成、修正、およびアクセスタイムスタンプ、読み込みおよび書き込みアクセス制御リスト、複製の場所の集まり、ファイルのサイズなどの追加情報も格納できる。
【００７４】
各ディレクトリグループは、名前空間ルートおよび／または名前空間内の１つまたは複数のサブツリーを管理する役割を持つ。各ディレクトリグループは、さらに、１つまたは複数の追加サブツリーを識別し、それらの追加サブツリーの管理責任を別のディレクトリグループに委任することができる。たとえば、ディレクトリＤおよびＥは、もともと、ディレクトリグループ４０４により管理されていたが、後から、ディレクトリグループ４０６に委任することができる。
【００７５】
ディレクトリグループでは、いつでも、サブツリーを他のディレクトリグループに委任することを決定できる。一実施形態では、この決定は作業負荷に基づいて行われ、ディレクトリグループは、過負荷になりつつあるとグループが判断した場合にサブツリーを委任する決定を下す。グループでは、過負荷になりつつあることを決定するためにさまざまなファクターを使用することができ、一実施形態では、各ディレクトリグループが、マシン１台当たりの予想ディレクトリ数の平均値にほぼ等しいサイズのサブツリーを管理しようとする（たとえば、１０，０００のオーダーで）。
【００７６】
サブツリーの委任先となるディレクトリグループを、さまざまな方法で決定できる。一実施形態では、委任を実行するディレクトリグループが、認識される分散ファイルシステム１５０からランダムにコンピュータを選択し、その選択されたコンピュータをサブツリーの委任先となる新しいディレクトリグループとして使用する。他のさまざまなファクターが選択プロセスに関わる（たとえば、可用性の低いコンピュータを選択しない、最近サブツリーを委任したコンピュータを選択しない、など）。
【００７７】
ディレクトリグループは、ディレクトリグループの１つまたは複数のメンバーにより電子署名された委任証明書を生成することにより特定のサブツリーを委任することができる。複数のメンバーが委任証明書に署名する状況では、署名プロセスはさまざまな形態を取りうる。一実施形態では、各メンバーは委任証明書の各自のコピーに署名する。他の実施では、委任証明書に再帰的に署名する（たとえば、あるメンバーが証明書に署名し、次にその電子署名された証明書に他のメンバーが署名するというように行う）。異なるメンバーが再帰的に証明書に署名する順序は、電子署名を検証する場合にベリファイヤ（ｖｅｒｉｆｉｅｒ）にその順序が知られている限り重要ではない（たとえば、署名の順序でベリファイヤを事前にプログラムしたり、順序を識別する情報を証明書に挿入しておくことができる）。４つのサイナー（ｓｉｇｎｅｒｓ）が再帰的に署名する証明書の例を以下に示す。
σs4(σs3(σs2(σs1(DC))))
ただし、ＤＣは、委任証明書が電子署名されることを表し、σsi（）は（）の内容がサイナーｉによって電子署名されたことを示す。
【００７８】
一実施形態では、ディレクトリグループ内のメンバー（コンピュータ）の数は、設計者が耐えられるようにしたいと考える障害のあるコンピュータの数に依存する。本明細書で使用しているように、障害のあるコンピュータとは、アクセス不可能な（たとえば、コンピュータの電源がオフになっている、あるいは故障している）コンピュータまたは破損しているコンピュータのことである（たとえば、悪意のあるユーザーまたはプログラムはコンピュータへのアクセス権を取得していると、適切な応答を与えないことにより、または不適切なデータを与えることにより、クエリに対し不適切な形で応答することができる）。一具体例では、ｆ台の障害のあるコンピュータを許容するために、ディレクトリグループは、３ｆ＋１台のコンピュータで構成する。さらに、この例では、少なくともｆ＋１台のコンピュータは委任証明書に電子署名する。
【００７９】
各名前空間ルートは、証明機関（ＣＡ）から取得した証明書に関連付けられている。証明機関は、名前空間の作成を検証する信頼できる機関である。サブツリーと関連するそれぞれの委任証明書は、現在のサブツリーから遡って０個またはそれ以上の他のサブツリーを通りＣＡによって署名された名前空間ルート証明書まで辿る証明書連鎖を含む。したがって、それぞれの委任証明書は、サブツリーを管理する認定ディレクトリグループであることを証明する複数の証明書に関連付けられている（証明書連鎖をＣＡによって署名された証明書まで遡って確定することにより）。
【００８０】
委任証明書は、異なるコンポーネントを含むことができ、一実施形態では、委任証明書は、（１）委任を実行するディレクトリグループにより管理されているサブツリーのルートの下にある委任されている経路の識別、（２）委任を実行するディレクトリグループに委任されているサブツリーのルートの識別、（３）委任されているサブツリーの識別、および（４）サブツリーの委任先となっているグループのメンバーの識別を含むことができる。サブツリーおよび経路メンバーの識別は変化する場合があり、実際のディレクトリ名（たとえば、ディレクトリＡ、Ｂ、Ｃ、Ｄなどの名前）または別法として、識別名（たとえば、グローバル一意識別子（ＧＵＩＤ））とすることができる。識別番号を使用することにより、ディレクトリ名が変更された場合でも委任証明書を作成し直す必要がない。
【００８１】
委任証明書の例は、図４に示されている。ディレクトリグループ４０２は、ＣＡから、グループ４０２が名前空間ルートを管理する権限のあることを示す証明書を取得する。この証明書は次のような形式である。
σOurCA("Root", GUIDRoot, DG402)                          （１）
ただし、σOurCAはＣＡ「ＯｕｒＣＡ」が証明書に署名したことを示し、「Ｒｏｏｔ」は名前空間ルートの名前であり、ＧＵＩＤRootは名前空間ルートのグローバル一意識別子であり、ＤＧ402はディレクトリグループ４０２のメンバーの名前（または他の識別子）を表す。
【００８２】
ディレクトリグループ４０２がディレクトリＡで始まるサブツリーをディレクトリグループ４０４に委任することに決めた場合、ディレクトリグループ４０２はディレクトリグループ４０４のメンバーに受け渡す委任証明書を生成する。この委任証明書は、上の証明書（１）とともに、以下の証明書を含む。
σDG402(GUIDRoot/A, GUIDA, DG404)                          （２）
ただし、σDG402は証明書がディレクトリグループ４０２のメンバーによって署名されたことを示し、ＧＵＩＤRoot／Ａはディレクトリグループ４０４（／Ａ）に委任される経路とともにディレクトリグループ４０２（ＧＵＩＤRoot）に委任されるサブツリーのルートのＧＵＩＤであり、ＧＵＩＤAは委任されるサブツリーのグローバル一意識別子（つまり、ディレクトリＡで始まるサブツリー）であり、ＤＧ404はディレクトリグループ４０４のメンバーの名前（または他の識別子）を表す。
【００８３】
同様に、ディレクトリグループ４０４がディレクトリＤで始まるサブツリーをディレクトリグループ４０６に委任することに決めた場合、ディレクトリグループ４０４はディレクトリグループ４０６のメンバーに受け渡す委任証明書を生成する。この委任証明書は、上の証明書（１）および（２）とともに、以下の証明書を含む。
σDG404(GUIDA/B/C/D, GUIDD, DG406)                        （３）
ただし、σDG404は証明書がディレクトリグループ４０４のメンバーによって署名されたことを示し、ＧＵＩＤA／Ｂ／Ｃ／Ｄはディレクトリグループ４０６（／Ｂ／Ｃ／Ｄ）に委任される経路とともにディレクトリグループ４０４（ＧＵＩＤA）に委任されるサブツリーのルートのＧＵＩＤであり、ＧＵＩＤDは委任されるサブツリーのグローバル一意識別子（つまり、ディレクトリＤで始まるサブツリー）であり、ＤＧ406はディレクトリグループ４０６のメンバーの名前（または他の識別子）を表す。
【００８４】
図の例では、委任証明書は、特定のサブツリー内のディレクトリ毎にではなく、委任時点で発行される。たとえば、委任証明書は、／Ａ／Ｂまたは／Ａ／Ｂ／ＣではなくＡ（サブツリー内の上位ディレクトリ）について発行される。
【００８５】
図４では、分散ファイルシステム１５０内の各コンピュータは、名前空間内のパス名のあるサブセットをそのパス名を管理するディレクトリグループにマッピングするローカルキャッシュ（たとえば、図２のキャッシュ２６０）を保持する。たとえば、特定のコンピュータのキャッシュは、パス名／Ａ、／Ａ／Ｂ、／Ａ／Ｂ／Ｃ、／Ａ／Ｆ、および／Ａ／Ｆ／Ｇのそれぞれからディレクトリグループ４０４へのマッピングを含むことができる。異なるコンピュータは、キャッシュ内に異なるマッピングを持つが、それぞれは通常、少なくとも名前空間ルートからその管理しているディレクトリグループ（ディレクトリグループ４０２）へのマッピングを含む。
【００８６】
管理しているディレクトリグループのマッピングへのパス名を保持することにより、コンピュータは、常に名前空間ルート（およびおそらくは他のディレクトリグループ）を管理しているディレクトリグループにアクセスしなくても、ディレクトリグループの検索プロセスの少なくとも一部を自動的にローカルで実行することができる。たとえば、コンピュータ側で、パス名が／Ａ／Ｂ／ｆｏｏ．ｔｘｔである「ｆｏｏ．ｔｘｔ」という名前のファイルにアクセスしようとし、コンピュータは、そのローカルキャッシュ内で、ディレクトリグループ４０４のパス名のマッピングを備えると仮定する。この例では、コンピュータは、自前のローカルキャッシュから、ディレクトリＢ内のファイルを管理するディレクトリグループ４０４のメンバーを、したがってファイルｆｏｏ．ｔｘｔを容易に識別することができる。そこで、ファイル「ｆｏｏ．ｔｘｔ」の場所を判別するためにアクセスするコンピュータ（つまり、どのコンピュータがパス名／Ａ／Ｂに対するディレクトリエントリを管理するか）の判別は、判別を行うためにディレクトリグループ４０２または４０４のいずれかにアクセスしなくても、キャッシュ内の情報に基づきコンピュータが実行する。
【００８７】
コンピュータは、ローカルキャッシュ内に、パス名全体をディレクトリグループにマッピングするための十分な情報がない場合、キャッシュ内に存在するパス名の最も長いプレフィックスに対するマッピングを見つける。その後、コンピュータは、その最も長いプレフィックスで最後のディレクトリを管理しているディレクトリグループにアクセスし、パス名の残り部分とその委任証明書をできるだけ多く管理するディレクトリグループを判別する。ディレクトリグループにアクセスし、委任証明書を取得するこのようなプロセスは、適切なマッピングが見つかるまで続けられる。
【００８８】
たとえば、コンピュータ側で、パス名が／Ａ／Ｂ／Ｃ／Ｄ／ｆｏｏ２．ｔｘｔである「ｆｏｏ２．ｔｘｔ」という名前のファイルにアクセスしようとし、コンピュータは、そのローカルキャッシュ内で、ディレクトリグループ４０６ではなく、ディレクトリグループ４０４のパス名のマッピングを備えると仮定する。コンピュータは、そのパス名を見て、パス名（／Ａ／Ｂ／Ｃ）内にあるキャッシュに含まれる最長のプレフィックスのマッピングを見つけ、ディレクトリグループ４０４である、そのディレクトリを管理する役目を負っているディレクトリグループにアクセスする。コンピュータは、ディレクトリグループ４０４のメンバーに対し、ディレクトリグループ４０６の委任証明書である、パス名／Ａ／Ｂ／Ｃ／Ｄ／ｆｏｏ２．ｔｘｔの関連するサブツリーに対する委任証明書を問い合わせる。ディレクトリグループ４０４のメンバーは、この委任証明書を問い合わせを行っているコンピュータに返し、このコンピュータはその委任証明書を検証することができる（たとえば、署名する側のコンピュータの公開鍵に基づいて）。受け取った委任証明書により、ディレクトリ／Ｄを管理する責任のあるディレクトリグループを識別し、コンピュータはファイル「ｆｏｏ２．ｔｘｔ」の場所を決定するためにそのディレクトリグループにアクセスすることを知る。したがって、ファイル「ｆｏｏ２．ｔｘｔ」の場所を判別するためにどのコンピュータにアクセスすべきかを判別する作業にディレクトリグループ４０４のメンバーへのアクセスが伴ったが、決定を下すためにディレクトリグループ４０２のメンバーへのアクセスは必要なかった。
【００８９】
ディレクトリおよびファイルの複製および格納
図１の分散ファイルシステム１５０は、ディレクトリエントリおよびそれらのエントリに対応するファイルの格納を異なる方法で管理する。システム１５０に格納されるファイルは複製され、システム１５０内の複数の異なるコンピュータに保存される。さらに、そのファイルに対するディレクトリエントリが作成され、これもまた、Ｂｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループの一部であるシステム１５０内の複数の異なるコンピュータ上に保存される。ディレクトリエントリの保存先コンピュータは、さらに以下で詳しく説明するように、ファイルの保存先コンピュータよりも多い。
【００９０】
明細書で説明しているファイルおよびディレクトリエントリの格納の異なる取り扱いを、上述の階層型格納構造と関連して使用できる。しかし、明細書で説明しているファイルおよびディレクトリエントリの格納の異なる取り扱いは、階層型格納構造を採用していないシステムでも使用できる。
【００９１】
Ｂｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループは、ある一定の台数のコンピュータに障害が生じている（危うい状態にあるかまたは利用できない状態にある）としても情報の格納および／または他のアクションの実行に使用できるコンピュータのグループである。コンピュータは、悪意のあるユーザーがコンピュータを操作している、悪意のあるプログラムがコンピュータ上で実行されているなどのさまざまな異なる形で危うい状態に置かれる場合がある。要求への応答に拒絶する、わざと正しくない情報またはゴミ情報などで要求に応答するなど、危うい状態にあるコンピュータについてあらゆる種類の処理が観察できる。Ｂｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループは、このような危うい状態にあるコンピュータが存在していても、情報の格納および／またはその他のアクションの実行を正確に行うことができる。Ｂｙｚａｎｔｉｎｅグループは、当業者にはよく知られており、したがって、本発明に関係している場合を除きこれ以上説明しない。
【００９２】
当業者には、一定数ｆの故障コンピュータがあってもある種の計算を正しく行えるようにするために（故障コンピュータはパワーダウン状態にあるなど危うい状態にあるかまたは何らかの形で利用できない状態にある）、Ｂｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループは少なくとも３ｆ＋１台のコンピュータを備えていなければならないことが知られている。分散ファイルシステム１５０では、ディレクトリエントリはＢｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループの３ｆ＋１台のコンピュータ上に格納されるが、ファイル自体はｆ＋１台のコンピュータ上に格納される（ディレクトリエントリが格納されるのと同じコンピュータの１つまたは複数であってよい）。
【００９３】
図５は、サーバーレス分散ファイルシステム内のファイルおよび対応するディレクトリエントリの格納例を示す図である。ファイルシステム５００（たとえば、図１のサーバーレス分散ファイルシステム１５０）は、１２台のコンピュータ５０２、５０４、５０６、５０８、５１０、５１２、５１４、５１６、５１８、５２０、５２２、および５２４を備える。システム５００の設計者は、２つのコンピュータ障害を許容できるようにすることを望んでいると仮定すると、Ｂｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループは少なくとも７（（３＊２）＋１）台のコンピュータを備える必要がある。Ｂｙｚａｎｔｉｎｅグループ５２６は、５０２〜５１４を含むように図に示されている。
【００９４】
ファイル５２８をファイルシステム５００に格納する場合、適切なディレクトリグループ内のコンピュータにより対応するディレクトリエントリ５３０が格納される（ディレクトリファイルを管理する役割を持つディレクトリグループは、ファイル５２８のパス名に基づいて格納される）。ディレクトリエントリ５３０に対する図５のディレクトリグループは、Ｂｙｚａｎｔｉｎｅグループ５２６であり、ディレクトリエントリ５３０はＢｙｚａｎｔｉｎｅグループ５２６内の正常に機能しているそれぞれのコンピュータ５０２〜５１４に格納される。したがって、ディレクトリエントリ５３０は最大７台までの異なるコンピュータ上に格納される。一方、ファイル５２８は、複製され、３台のコンピュータのそれぞれ（コンピュータ５１６、５２０、および５２４）に格納される。図に示されているように、ファイル５２８が格納されているコンピュータは、Ｂｙｚａｎｔｉｎｅグループ５２６になくてもよく、通常はない（しかしファイル５２８が格納されるコンピュータの１つまたは複数を任意選択によりＢｙｚａｎｔｉｎｅグループ５２６内に置くことも可能である）。
【００９５】
各ディレクトリエントリは、対応するファイルの名前、ファイルの格納先であるコンピュータの識別、およびファイルの内容をディレクトリエントリに対応する物として検証できるようにするファイル検証データを含む。ファイル検証データはさまざまな形態をとることができ、一実施形態では、ＭＤ５（Ｍｅｓｓａｇｅ  Ｄｉｇｅｓｔ  ５）、ＳＨＡ−１（Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ−１）などの暗号化セキュアハッシュ関数をファイルに適用することにより生成されるハッシュ値である。記憶域からファイルを取り出す場合、取り出し側コンピュータは、ハッシュ値を再生成し、その値をディレクトリエントリ内のハッシュ値と比較して、コンピュータが正しいファイルを受信したことを検証することができる。他の実施では、ファイル検証データは、ファイル識別番号（たとえば、ファイルの一意的識別子）、ファイルバージョン番号、およびファイルに付けられている署名のユーザーの名前の組合せである。
【００９６】
図６は、サーバーレス分散ファイルシステム内でファイルを格納するプロセスの例を説明する流れ図である。最初に、新しいファイル格納要求がクライアントコンピューティングデバイスに届く（処理６０２）。クライアントは、ファイルとファイル名を暗号化し、ファイル内容のハッシュを生成する（処理６０４）。クライアントは、暗号化されたファイル名およびファイル内容ハッシュを適切なＢｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔディレクトリグループに、ディレクトリエントリを作成する要求とともに送信する（処理６０６）。ディレクトリグループは、ファイル名が既存の名前と衝突していないか、クライアントに要求している内容を実行する許可が与えられているかを検証するなどして、要求の妥当性を確認する（処理６０８）。要求の妥当性が確認されない場合、要求は失敗する（処理６１０）。しかし、要求の妥当性が確認された場合、ディレクトリグループは新しいファイルのディレクトリエントリを生成する（処理６１２）。ディレクトリグループは、さらに、新しいファイルの複製セットを決定し、その複製セットを新規生成されたディレクトリエントリに追加する（処理６１４）。ファイルの複製も生成され（処理６１６）、ファイルシステム内の複数のコンピュータに保存される（処理６１８）。
【００９７】
Ｂｙｚａｎｔｉｎｅグループ内にディレクトリエントリを格納し、ファイル検証データをエントリに挿入することにより、フォールトトレランスが保持される（最大ｆ件までの障害）。しかし、格納領域要件およびＢｙｚａｎｔｉｎｅオペレーションは、Ｂｙｚａｎｔｉｎｅオペレーションを使用してアクセスせず、ディレクトリから別々にファイルを格納すると低減される。たとえば、ディレクトリエントリは１００バイトのオーダーになることもあるが、ファイル自体は数千さらには数十億バイトのオーダーとなる場合がある。
【００９８】
ディレクトリおよびファイルのロックメカニズム
図１の分散ファイルシステム１５０内の各オブジェクト（たとえば、ディレクトリおよびファイル）は、リースされたロックの集まりと関連付けられている。これらのロックは、アプリケーションで実行したいオペレーションの種類に基づいて、アプリケーションがそのオペレーションを実行するためディレクトリを開くのか、ファイルを開くのかを判別するために使用される。ロックは、ロックの種類および争奪のレベルによって決まる特定のタイムスパンを持つリースとみなすことができる。たとえば、書き込みロックのタイムスパンは数分程度であるが、読み込みロックのタイムスパンは数日程度と長い場合がある。アプリケーション側でオブジェクトにオペレーションを実行したい場合、アプリケーションが実行されているクライアントコンピュータは、オペレーションを実行するために必要なロックがすでにかかっているかどうかを調べる。ロックがまだかかっていなければ、そのオブジェクトを管理する役割を持つディレクトリグループに適切なロックを要求する。アプリケーションは、所望のオペレーションの実行を完了した後、任意選択により、取得されているロックを開放するか、または自動的にタイムアウトになるか、または管理するディレクトリグループによりリコールされるまで保持することができる。
【００９９】
特定のディレクトリについて、ディレクトリを実装するＢｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループは、そのディレクトリ内のすべてのファイル、ディレクトリのサブディレクトリの名前、およびディレクトリ自体を削除する権限に対するロックを管理する。このロックメカニズムは、適切なファイルおよびディレクトリ上の広範な（粒度が粗い）ロックを要求側クライアントコンピュータに付与し、クライアントコンピュータが多数の読み込みおよび／または更新を、ロック取得に対してＢｙｚａｎｔｉｎｅメッセージを何回も要求せずに１回のＢｙｚａｎｔｉｎｅロック取得で処理できるようにする。
【０１００】
図の例では、ロックメカニズムは１０種類の異なるロック、つまり、Ｒｅａｄ、Ｗｒｉｔｅ、Ｏｐｅｎ  Ｒｅａｄ、Ｏｐｅｎ  Ｗｒｉｔｅ、Ｏｐｅｎ  Ｄｅｌｅｔｅ、Ｎｏｔ  Ｓｈａｒｅｄ  Ｒｅａｄ、Ｎｏｔ  Ｓｈａｒｅｄ  Ｗｒｉｔｅ、Ｎｏｔ  Ｓｈａｒｅｄ  Ｄｅｌｅｔｅ、Ｉｎｓｅｒｔ、およびＥｘｃｌｕｓｉｖｅを採用している。ＲｅａｄおよびＷｒｉｔｅロックは、オブジェクト内のデータへのアクセスを制御する場合に使用する（たとえば、ファイルの内容）。Ｏｐｅｎ  Ｒｅａｄ、Ｏｐｅｎ  Ｗｒｉｔｅ、Ｏｐｅｎ  Ｄｅｌｅｔｅ、Ｎｏｔ  Ｓｈａｒｅｄ  Ｒｅａｄ、Ｎｏｔ  Ｓｈａｒｅｄ  Ｗｒｉｔｅ、およびＮｏｔ  Ｓｈａｒｅｄ  Ｄｅｌｅｔｅロックは、オブジェクトを開く操作を制御する場合に使用する。ＩｎｓｅｒｔおよびＥｘｃｌｕｓｉｖｅロックは、専用ロックである。これら１０個のロックについて、以下で詳述する。アプリケーション側で実行したいオペレーションに応じて、これらのロックのうちの適切な物がアプリケーションから要求される。
【０１０１】
Ｒｅａｄロック。Ｒｅａｄロックは、アプリケーションが関連するファイルを読み込めるようにアプリケーションによって要求される。Ｒｅａｄロックを、Ｗｒｉｔｅロックとともに使用すると、ディレクトリグループでファイル内のデータの一貫性を保持することができる。
【０１０２】
Ｗｒｉｔｅロック。Ｗｒｉｔｅロックは、アプリケーションが関連するファイルに書き出せるように（更新ともいう）アプリケーションによって要求される。Ｗｒｉｔｅロックを、Ｒｅａｄロックとともに使用すると、ディレクトリグループでファイル内のデータの一貫性を保持することができる。
【０１０３】
アプリケーション側でオブジェクトを開きたい場合、ディレクトリグループは、（１）モードはアプリケーションがすでにそのオブジェクトを開いてしまっている他のアプリケーションと衝突することを要求しているか、（２）オペレーションは、他のアプリケーションがすでに開いてしまっていて、共有する意志のあることを示しているそのオブジェクトの内容と衝突することになるということについてオブジェクトを共有するつもりであるオペレーションであるかという２つのチェックを実行する。Ｏｐｅｎ  Ｒｅａｄ、Ｏｐｅｎ  Ｗｒｉｔｅ、Ｏｐｅｎ  Ｄｅｌｅｔｅ、Ｏｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｒｅａｄ、Ｏｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｗｒｉｔｅ、およびＯｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｄｅｌｅｔｅという１０個のロックのうちの６個がこのチェックをサポートすることを対象としている。これらのロックは、オブジェクトを開く機能をアプリケーションに付与するために使用されるが、必ずしも、そのオブジェクトに対するデータを取得できることを保証していない（ＲｅａｄロックまたはＷｒｉｔｅロック（アプリケーション側で実行したいオペレーションの種類による）を取得してデータにアクセスする）。
【０１０４】
Ｏｐｅｎ  Ｒｅａｄロック。Ｏｐｅｎ  Ｒｅａｄロックは、アプリケーションが読み込みのため関連するオブジェクトを開けるようにアプリケーションから要求される。
【０１０５】
Ｏｐｅｎ  Ｗｒｉｔｅロック。Ｏｐｅｎ  Ｗｒｉｔｅロックは、アプリケーションが書き込みのため関連するオブジェクトを開けるようにアプリケーションから要求される。
【０１０６】
Ｏｐｅｎ  Ｄｅｌｅｔｅロック。Ｏｐｅｎ  Ｄｅｌｅｔｅロックは、アプリケーションが削除のため関連するオブジェクトを開けるようにアプリケーションから要求される。
【０１０７】
Ｏｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｒｅａｄロック。Ｏｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｒｅａｄロックは、アプリケーションが他のアプリケーションとオブジェクト読み込み機能を共有するつもりがない場合にアプリケーションによって要求される。
【０１０８】
Ｏｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｗｒｉｔｅロック。Ｏｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｗｒｉｔｅロックは、アプリケーションが他のアプリケーションとオブジェクト書き込み機能を共有するつもりがない場合にアプリケーションによって要求される。
【０１０９】
Ｏｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｄｅｌｅｔｅロック。Ｏｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｄｅｌｅｔｅロックは、アプリケーションが他のアプリケーションとオブジェクト削除機能を共有するつもりがない場合にアプリケーションによって要求される。
【０１１０】
サポートされている他の２つのロックはＩｎｓｅｒｔロックおよびＥｘｃｌｕｓｉｖｅロックである。
【０１１１】
Ｉｎｓｅｒｔロック。Ｉｎｓｅｒｔロックは、ディレクトリ内のオブジェクト用に特定の名前を作成するようにアプリケーションによって要求される。Ｉｎｓｅｒｔロックを付与すると、アプリケーションは特定の名前でオブジェクトを作成する権限が与えられる。Ｉｎｓｅｒｔロックは、同じオブジェクト名を持つ他のＩｎｓｅｒｔロックおよびそのディレクトリ上のＥｘｃｌｕｓｉｖｅロックと衝突する。
【０１１２】
Ｅｘｃｌｕｓｉｖｅロック。Ｅｘｃｌｕｓｉｖｅロックは、ディレクトリ内に存在しうる（が、すでに存在しているわけではない）それぞれの使用可能な名前に対するＩｎｓｅｒｔロックを含む、前記の９つのロックのすべてを取得するように、アプリケーションによって要求される。ディレクトリに対するＥｘｃｌｕｓｉｖｅロックは、ディレクトリ内のファイルまたはサブディレクトリに対するＥｘｃｌｕｓｉｖｅロックを暗黙のうちに含むことはないが、むしろ、ディレクトリの名前空間のみに対するＥｘｌｃｕｓｉｖｅロックを含む。Ｅｘｃｌｕｓｉｖｅロックは、前記の９つのロックのそれぞれと衝突する。
【０１１３】
さまざまな異なるロックの間に、いろいろな衝突が存在する。表Ｉは、一実施形態のロック間の衝突を示す衝突マトリックスである。表Ｉでは、Ｉｎｓ  （Ｉｎｓｅｒｔ）、Ｅｘｃｌ  （Ｅｘｃｌｕｓｉｖｅ）、Ｏ−Ｒ  （Ｏｐｅｎ  Ｒｅａｄ）、Ｏ−Ｗ  （Ｏｐｅｎ  Ｗｒｉｔｅ）、Ｏ−Ｄ  （Ｏｐｅｎ  Ｄｅｌｅｔｅ）、Ｏ−！Ｒ  （Ｏｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｒｅａｄ）、Ｏ−！Ｗ  （Ｏｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｗｒｉｔｅ）、およびＯ−！Ｄ  （Ｏｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｄｅｌｅｔｅ）という略記を使用する。表Ｉのセル内の「Ｘ」は、対応する２つのロックの間の衝突を示すが、たとえば、Ｏｐｅｎ  ＲｅａｄはＯｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｒｅａｄと衝突するが、Ｏｐｅｎ  Ｎｏｔ  Ｓｈａｒｅｄ  Ｗｒｉｔｅとは衝突しない。
【０１１４】
【表１】
2011008818.tif 000003
【０１１５】
１つのクライアントコンピュータのみが名前空間のある領域にアクセスした場合にパフォーマンスを高めるため、ファイルシステム１５０は、アプリケーション（またはクライアント）が近い将来追加関連ロックを要求する可能性が高いという仮定のもとで、クライアント要求に対し実行されているアプリケーションよりも広い範囲のロックを発行することができる。たとえば、アプリケーションがファイル／Ａ／Ｂ／Ｃ／ｆｏｏ．ｔｘｔを開く場合、クライアントはこのファイルのロックを要求する。ディレクトリグループがロックを付与する場合、これはロックを／Ａ／Ｂ／Ｃのディレクトリロックにアップグレードすることができる（たとえば、過去のパフォーマンスに基づいて、ディレクトリグループがそのディレクトリ上の衝突がまれであると判断する）。アプリケーションが同じディレクトリ内の他のファイルを開く場合、クライアントはディレクトリグループに他のロックを要求することなく、ファイルを開くことができる。
【０１１６】
クライアントのロック要求が他のクライアントに付与されている既存のロックと衝突する場合、ディレクトリグループは、以前発行したロックを、要求を拒絶するのではなく、新しい要求と衝突しないロックにダウングレードしようとする。ロックアップグレードを行うと、クライアントは要求しなかったロックを保持し、ロックダウングレードの成功の確率は、通常、非自明な値となる。ロックのリコールが失敗した場合、その要求は拒否される。
【０１１７】
さまざまなオペレーションをファイルシステム内のオブジェクトに対して実行することができる。以下の表ＩＩは、より一般的なオペレーションのうちのいくつかと、それらのオペレーションを実行するためアプリケーションによって要求されるロックをまとめた。
【０１１８】
【表２】
2011008818.tif 000004
【０１１９】
ファイルに変更を加える場合、変更は、コンピュータによりローカルで行われ、その後、ファイル（暗号化された後に）はそのファイルを管理する役割を持つディレクトリグループにプッシュされ戻される。この情報はディレクトリグループ内のさまざまなコンピュータに格納され、更新されたファイルは適切なコンピュータに格納される。
【０１２０】
セキュアクラッシュリカバリ（Ｓｅｃｕｒｅ  Ｃｒａｓｈ  Ｒｅｃｏｖｅｒｙ）
図１を再び参照すると、上述のシステムは、不正ユーザーおよびマシンによる変更またはアクセスを防止して、分散ファイルシステム１５０内にファイルを格納し、ファイルおよびディレクトリエントリの格納を管理する。ファイルがシステム内の複数の異なるコンピュータ上のシステム１５０内に複製され、格納されているとしても、ディレクトリエントリ、およびシステム内の複数の異なるコンピュータ上に保存されているファイルに対して保護が実施される。ファイルの書き込みでは、いくつかの故障／安全でないコンピュータｆ（安全でない／故障コンピュータは、停電など危うい状態にあるかまたは他の何らかの形で利用できない状態にある）にも関わらず連携する必要があるコンピュータの台数について、Ｂｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループは少なくとも３ｆ＋１台のコンピュータを含んでいる必要がある。分散ファイルシステム１５０では、ディレクトリエントリはＢｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループの３ｆ＋１台のコンピュータ上に格納されるが、ファイル自体はｆ＋１台のコンピュータ上に格納される（ディレクトリエントリが格納されるのと同じコンピュータの１つまたは複数であってよい）。
【０１２１】
ファイル書き込みでは、ローカルマシンであってもクラッシュなどの致命的な障害の後、またはユーザーがマシンからログアウトした後に保護を実施する必要がある。より具体的には、ユーザーがマシンにログインした場合、そのマシンがユーザーに代わってファイルを更新するということである。分散ファイルシステムの一部であるファイルに更新を加えた場合、更新はシステムに即座にアップロードされるわけではない。むしろ、システムリソースに関しては、即時アップロードはひどくコストが高くつく。ログインして更新を実行した後、ユーザーがマシンからログアウトするか、またはマシンでクラッシュした場合、クラッシュまたはログアウトイベントに先立ってユーザーが正当に加えた変更をアップロードできる状態をマシンが保持している間に、ユーザーがログインできなくなった場合に、ユーザーに代わって処理できる状態をマシンが保持することを防止する必要がある。それぞれの書き込みにユーザーのＲＳＡ秘密鍵で署名させると、マシンがデータとともに書き込みを認証する署名を格納しているため後からアップロードすることが可能である。マシンが書き込みの認証のセキュアディレクトリグループを納得させる必要があった場合、できるならマシンはデータとともに証明書を送信する。しかし残念なことに、この解決策もまた、過剰なマシンリソースが要求される。たとえば、ＲＳＡ秘密鍵演算に基づく署名に対するコストは、現在のディスクの約６〜８ｍｓのディスク待ち時間と比較して１ＧＨｚプロセッサ上でコンピュータ処理（ＣＰＵ）時間は約６．５ｍｓである。好ましくは、システムでは、ファイル書き込みのクリティカルパスではこのようなコスト高を回避することになる。本明細書で提示している実施形態によれば、システム１５０などのシステムに対する保護は効率がよく、ユーザーの秘密鍵が証明提示の際に利用可能でない場合にファイル書き込みに対する保護が行われる。
【０１２２】
委任証明書
図７および図８の組合せを参照すると、本発明の一実施形態は、委任証明書を使用してファイル書き込み保護を処理する。この実施形態によれば、ユーザーがまずファイル７１０を書き込む場合、ユーザーは、委任証明書に示されている予め定めた基準に従ってマシン１０６上のクライアントソフトウェア２０４がユーザーに代わりファイル７１０を更新するのを許可するユーザーの秘密署名鍵で委任証明書７２０に署名する（処理８１０）。たとえば、この基準により、委任証明書を限られた時間に限定すること、および／または新しいバージョン番号のファイル７１０にのみ変更を許可することが可能である。クライアントマシン１０６は、暗号化されたファイルデータとともにローカルディスクの分散ファイル部分１２８に証明書を格納する（処理８２０）。同じファイルにその後書き込みを行うと、マシン１０６はデータを分散ファイル部分１２８に書き込む。マシン１０６がクラッシュして再起動し、ネットワーク１１０に対し更新ファイルがある場合、マシン１０６は更新のログをディレクトリグループ内の複製７５０に送信し、委任証明書７２０を挿入する（処理８４０）。複製７５０は、委任証明書をチェックし、正しいバージョン番号を識別する指示、証明書が期限切れになっておらず、正しいマシンの名前を指定しているという指示などの予め定めた基準を満たした場合のみ（処理８５０）変更を受け付ける。通常のケースでは、マシンがクラッシュしない場合、ファイルは正常に閉じられ、ディレクトリ内に格納されているファイル内容のハッシュ表現を、たとえば、すでに存在している可能性のあるセキュリティ保護されたマシン間接続を使用して、複製７５０に送信することができる。ユーザーが、変更を複製グループ７５０にアップロードする前にマシン１０６からログアウトした場合、修正されたファイルのハッシュに対しユーザーの秘密鍵で署名する。ユーザーは、ユーザーがログアウトし、複製７５０がユーザーの代わりにマシン１０６からもうそれ以上要求を受け付けることができなくなった場合に、委任証明書を取り消す（処理８６０）。取り消しでは、取り消し証明書を格納するために複製されたオペレーションを実行する必要がある。
【０１２３】
一実施形態では、委任証明書は、ディレクトリグループによってチェックされるいくつかのセキュリティ項目のうちの１つである。たとえば、ファイル７１０を閉じて、ディレクトリに更新を送信する前に、ローカルマシンにクラッシュが発生した場合、更新がディレクトリグループに届くと、委任証明書７２０上のユーザーの署名とファイル７１０の内容のマシン１０６による署名とを比較することで、ファイルの有効性をチェックすることができる。
【０１２４】
図７および８で説明している方法は、マシン１０６がクラッシュしてもユーザーの鍵を損なうことはないが、いくつかの欠点がある。特に、マシン１０６上でユーザーがファイル７１０を書き込み、マシン１０６がクラッシュして、マシンが損なわれ、たとえば、ファイル７１０がクラッシュ時点で開いていると仮定する。ユーザーからの委任証明書がマシン１０６上に存在し、委任証明書がユーザーによって取り消されていないため、マシン１０６は、再起動の後任意の方法でファイル７１０を変更することができる。したがって、Ｏｕｔｌｏｏｋのデータベースファイルなど常時開いているある種のファイルでは、このような脆弱性は望ましくないリスクとなりうる。そこで、不本意なシャットダウンが発生した場合、通常であれは、Ｏｕｔｌｏｏｋの．ｐｓｔファイルに委任証明書が使用されることになり、攻撃者がその時を狙ってこの脆弱性につけ込む可能性がある。しかし、委任証明書法では、委任証明書の脆弱性はクラッシュ時に行われる修正を受けるファイルにのみ制限されるという意味でファイルが保護されるのである。したがって、その証明書の影響を受けないファイルは修正されず安全である。
【０１２５】
一実施形態では、委任証明書は、有効期限による期間制限が課せられている。しかし、委任証明書の都合の悪い時期が期限切れの日だと、ローカルマシンがデータアップロードを行えなくなった場合にさらに問題が大きくなる可能性がある。一方、データアップロードを行えるように委任証明書のタイムアウトを長くとると、マシン１０６が脆弱な状態に置かれている期間が長くなり攻撃者に付け込まれるおそれがある。この弱点に対処するため、一実施形態では、そうすることが可能であれば復旧したマシンにクラッシュ後直ちにグループとコンタクトを取らせることを目的としている。たとえば、マシン１０６は再起動直後に破損ファイルを保持している可能性があるか、またはマシンは再起動に長い時間がかかりファイル７１０をネットワーク１１０に送り返すことができない。
【０１２６】
一実施形態では、委任証明書７２０は最初の書き込みの後に生成される。別法として、書き込み許可でファイル７１０を開き、最初に書き込むまでの間のある時点に委任証明書を生成することができる。生成時に署名された委任証明書７２０をマシン１０６上のローカルログに追加することができる。
【０１２７】
ディレクトリグループがユーザーに代わってより強力な委任証明書を発行する場合、すべてのファイルに対し委任証明書の署名を回避することができる。たとえば、その委任証明書を（ユーザーに書き込み権限がある）ディレクトリ内のすべてのファイルまたは限られたバージョン番号の集まりに対する他の何らかのファイル群に適用することができる。もちろん、このようなことを行うと、ユーザーの脆弱性が増す、つまり、マシンはクラッシュ後の集まりの中の（ユーザーに修正の権限がある）ユーザーのファイルのすべてについてユーザーに代わって処理することが可能である。
【０１２８】
秘密鍵共有を使用する権限委任
図９と図１０をまとめて参照すると、他の実施形態では、ファイルの書き込み後クライアントマシンを信頼しなくても、ファイル書き込みのクリティカルパスで秘密鍵署名を回避するアプローチを対象としている。図９に示されているように、ファイルシステム９００は、７台のコンピュータ９０２、９０４、９０６、９０８、９１０、９１２、および９１４を含むＢｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループ９２６である。システム９００の設計者が、２つのコンピュータ障害を許容できるようにすることを望んでいると仮定すると、Ｂｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループは少なくとも７（（３＊２）＋１）台のコンピュータを備える。ディレクトリエントリ９３０は、７台のコンピュータ９０２〜９１４と共有される。
【０１２９】
一般に、クライアントコンピュータ９１６がＢｙｚａｎｔｉｎｅグループ９２６に更新９１８などの更新ファイルに対する書き込みロックを要求する場合、ユーザーに代わってその作業が行われる。ロックが発行された場合、ユーザーは新しいバージョンのファイルを生成することが許可される。バージョン番号は、クライアントコンピュータ９１６が書き込みロックを解除し、実際にファイルが修正されると増分される。
【０１３０】
秘密鍵共有を使用する方法によれば、クライアントコンピュータ９１６がディレクトリグループ９２６にコンタクトを取り、たとえば、ユーザーに代わってファイル書き込みを実行したい場合、秘密鍵Ｋが作成される（処理１００１）。ユーザーがＭを、秘密鍵を決定するために必要な、秘密鍵の割り当て分の個数または秘密鍵の異なる部分を表す物と決定し、Ｍをｆ＋１とすることにより決定され（処理１００２）、ユーザーは再構成しきい値Ｍとともに秘密鍵ＫをＮ個の割り当て分に分割する（処理１００４）。グループ９２６については、Ｍは３でなければならない。したがって、秘密鍵のユーザー／作成者は、Ｎを、ディレクトリエントリ（３ｆ＋１）および
【０１３１】
【数１】
2011008818.tif 000005
【０１３２】
を保持する複製グループ９２６のサイズとなるように選択しなければならない。
【０１３３】
最初にディレクトリグループとコンタクトを取る場合、ユーザーはクライアント９１６を介して、Ｎ個の割り当て分を、この場合には７個の割り当て分をグループ９２６のそれぞれのメンバーに１つずつ受け渡す（処理１００６）（しかし、一部のグループメンバーがグループ内でアクティブでない場合、クライアント９１６は、メンバーがアクティブになるまで、またアクティブにならない限り、それらのグループメンバーの割り当て分を送信しないが、いつでもせいぜいｆ個のメンバーが非アクティブ状態にあると仮定している）。コンピュータ９０２〜９１４のうち３台のコンピュータは、対称鍵などの鍵である秘密鍵Ｋを復元する必要がある。秘密鍵Ｋは、クライアントコンピュータ９１６上のユーザーに知られており、ユーザーはこの秘密鍵Ｋを使用して、ディレクトリグループ９２６に送信されるファイル書き込みおよび更新ファイルを認証する。特に、クライアント９１６上のユーザーがファイルを更新する場合、秘密鍵Ｋを更新ファイルとともに鍵として使用してメッセージ認証コード（ＭＡＣ）を作成する（処理１００８）。図からわかるように、ＭＡＣは、対称鍵、この場合は秘密鍵Ｋにより暗号化されているファイルデータのＳＨＡ−１タイプのハッシュなどの一方向ハッシュ関数とすることができる。システム要件に応じて、秘密鍵Ｋをファイルデータの一部と組み合わせて、ＭＡＣを作成したり、更新全体と組み合わせてＭＡＣを形成することもできる。ＭＡＣ形成のコストを制限要因とみなすシステムでは、この方法をデータの一部に対して適用し、コンピューティングリソースを節約することができる。逆に、システムがＭＡＣ形成のコストをセキュリティに比べてあまり重要でないとみなす場合、この方法をＭＡＣ形式に適用して、ファイル全体を含むようにできる。
【０１３４】
秘密鍵ＫおよびそのＮ個の割り当て分は、クライアントマシン９１６上に格納されており、マシンがクラッシュしたり、ユーザーがログアウトした場合（処理１０１０）、これらは忘れ去られる。したがって、マシンがクラッシュしたり、ユーザーがログアウトした場合、マシンはＭＡＣがもう添付されていないログエントリのＭＡＣを生成することはできないが、それは、このようなＭＡＣを生成する作業には忘れられた秘密鍵Ｋを知っている必要があるからである。クラッシュもログアウトイベントもない場合、マシンはユーザーの信用情報を保持しており、これを使用すれば、サーバーグループ９２６とのセキュリティ保護された接続を確立し、このサーバーグループ上でグループが添付されているＭＡＣを検証しなくてもログを受け付ける。逆に、クラッシュまたはログアウトがある場合、マシンは、ユーザーの信用情報を保持せず、サーバーグループ９２６との適切なセキュリティ保護された接続を確立することはできないが、その代わりに、たとえば、これは再起動に基づくことができるが、クライアントコンピュータ９１６が可能である場合、たとえば、クライアントコンピュータ９１６は一実施形態により、自動的に、セキュリティ保護されていないチャネル上で更新および関連するＭＡＣをグループに送信する（処理１０１０）。
【０１３５】
ディレクトリグループ９２６は、ＭＡＣと更新をログの形式で受け取る。しかし、ログは認証セッションの外部から送られるので、ＭＡＣは秘密鍵Ｋを使用して作成されるため、秘密鍵共有法で更新を実行することができる。特に、図１１に示されているように、ディレクトリグループは更新ログの形でＭＡＣおよび更新を受け取る（処理１１１０）。ディレクトリグループは、ログのシリアル番号をチェックし、欠損している更新がないか（処理１１１２）、グループのそれぞれのアクティブな、正しく機能しているメンバーが秘密鍵Ｋの割り当て分を公開しているかを検証する（処理１１２０）。ディレクトリグループ９２６は、ＫのＭ個の正しい割り当て分を受け取るまで、または２ｆ＋１個の割り当て分を受け取るまで、受け取った割り当て分が正しかろうとなかろうと、待機する（処理１１３０）。ディレクトリグループは、受け取った割り当て分が正しいかどうかを判別する（処理１１４０）。さらに具体的には、受け取った割り当て分が何らかの秘密鍵Ｋの割り当て分の正しい集まりになっていない場合、ディレクトリグループでは、割り当て分を生成した際にクライアントが破損していると想定し、ログを破棄する（処理１１４０および１１５０）。秘密鍵Ｋが再構成される場合、ディレクトリグループ９２６は、秘密鍵Ｋを使用して、更新ログ内のＭＡＣを検証する（処理１１６０）。ＭＡＣが正しい場合、ディレクトリグループは、ログを認証されている物として受理し、ログ内の更新をそれが認証チャネル上で注目しているユーザーからきた物であるかのように適用する（処理１１７０）。ＭＡＣがチェックしない場合、ログは破棄される（処理１１５０）。一実施形態によれば、ログを破棄する決定は、ログ内の更新に割り当てられたシリアル番号をチェックする作業を含んでいる。たとえば、ディレクトリグループが秘密鍵Ｋの割り当て分を公開する処理を実行するのに先立って、ディレクトリグループに届いたそれぞれのログのチェックを、シリアル番号のリストまたは他の順序チェックメカニズムと突き合わせて行い、受け取ったログが予め定めた順序であることを確認する（処理１１１２）。そのようにして、順序の狂っている更新は実行できなくなっており、悪意のあるマシンは検出を免れずに有効なログの真ん中からオペレーションを削除できず、残りを送信することはできない。順序チェックを行った後、メンバーは秘密鍵Ｋの割り当て分を公開することができ（処理１１２０）、その割り当て分により秘密鍵Ｋが再作成されない場合または２ｆ＋１個の正しい割り当て分が届いていない場合（処理１１３０および１１４０）、ディレクトリグループはログを破棄する（処理１１５０）。
【０１３６】
一実施形態では、秘密鍵Ｋは、同じユーザー、クライアントマシン、およびディレクトリグループを共有するすべての書き込みについて関連付けられている単一の鍵である。この実施形態では、ＭＡＣはディレクトリグループ内の各メンバーに送信され、秘密鍵Ｋの割り当て分を持つ少なくともｆ＋１個のメンバーは鍵を再構成する必要がある。したがって、この実施形態では、鍵は、特定のＢｙｚａｎｔｉｎｅグループについて関連するすべての書き込みを対象とすることができる。
【０１３７】
オーセンティケータ
他の実施形態によれば、秘密鍵共有の代わりに、メッセージ認証コード（ＭＡＣ）のベクトルを使ってファイル書き込みを保護している。この実施形態では、クライアントマシンからの追加信用なしで、メッセージ認証コードのベクトルに権限が委譲される。図１２を参照すると、クライアントマシンは、ディレクトリグループのメンバー間に分散するように構成される複数の秘密鍵を作成し、ディレクトリグループのメンバー毎に秘密鍵を１つ作成する（処理１２１０）。複数の秘密鍵には、ディレクトリグループの各メンバーにより個別に確立される複数の秘密対称セッション鍵を含めることができ、したがって、各メンバーマシンと個々のユーザーの間に対称鍵関係を確立できる。ユーザーは、ファイルを作成し、そのファイルを複数の秘密鍵とともにディレクトリグループに送信するか、またはファイルを送信することなくオフラインでメンバーのそれぞれとの対称鍵関係を確立することができる。いかなる場合も、クライアントマシンは、１つの秘密鍵をディレクトリグループメンバーのそれぞれに送信する（処理１２２０）。
【０１３８】
一般に、ユーザーが更新を生成し、後で送信するためその更新をログに格納する場合、ログには複数のメッセージが格納され、それぞれのメッセージにはＭＡＣのベクトルが添付され、それぞれのＭＡＣは処理１２１０で生成された鍵のうちの１つで鍵合わせしたベクトル内に置かれている（処理１２３０）。クライアントマシンが、一実施形態により認証チャネルセッションをいきなり終了させるなどクラッシュまたはその他の致命的イベントのせいで使用不能になった場合、クライアントは鍵を忘れ（処理１２４０）、ログ内の更新は認証チャネルの外部に送信される（処理１２６０）。当業者であれば、ＭＡＣのベクトル内の各ＭＡＣは、対称鍵、または他の多数のＭＡＣアルゴリズムのうちの１つで暗号化された更新ログ記録（それ自体、ファイル内容のセキュアハッシュを含む）の一方向ハッシュ関数であることを理解するであろう。この場合、１つのＭＡＣを送信するのではなく、複数のＭＡＣを送信し、各ＭＡＣではクライアントとディレクトリグループのうちの１つのメンバーにしか知られていない異なる秘密鍵を使用している。ディレクトリグループのそれぞれの正常に機能しているメンバーは鍵を受け取る。一実施形態では、別々の対称鍵をユーザー、クライアントマシン、およびディレクトリグループメンバー毎に設定する。たとえば、ユーザーは、複製／ディレクトリグループメンバー毎に１つのＭＡＣエントリによりオーセンティケータを計算することにより各書き込みを認証することができる。クラッシュなどに続いてクライアントマシンが再起動した後（処理１２４０）、復旧すると、マシンはオーセンティケータをディレクトリグループに送信することができる（処理１２６０）。グループの各メンバーは、対応するＭＡＣを別々に検証し、更新を受け入れるかまたは更新を拒絶する（処理１２７０、１２８０、および１２９０）。一実施形態では、更新を許可するためには（処理１２８０）ＭＡＣのｆ＋１回の検証が必要であり（処理１２７０）、そうでなければ、更新は拒絶される（処理１２９０）。
【０１３９】
一実施形態では、ＭＡＣのベクトル内のＭＡＣの少なくとも１つを作成するために使用される対称鍵の１つまたは複数は、ディレクトリグループの１つまたは複数のメンバーに対する要求を認証するためなどの他の目的にも使用される鍵である。上述の秘密鍵共有法などの他の実施形態では、それぞれの更新をシリアル番号に関連付けて、順序の狂っている更新を許可しないようにできる。
【０１４０】
都合のよいことに、秘密鍵共有法とＭＡＣベクトルを使用する方法の両方において、ＭＡＣを計算するための暗号法が十分に強いと仮定すると、攻撃者は、ｆ＋１個のＢｙｚａｎｔｉｎｅグループメンバーに対する制御権を取得した場合またはクライアントマシンから秘密鍵を学習できる場合に書き込み要求を改ざんすることぐらいしかできない。クライアントマシン内の鍵は、ページングファイルに入り込むのを回避するために、メインメモリ内に、またピン留めページに保持し、マシンがクラッシュした場合に鍵が破棄されることが好ましい。さらに、ユーザーは、いつでも鍵を破棄することができ、特に、一実施形態ではユーザーは、ログアウトしたい場合に鍵を破棄することが必要である。
【０１４１】
バージョン検証
上述の委任証明書、秘密鍵共有、およびＭＡＣベクトル法は、それぞれ、更新および／またはファイル署名をＢｙｚａｎｔｉｎｅグループによって格納されるのに先立って、他の保護手段を含めることができる。
【０１４２】
特に、図１３とともに図９を参照すると、バージョン検証を対象とする方法がある。クラッシュした後、クライアントコンピュータ９１６は、秘密Ｋタイプ鍵および関連する情報に基づき、ファイルを署名とともに、検証のためＢｙｚａｎｔｉｎｅグループ９２６に送信することができる（処理１３１０）。Ｂｙｚａｎｔｉｎｅグループ９２６は、上述の方法のうちの１つに従って処理し、すべての複製でｌｏｃｋ−ｓｅｃｒｅｔ鍵を再構成し、それを使用してＭＡＣを検証し、委任証明書をチェックし、またはＭＡＣのベクトルを検証する。いずれにせよ、秘密鍵共有法では、秘密鍵はもはや秘密ではない。これらの方法のそれぞれにおいて、認証がチェックされる（処理１３３０）。特に、委任証明書法では、証明書のチェックが行われ、その証明書が有効であればディレクトリグループはファイルのハッシュを格納する。秘密鍵共有法では、サーバーが、ファイルのＭＡＣを検証し、ＭＡＣが正しければファイルのハッシュを格納する。ＭＡＣベクトルオーセンティケータ法では、サーバーは、ＭＡＣのベクトルを検証し、ＭＡＣベクトルが確認されればファイルのハッシュを格納する。
【０１４３】
この時点以降、この方法によれば、提供されたオーセンティケータ（証明書、共有秘密鍵、またはＭＡＣベクトル）を使用して更新されたファイルの他の検証をクライアント９１６が要求しないようにできる（処理１３４０）。つまり、これらのオーセンティケータは、１回の使用のみ有効である。したがって、再構成された後に不良複製から鍵または鍵の割り当て分が漏れても、更新のファイルハッシュがすでに複製に公開されているため、またその特定のハッシュのみを検証するため、公開された鍵によりダメージを受けることはない。たとえば、不良複製が、現在障害のあるクライアント９１６と共謀し、ファイルの破損したバージョンに対して新しいハッシュを生成しようとすると仮定する。その場合、複製にはすでにオリジナルのハッシュがあるため、ファイルのそのバージョンに対する異なるハッシュを受け付けない、つまりクライアント９１６は、Ｂｙｚａｎｔｉｎｅグループによって秘密鍵再構成が開始されるのに先立って、すでに署名済みデータをＢｙｚａｎｔｉｎｅグループ９２６に「コミット」している。この方法は、データを公開するのに先立ってデータに対するハッシュをコミットするある種の乱数発生プロトコルに似ている。
【０１４４】
図１４を参照すると、一実施形態は、選択的再生攻撃を防止するため検証を使用することを対象とする。特に、秘密鍵共有のそれぞれにおけるオーセンティケータ、オーセンティケータと委任証明書実施形態は、特定のファイルの内容の認証を行う。したがって、クラッシュしてから、ログをディレクトリグループに対して再生するのに先立ってマシンが破損した場合、攻撃者はディレクトリグループに送信する更新および無視する更新を選ぶことが可能になる。
【０１４５】
たとえば、３つのファイルＦ１、Ｆ２、およびＦ３を更新しているマシンを考える。ユーザーは、まずＦ１を書き込み、次にＦ２、そして最後にＦ３を書き込む。クライアントマシンは、これらの書き込みをファイルに適用し、この３つの新しいファイル（上述の実施形態で生成された）に対してオーセンティケータＡ１、Ａ２、Ａ３を生成し、ログに格納する。その後クライアントマシンがクラッシュし、再起動に先立って破損している場合、攻撃者は有効なオーセンティケータとともに３つのファイルの更新バージョンを見つけることができる。攻撃者は、新しいオーセンティケータを作成することはできないが、ユーザーがＦ１およびＦ２の後にＦ３が更新されていると確信していたとしても、Ｆ１またはＦ２なしのＦ３のみの変更をディレクトリグループに報告することができる。
【０１４６】
このような攻撃を防御するため、図１４を参照して一実施形態を説明する。まず、特定の更新されたファイルだけでなく、ログ内のその時点までの更新のシリーズ全体について生成オーセンティケータを構成する（処理１４１０）。上の例では、ディレクトリグループはＡ１を計算し、次にＡ１、２、次にＡ１、２、３と計算し、ファイル１までの更新を認証し、その後、ファイル１と２の両方に対する更新、最後に３つすべての更新を認証する。クライアントマシンが破損した場合、マシンはこれら３つのオーセンティケータの１つを自由に送り返すことができるが、マシンは、ファイル３が更新されたが、ファイル１と２は更新されていないということをディレクトリグループに納得させることができない。したがって、ディレクトリグループはログ内のファイルの順序をチェックする（処理１４２０）。
【０１４７】
上述の３つの実施形態はすべて、何らかのデータ上の電子署名、たとえば、Ａ（データ）などの「署名」関数の形を取る。ユーザーが新しいログを開始し、ディレクトリグループが第１の更新を受け取った場合、第１のファイルに対する変更を認証することは、Ａ（ｈ（Ｆ１））と表すことができる。ファイル内容ハッシュは、データだけでなく、ファイルＩＤを含むメタデータについても計算される。したがって、一方のファイルのオーセンティケータを使用して他のファイルの内容を変更することはできない。第２のファイルが更新された場合、ディレクトリグループはＡ（ｈ（ｈ（Ｆ１）；ｈ（Ｆ２）））を生成する。特に、ディレクトリグループは、第１のファイルの内容ハッシュを第２のファイルの内容ハッシュと連結し、まとめてハッシュし、その結果を認証する。第３のファイルについては、ディレクトリグループはＡ（ｈ（ｈ（ｈ（Ｆ１）；ｈ（Ｆ２））；ｈ（Ｆ３）））を生成する。したがって、ディレクトリグループはメモリ内の付加された１つのハッシュを追跡し、それを新規更新されたファイル内容とともにハッシュしてから、新しいオーセンティケータを計算する。
【０１４８】
一実施形態では、ディレクトリグループはファイル内容の変更と、さらに解除されたロック、アクセス制御リストに対する変更、ファイルの名前変更／削除などの他のオペレーションを含む特定のグループに対する更新の単一ログを構築する。最終的に、ユーザーは、ディレクトリグループにまで遡る他のオペレーションを含めたログをアップロードし、更新をディレクトリ情報のグループのコピーに適用する。この統合ログ内のエントリでは、上述の方法の１つを使用してオーセンティケータを構成しており、したがって、クラッシュした後、安全にアップロードすることができる。クラッシュまたはログアウトに先立ってログをアップロードする場合、クライアントは新しいログ（前にアップロードしたログの内容を含まない）に対して新しいオーセンティケータを開始することができるが、それは、クライアントがもはや第１のログが存在していないことをディレクトリグループに納得させることができないからである。
【０１４９】
秘密鍵共有およびオーセンティケータ法のコスト
秘密鍵共有法とＭＡＣベクトルオーセンティケータ法の違いはシステム要件によって決まる。特に、ＭをＳＨＡ−１ハッシュのＭＡＣを生成する時間とし、ＳＳＧを秘密ロック鍵の割り当て分を生成して複製に送信する時間とし、ＳＳＲを割り当て分から秘密ロック鍵を再構成する時間とする。他のパラメータとしては、クライアントがログアウトするまでのディスクへの遅延書き込みの平均数Ｗに対するＢｙｚａｎｔｉｎｅグループが許容するフォールトの数ｆおよびリカバリ数と書き込み数との比Ｒがある。
【０１５０】
秘密鍵共有の実施形態では、Ｂｙｚａｎｔｉｎｅグループへの第１のオペレーションがユーザーに代わって実行された場合にクライアントマシン上のユーザーが秘密ロック鍵の割り当て分を生成する必要があるが、ＳＳＧ秒かかる。遅延書き込みのクリティカルパスでは、この実施形態によりＭＡＣの計算が付加され、これはＭ秒を要する。復旧時に、ファイルハッシュの妥当性確認に先立って複製により鍵が再構成されるが、これはＳＳＲ秒を要する。
【０１５１】
オーセンティケータベースの実施形態では、ユーザーが最初にＢｙｚａｎｔｉｎｅグループメンバーと通信する場合に対称セッション鍵を生成する必要がある場合がある。これらの鍵を生成するコストは小さく、これらの鍵をクライアントマシンとディレクトリグループ内の複製との間の既存のセキュアチャネルで送信することができる。遅延ファイル書き込みのクリティカルパスでは、オーセンティケータベースの実施形態は、３ｆ＋１回のＭＡＣ計算が必要であり、オーセンティケータの生成にＭ秒を要する。実際には、ｆ＋１個の正しい複製を納得させ、これらの複製はさらに他の複製を納得させることができるため、２ｆ＋１回の暗号化で十分である。復旧時に、各複製はその対称鍵を使用して、ファイルハッシュの妥当性を確認し、これにＭ秒を要するが、余分な再構成作業は行われない。
【０１５２】
秘密鍵分割実施形態では、ユーザーが最初にＢｙｚａｎｔｉｎｅグループとコンタクトを取る際に前払いコストを支払い、さらに、クラッシュに先立ってディレクトリグループに更新をアップロードしていなかったファイルにクラッシュが発生した場合に、再構成コストペナルティを支払う。しかし、秘密鍵分割実施形態は、クリティカルパスではコストが低い。ページ修正がログに書き込まれた場合、秘密鍵共有アプローチでは、ファイルハッシュを計算し、ハッシュのＭＡＣを計算する必要がある。ＭＡＣベクトルベースの実施形態では、ファイルハッシュを計算し、ハッシュの２ｆ＋１個のＭＡＣ（つまり、ｆ＝３で７つのＭＡＣ）を計算する必要がある。したがって、秘密鍵共有ベースのスキームのコストはＣＳＳ＝ＳＳＧ＋Ｗ＊Ｍ＋Ｗ＊Ｒ＊ＳＳＲとなる。  
したがって、オーセンティケータベースのスキームのコストはＣＡ＝Ｗ＊（２ｆ＋１）＊Ｍ＋Ｗ＊Ｒ＊Ｍとなる。
【０１５３】
損益分岐点は、Ｗ＝ＳＳＧ／（２ｆ＊Ｍ＋Ｒ（Ｍ−ＳＳＲ））に対応する。
したがって、トレードオフの関係は、ロック秘密鍵の割り当て分の生成、ＲＳＡを使用したハッシュの署名、ハッシュのＭＡＣの計算、および割り当て分からの秘密鍵の再構成の相対的コストによって決まる。
【０１５４】
これらの実施形態ではＲＣ２を１２８ビット鍵とともに使用して、１ＧＨｚのＰｅｎｔｉｕｍ（登録商標）でＭＡＣを計算すると仮定している場合、ＭＡＣの計算にＭ＝８μｓを要する。ｆ＝３およびＲ＝０とし、秘密鍵共有スキームではファイルキャッシュからディスクへの書き込みのクリティカルパスでＭＡＣ計算を１回実行すると仮定すると、オーセンティケータベースのアプローチだと、約５６μｓのコストに対して７回の等価ＭＡＣ計算を実行することになる。したがって、クリティカルパスの待ち時間に関して、スキームは両方とも、ディスク書き込み待ち時間（６〜８ｍｓ）とファイルのハッシュを計算する時間に比べて時間のオーバーヘッドがごく小さい。
【０１５５】
秘密鍵共有アプローチでは、約２４バイトの１つのデータレコードをログに記録しなければならないが、オーセンティケータベースの実施形態では、７個のレコード（１６８バイト）をログに記録しなければならない。オーセンティケータベースのアプローチにおけるバイトオーバーヘッドは高いが、１６８バイトという絶対値は非常に低い。このオーバーヘッドは、ディレクトリグループに対してまだハッシュがフラッシュされていない、修正済みのファイルのみである。
【０１５６】
１２８ビットのロック秘密鍵の１０個の割り当て分を生成するＳＳＧは１．５ｍｓ［１］であり、署名を生成する時間は６．５ｍｓであると仮定すると、損益分岐点はＷ＝３１である。
【０１５７】
たとえば、ＭＡＣ計算では、ＨＭＡＣ−ＳＨＡ１の計算はＰＩＩＩ  １ＧＨｚで約２μｓのコストがかかり、したがって、増益分岐点はＷ＝１２５となる。おそらくセキュリティ保護されているＭＡＣ構成であるＵＭＡＣ２／８を使用すると、ＰＩＩＩ  Ｋａｔｍａｉ  ６００ＭＨｚで３２バイトについてＭＡＣを生成するコストは０．６２μｓであり、損益分岐点はＷ＝４０３となる。このメッセージサイズでは、ＵＭＡＣはＣＢＣモードでＲＣ６を使用してＭＡＣを計算する。ＵＭＡＣ２／８は、当面すべての複製に再利用できる８バイトと、複製毎に用意される８バイトタグを持つ。したがって、合計６４バイトをログに記録するが、秘密鍵共有実施形態よりもわずか４８バイト多いだけである。
【０１５８】
復旧後、秘密鍵分割実施形態とオーセンティケータベースの実施形態は両方とも、該当するデータすべてをサーバーすべてに伝送する。送出される量は両方のスキームで等しいが、秘密鍵分割実施形態では、同じレコードを全員に送信し、オーセンティケータベースのスキームでは、異なるがサイズは等しいレコードを全員に送信する。前者は１０台のサーバーのそれぞれにおいて秘密鍵を解読する必要がある。１０／７の数については、コストは２５〜３０ｍｓの間であり、おそらく１０／４についてはより小さいであろう。オーセンティケータベースの実施形態では、各サーバーでファイルハッシュについてＭＡＣを計算する必要がある。  
したがって、Ｒ＝１ｅ−４とし、ＨＭＡＣ−ＳＨＡ１を使用して復旧を考慮すると、損益分岐点はＷ＝１５８となる。これは、Ｒ＝１ｅ−５でＷ＝１２８である。
【０１５９】
本質的に、秘密鍵分割実施形態のセットアップおよび復旧の計算オーバーヘッドと、主流の非キャッシュ書き込み経路におけるオーセンティケータベーススキームの計算オーバーヘッドは釣り合っている。増益分岐点は、ＭＡＣ計算と秘密鍵共有に使用される技術によって変化し、また同じロック秘密鍵で認証された書き込みの回数および復旧から復旧までの間の書き込みの回数によっても異なる。
【０１６０】
結論
上の説明では構造的機能および／または方法論的ステップに固有の言語を使用しているが、付属の請求項で定められている発明は、説明した特定の機能またはステップに限られていないことは理解されるであろう。むしろ、特定の機能およびステップは請求されている発明を実施する例として開示されている。
【符号の説明】
【０１６１】
１００  ネットワーク環境
１０２  デバイス
１０４  デバイス
１０６  デバイス
１０８  コンピューティングデバイス
１１０  ネットワーク
１２０  分散システム部分
１２２  ローカル部分
１２４  分散システム部分
１２６  ローカル部分
１２８  分散システム部分
１３０  ローカル部分
１３２  ローカル部分
１５０  分散ファイルシステム
２００  コンピューティングデバイス
２０２  サーバーコンポーネント
２０４  クライアントコンポーネント
２０６  メモリ
２０８  大容量ストレージ
２１０  分散ファイルシステムインターフェイス
２２０  制御モジュール
２２２  ディレクトリグループ検索モジュール
２２６  ファイル暗号化モジュール
２２８  ディレクトリ暗号化モジュール
２４０  暗号化ファイル
２５０  分散システム制御モジュール
２５２  重複識別器
２５４  サブツリー委任モジュール
３００  コンピュータ環境
３０２  コンピュータ
３０４  処理ユニット
３０６  システムメモリ
３０８  システムバス
３１０  ランダムアクセスメモリ（ＲＡＭ）
３１２  読み取り専用メモリ（ＲＯＭ）
３１４  基本入出力システム（ＢＩＯＳ）
３１６  ハードディスクドライブ
３２０  取り外し可能な不揮発性磁気ディスク
３１８  磁気ディスクドライブ
３２４  取り外し可能な不揮発性光ディスク
３２６  データ媒体インターフェイス
３２８  プログラム
３３０  プログラムモジュール
３３２  プログラムデータ
３３４  キーボード
３３６  ポインティングデバイス
３３８  入力デバイス
３４０  入出力インターフェイス
３４２  モニタ
３４６  プリンタ
３４８  リモートコンピューティングデバイス
３５０  ローカルエリアネットワーク（ＬＡＮ）
３５２  ワイドエリアネットワーク（ＷＡＮ）
３５４  ネットワークインターフェイスまたはアダプタ
３５６  モデム
３５８  リモートアプリケーションプログラム
４００  名前空間
４０２  ディレクトリグループ
４０４  ディレクトリグループ
４０６  ディレクトリグループ
４０８  ディレクトリグループ
４１０  ディレクトリグループ
５００  ファイルシステム
５０２、５０４、５０６、５０８、５１０、５１２、５１４、５１６、５１８、５２０、５２２、５２４  コンピュータ
５２６  Ｂｙｚａｎｔｉｎｅグループ
５２８  ファイル
５３０  ディレクトリエントリ
７１０  ファイル
７２０  委任証明書
７５０  複製
９００  ファイルシステム
９０２、９０４、９０６、９０８、９１０、９１２、９１４  ７台のコンピュータ
９１６  クライアントコンピュータ
９１８  更新
９２６  Ｂｙｚａｎｔｉｎｅ−ｆａｕｌｔ−ｔｏｌｅｒａｎｔグループ
９３０  ディレクトリエントリ
【図１】
2011008818.tif 000006
【図２】
2011008818.tif 000007
【図３】
2011008818.tif 000008
【図４】
2011008818.tif 000009
【図５】
2011008818.tif 000010
【図６】
2011008818.tif 000011
【図７】
2011008818.tif 000012
【図８】
2011008818.tif 000013
【図９】
2011008818.tif 000014
【図１０】
2011008818.tif 000015
【図１１】
2011008818.tif 000016
【図１２】
2011008818.tif 000017
【図１３】
2011008818.tif 000018
【図１４】
2011008818.tif 000019