(57)【要約】  ２つの事象間の因果的関係は、第１の事象が第２の事象に意味のあるように先行するときに生じ、因果モジュールによって識別される。因果モジュールは、多数のネットワーク事象を分析して、利用可能なネットワークトラフィックおよび先行物事象を評価することにより、それらの事象が因果的に関係しているかどうかを確定する。必要な記憶空間と検索動作はどちらも、ネットワーク事象の相関した因果的連鎖を追跡することによって低減される。複数の相関した因果的連鎖中の事象間の因果的関係は、ネットワーク事象空間を事象部分空間に区分することによって、そのネットワーク事象空間内に維持される。このようにして、同じ事象部分空間を共用する事象は、その区分部分空間がほぼ因果的に一貫している限り、一定のままとなる。隣り合う異なる部分空間からの事象の因果は、共用される境界事象の結合が可能になるまで各照会事象に対して個別の部分空間を確定することによって、確定され得る。【特許請求の範囲】
【請求項１】
事象空間の事象部分空間の複数の境界事象の発生に関連するデータを受け取るための通信インターフェースと、
前記通信インターフェースに結合され、事象の因果を、前記事象がメンバである前記事象部分空間の前記１つまたは複数の境界事象との前記事象の因果的関係に、少なくとも一部基づいて確定するように構成される因果モジュールと
を備える装置。
【請求項２】
前記因果モジュールが、前記境界事象がメンバである前記事象部分空間に少なくとも一部基づいて、前記境界事象の因果に関連するデータを維持するように構成される、請求項１に記載の装置。
【請求項３】
前記因果モジュールが、前記境界事象の因果に関連する前記データを、前記事象部分空間に関連する１つまたは複数の表中に維持するように構成される、請求項２に記載の装置。
【請求項４】
前記１つまたは複数の表が、リンク表、チャンク割振り表、ハッシュ表、および連鎖索引表からなる前記群から選択された１つまたは複数のタイプである、請求項３に記載の装置。
【請求項５】
前記因果モジュールが、前記境界事象の因果に関連する前記データを、前記事象部分空間に関連する１つまたは複数の混合カウンタ中に維持するように構成される、請求項２に記載の装置。
【請求項６】
前記１つまたは複数の混合カウンタが、２値混合カウンタおよび３値混合カウンタからなる前記群から選択された１つまたは複数のタイプである、請求項５に記載の装置。
【請求項７】
前記因果モジュールが、前記事象部分空間の前記境界事象に対する因果タグを記憶することを含む休眠フェーズを有するマルチフェーズ記憶を使用する前記事象部分空間の前記境界事象の因果に関連する前記データを維持するように構成される、請求項１に記載の装置。
【請求項８】
前記マルチフェーズ記憶が、前記事象部分空間の非境界事象に対する因果タグを構築することを含むアクティブフェーズをさらに有する、請求項７に記載の装置。
【請求項９】
前記因果モジュールが、前記事象と、前記１つまたは複数の境界事象との間の因果的関係を確定するように構成される、請求項１に記載の装置。
【請求項１０】
前記因果モジュールが、前記事象部分空間の前記１つまたは複数の境界事象と、前記事象空間の少なくとも１つの他の事象部分空間の１つまたは複数の他の境界事象との間の因果的関係を確定するように構成される、請求項１に記載の装置。
【請求項１１】
前記因果モジュールが、事象因果を確定する目的で、前記複数の境界事象の発生に関連するすべての前記受取りデータよりも小さいデータを維持するように構成される、請求項１に記載の装置。
【請求項１２】
前記因果モジュールが、前記事象空間を階層分割事象空間に区分するように構成される、請求項１に記載の装置。
【請求項１３】
前記因果モジュールが、因果表なしで因果を確定するように構成される、請求項１２に記載の装置。
【請求項１４】
複数の事象の発生に関連するデータを受け取るための通信インターフェースと、
前記通信インターフェースに結合され、事象の因果を、前記事象の、因果連鎖に編成される他の事象との因果的関係に少なくとも一部基づいて確定するように構成される因果モジュールと
を備える装置。
【請求項１５】
因果連鎖のうちの少なくとも１つが、ネットワークの装置に関連する、請求項１４に記載の装置。
【請求項１６】
デスクトップコンピュータ、サーバ、ルータ、スイッチ、およびファイアウォールからなる前記群から選択された、請求項１５に記載の装置。
【請求項１７】
前記因果モジュールが、因果連鎖に編成される前記複数の事象の発生に関連するすべての前記受取りデータよりも小さいデータを維持するようにさらに構成される、請求項１４に記載の装置。
【請求項１８】
前記因果モジュールが、事象に対して、前記様々な因果連鎖中に直接的先行物事象が配置された因果的関係データを記憶するようにさらに構成される、請求項１７に記載の装置。
【請求項１９】
前記因果モジュールが、前記因果的関係データを１つまたは複数の表中に記憶するようにさらに構成される、請求項１７に記載の装置。
【請求項２０】
前記１つまたは複数の表が、リンク表、チャンク割振り表、ハッシュ表、および連鎖索引表からなる前記群から選択された１つまたは複数のタイプである、請求項１９に記載の装置。
【請求項２１】
前記因果モジュールが、因果的関係データを１つまたは複数の混合カウンタ中に記憶するようにさらに構成される、請求項１７に記載の装置。
【請求項２２】
前記混合カウンタが、２値混合カウンタおよび３値混合カウンタからなる前記群から選択された１つまたは複数のタイプである、請求項２１に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、２００５年６月２７日にどちらも出願された「ＤＥＴＥＲＭＩＮＩＮＧ  ＥＶＥＮＴ  ＣＡＵＳＡＬＩＴＹ  ＩＮＣＬＵＤＩＮＧ  ＥＭＰＬＹＭＥＮＴ  ＯＦ  ＣＡＵＳＡＬ  ＣＨＡＩＮＳ」および「ＤＥＴＥＲＭＩＮＩＮＧ  ＥＶＥＮＴ  ＣＡＵＳＡＬＩＴＹ  ＩＮＣＬＵＤＩＮＧ  ＥＭＰＬＯＹＭＥＮＴ  ＯＦ  ＰＡＲＴＩＯＮＥＤ  ＥＶＥＮＴ  ＳＰＡＣＥ」と題する米国特許出願、ならびに２００４年６月２８日に出願された米国仮特許出願第６０／５８３，４５５号による優先権の利益を主張する。
【０００２】
本発明の実施形態は、データ処理およびデータ通信の分野に関する。より詳細には、本発明の実施形態は、ネットワーキング環境での事象因果を確定する（またはその確定を可能にする）ための、かつ／あるいはその確定を使用する（またはその使用を可能にする）ための方法および機器に関する。
【背景技術】
【０００３】
多くの問題が、事象間の因果の理解および／または確定を必要とする。そのような理解および／または確定を必要とする例示的な技術問題としては、現代のネットワークの管理がある。半導体、プロセッサ、および関連技術の進歩により、広範な汎用および専用コンピューティング装置をどこでも利用可能になった。さらに、電気通信、ネットワーキング、および関連技術の進歩により、こうしたコンピューティング装置間の接続性が向上した。事象の因果を理解すれば、こうしたますます多様になるネットワークを、より効率的かつ効果的に管理できるようになり得る。
【発明の開示】
【課題を解決するための手段】
【０００４】
本発明について、添付の図面に示されている例示的な実施形態を挙げて説明するが、それだけには限定されない。添付の図面において、同様の参照番号は、類似の要素を示す。
【発明を実施するための最良の形態】
【０００５】
本発明の実施形態は、それだけには限らないが、因果的連鎖および／または区分事象空間を使用する、特に、ネットワーク環境において、複数の事象から導出される事象因果を確定するために装備される機器またはシステムを含む。
【０００６】
以下の詳細な説明では、本明細書の一部を形成する添付の図面を参照する。そこでは、全体を通して同様の番号は同様の部品を示しており、例として、本発明を実施することが可能な特定の実施形態が示されている。本発明の範囲から逸脱することなく、他の実施形態を使用することも可能であり、構造的または論理的変更を行うことも可能であることを理解されたい。したがって、以下の詳細な説明は、限定的な意味にとられるべきではなく、本発明の範囲は、添付の特許請求の範囲およびそれらの均等物によって定義される。
【０００７】
以下の説明では、様々な実施形態について、理解を容易にするために、一部詳細についても説明することにする。説明のために、具体的な数、材料、および構成について述べる。しかし、具体的な詳細なしでも、代替実施形態を実施することが可能であることが、当業者には明らかであろう。こうした実施形態がわかりにくくならないように、よく知られた特徴が省略または簡略化されている場合もある。
【０００８】
説明の一部は、一般に当業者が自分たちの仕事の本質を他の当業者に伝えるために使用する仕方と一貫性のある、データ、事象、区画、部分空間境界などの語で提示する。当業者にはよく理解されるように、これらの量は、プロセッサおよびそのサブシステムの電気および／または光構成要素によって、維持、記憶、転送、結合、ならびにその他の方法で操作することのできる電気、磁気、ＲＦ、または光信号の形をとる。
【０００９】
以下、セクションを設けて説明する。セクションラベルの使用は、理解を容易にするためのものであり、本発明を限定するように解釈されるべきではない。様々な動作について、本発明を理解するのに非常に役に立つように、多数の個別のステップとして説明する。しかし、説明の順序は、これらの動作が必ず順序依存でなければならないことを暗示するものと解釈されるべきではない。特に、これらの動作は、提示された順序で実施される必要はない。
【００１０】
本明細書中の「一実施形態（ｏｎｅ  ｅｍｂｏｄｉｍｅｎｔ）」または「実施形態（ａｎ  ｅｍｂｏｄｉｍｅｎｔ）」の言及は、実施形態に関連して記述される特定の特徴、構造、または特性が、本発明の少なくとも１つの実施形態に含まれることを意味する。本明細書中の様々な場所での「一実施形態では（ｉｎ  ｏｎｅ  ｅｍｂｏｄｉｍｅｎｔ）」または「実施形態では（ｉｎ  ａｎ  ｅｍｂｏｄｉｍｅｎｔ）」という語句の出現は、必ずしもすべて同じ実施形態を指すわけではないが、そうであることもある。「備える（ｃｏｍｐｒｉｓｉｎｇ）」、「有する（ｈａｖｉｎｇ）」、および「含む（ｉｎｃｌｕｄｉｎｇ）」という語は、文脈がそうでないことを求めない限り、同義語とみなされるべきである。また、これらの語句のどの使用も、記述される特定の特徴、構造、または特性が、そのような記述が含まれるすべての実施形態に必要な構成要素であると、暗示または指示するべきではない。
【００１１】
コンピューティング環境の概要
次に、図１を参照すると、様々な実施形態による、コンピューティング環境１００を示すブロック図が示されている。前に触れたように、本発明は、主にネットワーク管理の文脈で説明するが、それだけには限定されず、２つの事象および／または現象間の因果の理解を必要とする他の用途で実施することも可能である。
【００１２】
図示されるように、コンピューティング環境１００は、公衆ネットワーク１１４に結合される専用ネットワーク１０２を含む。より具体的には、専用ネットワーク１０２は、互いに結合され、かつ図示されている公衆ネットワーク１１４に結合される、いくつかのアプリケーションサーバ１０４、ユーザコンピュータ１０６、およびゲートウェイ１０８を含む。さらに、専用ネットワーク１０２は、互いに結合され、かつ図示されている前に列挙された要素に結合される、センサ１１０およびネットワーク管理サーバ１１２も含む。様々な実施形態では、公衆ネットワーク１１４は、インターネットを含んでもよい。
【００１３】
センサ１１０は、ネットワークトラフィックを監視し、広範な事象の発生を検出し報告するために使用され、一方、管理サーバ１１２は、センサ１１０によって検出され報告される事象に少なくとも一部基づく専用ネットワーク１０２を管理するために配備される。具体的には、管理サーバ１１２のうちの少なくとも１つは、相関した事象連鎖の事象の発生に関連するデータを受け取るための通信インターフェースと、因果を確定し、検出／報告された事象を関連付け、専用ネットワーク１０２の管理を容易にするために、本発明の因果ロジックの実施形態での、その先行物事象の記録を維持するための因果モジュールとを備えている。この文脈において本発明で使用される「事象」という語は、検出され、監視され、かつ／または報告され得る、事実上すべての発生および出来事を広く含む。
【００１４】
因果的関係分析機能によって、本発明の実施形態は特に、大きなネットワークを管理するのに適している。しかし、本発明の実施形態はまた、中小ネットワークにも適しており、それらを管理するために配備されてもよい。したがって、専用ネットワーク１０２のサイズに応じて、ネットワークトラフィックのボリューム、および／または事象の数に即して、１つまたは複数のセンサ１１０を使用して、事象の発生を検出し報告してもよい。同様に、管理サーバ１１２は、ネットワークを管理するために使用されてもよい。
【００１５】
代替実施形態では、いくつかのまたはすべてのセンサ１１０は、管理サーバ１１２と組み合わせてもよい。あるいは、管理サーバ１１２を使用して、多数のネットワークを管理することもできる。さらに他の実施形態では、アプリケーションサーバ１０４のいくつかまたはすべてを、管理サーバ１１２と組み合わせてもよい。同様にいくつかのまたはすべてのユーザコンピュータは、アプリケーションおよび／または管理サーバ１０４／１１２と組み合わせてもよい。
【００１６】
管理サーバ１１２のうちの少なくとも１つに提供される因果モジュールに含まれる因果的関係分析ロジックを除き、図１の列挙された要素は普通、当技術分野で知られている広範な対応する要素を表す。したがって、コンピューティング環境１００は、任意の数のアプリケーションサーバ、センサ、管理サーバ、ユーザコンピュータ、ゲートウェイなどを含んでもよい。本発明の実施形態は、複数のネットワーク装置要素を含んでもよい。ただし、それらの要素が全体としてサポートすべき、その結果生じるユーザ数および使用を扱うためのリソースを、それらの要素が適切に備えることを条件とする。
【００１７】
ネットワーク管理サーバ
図２は、様々な実施形態による、ネットワーク管理サーバ１１２としての使用に適したコンピューティング装置２００のブロック図を示す。図示されるように、コンピューティング装置２００は、１つまたは複数のプロセッサ２０２、システムメモリ２０４、大容量記憶装置２０６、入出力装置２０８、および通信インターフェース２１０を含む。例示的な大容量記憶装置２０６は、ディスケット、ハードドライブ、ＣＤ−ＲＯＭ、ＤＶＤなどを含む。例示的な入出力装置２０８は、キーボード、カーソル制御などを含む。また、例示的な通信インターフェース２１０は、ネットワークインターフェースカード、モデムなどを含む。要素２０２〜２１０は、１つまたは複数のバスを表し得るシステムバス２１２を介して互いに結合される。多数のバスのケースでは、それらのバスは、１つまたは複数のバスブリッジ（図示せず）によってブリッジされてもよい。
【００１８】
システムメモリ２０４および大容量記憶装置２０６は、事象因果的関係分析ロジック／モジュール２２４を含むネットワーク管理ソフトウェア２２２を実装したプログラミング命令の、作業コピーおよび永続コピー（図示せず）を維持および／または記憶するために使用される。プログラミング命令の永続コピーは、たとえば、配布媒体（図示せず）によって、または配布サーバ（図示せず）から通信インターフェース２１０を介して、工場で、または現場で、大容量記憶装置２０６にロードされてもよい。
【００１９】
ネットワーク管理ソフトウェア２２２、具体的には、因果的関係分析ロジック／モジュール２２２を除き、要素２０２〜２１２の構成および機能が一般に知られており、したがって、それらについてこれ以上説明しない。
【００２０】
ネットワーク管理
様々な実施形態では、ネットワーク管理ソフトウェア２２２は、ネットワークトラフィックを分析することにより、専用ネットワーク１０２における事象の発生の因果的関係を計算し追跡することが可能になるように適合される。因果モジュール２２４中の因果的関係分析ロジックは、計算パワーおよび／または記憶空間が制約され得るが、ネットワーク管理ソフトウェア２２２が、ネットワーク１０２中で生じるすべてのまたは選択されたトラフィックに対して分析を効率的に実施するのを可能にする。特に、様々な実施形態では、ネットワーク管理ソフトウェア２２２は、顕著に異常な挙動の間の因果的関係を確立し、普通なら隠れていたであろう微妙な違いを検出することが可能である。「異常な挙動」および／または「微妙な違い」は、アプリケーション依存である。以下の説明から明らかになるであろうように、特定アプリケーションの「異常な挙動」および／または「微妙な違い」の性質は、分析の構成および／または分析の使用によって反映されてもよい。
【００２１】
たとえば、一実施形態では、１つまたは複数のセンサ１１０は、コンピュータ１０６および／またはサーバ１０４の間の接続、それらの接続タイプ、ならびに転送されるデータの量を追跡するように割り振られてもよい。次に、センサ１１０のうちの１つまたは複数が、第１のコンピュータ１０６から大量のデータを転送する財務ファイルサーバ１０４への接続を検出することが可能であり、かつ、しばらくして、第１のコンピュータ１０６と第２のコンピュータ１０６の間の別の接続が、大量のデータの別の転送を行うと仮定する。最後に、第２のコンピュータ１０６と、同様に大きなデータ転送を行うインターネットベースの不満のある従業員ウェブサイトとの間の接続が、検出される。これらの報告された検出から、管理サーバ１１２は、１人または複数の従業員が、何らかの量の財務データを不満のある従業員ウェブサイトに転送した可能性があると推論してもよい。管理サーバ１１２は、転送された実際のデータの直接的洞察を有していないかもしれないが、それらの事象は、より詳しい調査を求めるアラートの発行を正当化する。
【００２２】
因果的粒度
様々な実施形態では、後続の計算に価値のあり得る直接的因果的関係が、異なるレベルの粒度を使用して、選択的に確定されてもよい。したがって、たとえば、特定のネットワーク管理サーバ１２２が利用可能な情報に応じて、ネットワーク上の特定のコンピュータおよび／または通信に即して、因果的関係が、選択的に確定されてもよい。たとえば、一実施形態では、どのようにして特定のサーバ上で動作するプロセスがファイルシステムを改変し、または共有メモリを介して相互作用するかに関する情報を、ネットワーク管理サーバ１２２が有さない場合、管理サーバ１２２は、そのサーバ上で生じるすべての事象は因果的に関係していると仮定してもよい。
【００２３】
因果的連鎖の適用
様々な実施形態では、分析量を簡略化し低減させるために、ネットワーク管理サーバ１２２は、因果的連鎖を使用し、その因果的連鎖を１つまたは複数の認識可能な実体に関連付けてもよい。例示的な認識可能な実体は、ワークステーション、プロセス、サーバなどを含む。一実施形態では、いくつかの実体が、考慮から除外されてもよい。それらが生成するいくつかの事象は、局所的に因果的に独立とみなされてもよいからである。こうした除外される実体のいくつかの例には、ファイアウォール、ルータ、スイッチ、ハブなどが含まれる。一実施形態では、ネットワーク管理サーバ１２２は、ファイアウォール上の２つの事象を必ずしも因果的に独立であると自動的にはみなさず、むしろネットワーク管理サーバ１２２はさらに、観察される両事象がネットワークの他の部分に対して有する効果を観察することによって、因果を確定する。
【００２４】
記憶手法
様々な実施形態では、因果的関係を計算するのに使用される各ネットワーク管理サーバ１２２は、相対的に非常に大きいが相対的に遅いハードドライブと、相対的に小さいが相対的に非常に高速な物理メモリバンクとを備える。その構成により、因果的関係分析に対する２フェーズ手法が容易になり、その場合、その分析の一方のフェーズは、一方のタイプの記憶の大きなサイズを活用し、その分析の他方のフェーズは、他方のタイプの記憶の速度を活用する。しかし、一実施形態では、ネットワーク管理サーバ１２２は、その限定されたサイズの故に、第１のフェーズの記憶にはメモリを使用し、その限定された速度の故に、第２のフェーズの記憶にはハードドライブを使用してもよい。
【００２５】
様々な実施形態では、因果的関係分析は、事象部分空間またはセルという概念を使用し、少数の部分空間またはセル内の事象を検索することを伴ってもよい。したがって、速度のためには、部分空間またはセルの事象が、物理的メモリに維持および／または記憶されてもよい。一実施形態では、因果的関係分析は、まれに参照される多数の部分空間またはセル内の検索事象を伴ってもよい。したがって、そのデータは、長期間アーカイブされ、これらの部分空間またはセル内の事象は、ハードドライブの記憶空間に記憶されることになる。しかし、一実施形態では、キャッシング機構が使用され、それによって頻繁に必要とされない部分空間またはセルに関連する事象が、物理的メモリからフラッシュされ、新しい計算に必要とされる部分空間またはセルに関連する事象が、ハードドライブからインポートされる。この方式の下では、ディスク上と同じだけ多くの空間を物理的メモリ中に保全する必要はなく、またディスクに、それ程大きな性能を要求する必要もない。したがって、その実施形態では、ディスクを第１のフェーズの記憶装置として示し、空間のためにそこに記憶される部分空間またはセルに関連する事象を２重に最適化し、物理メモリを第２のフェーズの記憶装置として示し、速度のためにそこに記憶される部分空間またはセルに関連する事象を２重に最適化する。
【００２６】
因果的関係分析序論
本願では、因果的関係とは、２つの事象ａおよびｂの間の関係であり、それは、ａが意味のあるようにｂに先行したことを示す。これにより、本発明者らは、ａがｂより早い時点で発生しただけでなく、ｂをもたらした事象の連鎖の一部であったことを意味する。因果的関係は、推移的かつ非反射的である。言い換えれば、ａ〜＞ｂおよびｂ〜＞ｃは、ａ〜＞ｃであり、ｂ〜／＞ａであることを暗示する。因果的関係はまた、２つの事象ａおよびｂの間の直接的因果的関係（→）の推移閉包であり、それは、ａがｂに先行しただけでなく、ａとｂの間に中間事象がなかったことを示す。
【００２７】
様々な実施形態では、直接的因果的関係の維持は、各事象が直接的因果的先行物に戻るポインタを有することによってもたらされる。２つの事象が因果的に関係しているかどうかを迅速に確定するために、この関係の推移閉包の要約が維持される。
【００２８】
一般に、これは、時間がかかり（Ｏ（ｎ３）、ただしＯは実行される演算数、ｎは追跡される事象数）、空間を消費する（Ｏ（ｎ２）、事象を記憶するのに必要な空間以外）可能性がある。推移要約を維持することの代替方法は、直接的因果的関係を検索して、１つの事象が推移的に別の事象（１照会あたりＯ（ｎ）、可能な照会数ｎ２）をもたらすかどうかを、突き止めることである。以下では、通信挙動における共通性を活用するための一連の技法について説明するが、それらにより、推移要約を維持および／または記憶するのに必要な空間、ならびにそれを計算するのに必要な時間が、著しく低減し得る。
【００２９】
次に図３、４、および６〜１６に移ると、様々な実施形態の個々の方法が、因果グラフに即して、動作機構について記載されている。因果モジュールによって実行されるべき方法および技法が、コンピューティング装置またはネットワーク管理サーバ１２２などのコンピュータ制御ネットワーク装置によって実行される動作プログラムを構成する。グラフ表現に即して因果モジュールの動作方法を説明することで、適切に構成されたネットワーク装置（因果管理サーバ、ユーザコンピュータ、サーバ、ゲートウェイ、センサなど）上でそれらの方法を実行するための命令を含む、そのような動作プログラムを、当業者が開発することが可能になる。
【００３０】
これらの動作は、コンピュータ制御装置中で行われてもよく、またはネットワーク装置中で実施されてもよい。公認の標準に準拠するプログラミング言語で書かれた場合、そのような命令は、様々なハードウェアプラットフォーム上で、また、様々なオペレーティングシステムに対するインターフェース向けに、実行することができる。実施形態によっては、これらの方法のすべてまたは一部が、ファームウェアによって実装されてもよい。さらに他の実施形態では、これらの方法のすべてまたは一部が、ハードウェアに実装されてもよい。
【００３１】
様々な装置および方法を使用して、本明細書に記載されるネットワーク向けの因果管理システムを実装してもよいことが理解されよう。さらに、動作という語を、（たとえば、プログラム、プロシージャ、プロセス、アプリケーションなど）何らかの形で、アクションをとることまたは結果をもたらすこととして用いることが、当技術分野では一般的である。そのような表現は単に、装置が動作を実行すると、管理システムの因果モジュールがアクションを行い、または結果を生み出すことを言う、省略表現法である。
【００３２】
因果問題
様々な実施形態では、事象および事象関連の因果的関係を確定する因果問題は、すべての事象の直接的因果的関係を表す因果グラフによって表されてもよい。因果問題は、２つの事象が因果的に関係しているかどうかを確定することである。言い換えれば、２つの事象について、直接的因果グラフ中にそれらの間の経路が存在するかどうかを確定する。
【００３３】
図３は、中間事象ｂ、ｃ、およびｄを介して因果的に関係している２つの事象ａおよびｅをもつ、一例を示す。したがって、直接的因果的関係のこのグラフ中に、事象ａおよびｅの間の経路が存在する。
【００３４】
このグラフは、観察者にとって関係がかなり明らかとなるのに十分なだけ小さい。しかしながら、一般に、この問題は、むしろ図２のように見え、その場合、各事象ごとの局所的情報、およびグラフまたは事象間のネットワーク上の未知の事象の雲が存在する。したがって、２つの任意の事象ａおよびｅが因果的に関係しているかどうかを確定するには、事象ａおよびｅの間に存在する事象の雲を晴らす必要がある。
【００３５】
様々な実施形態では、いくつかの手法のうちの１つまたは複数を使用して、この因果問題を解決してもよい。例示的な手法には、線形探索、明示的推移閉包、表ベースの手法のバリエーション、および混合カウンタ方法が含まれる。線形探索手法は、２つの恣意的に選ばれた事象が因果的に関係しているかどうかを確定するために、潜在的に多数の事象を調べる。明示的推移閉包方法は、比較的少数のノードに対する関係情報を記憶するために、大量の空間を必要とする可能性もある。表方法のバリエーションは、明示的推移閉包方法よりも著しく小さい記憶容量で、迅速に結果を生み出す。混合カウンタ方法は、様々な表方法よりもわずかに時間がかかって結果を生み出すが、やはり著しく小さい空間しか必要としない。
【００３６】
部分的因果
先に論じたように、事象が生じる時点を単に知るだけでは、因果的順序を確定するのに不十分である。たとえば、互いに異なる時点で発生した事象は、まだ因果的に独立であり得る。しかし、１つの事象が別の事象よりも早い時点で生じたことを知ることで、第２の事象が、第１の事象の因果的先行物ではあり得ないことがわかる。その結果、因果方程式の一部を、単純なタイムスタンプに基づいて非常に迅速に計算し、それらのタイムスタンプがどのように互いに関係するかを確認することが、しばしば可能である。たとえば、すべてのタイムスタンプが厳密に正確であると仮定されるならば、ｂがａよりも後のタイムスタンプを有するような２つの事象ａおよびｂが与えられた場合、ｂ〜＞ａを可能性として除外することができる。
【００３７】
線形探索手法
様々な実施形態では、線形探索手法は、２つの事象のうちの一方で開始し、他方の事象を求めて、すべての直接的因果的リンク上を外向きに検索する。最悪のケースでは、その２つの事象間に因果的リンクが存在しないことを確定するために、既知のすべての事象を調べる必要があることがある。図５は、ａ〜＞ｂを確定するための線形探索手法を実証している。「外向き」という語は、理解しやすいように使用されている。方向的特徴付けは、本発明に関して限定するものではない。
【００３８】
部分的因果試験は、可能な場合、検索の方向を制限することができる。本発明者らの例では、本発明者らは、ｅ〜＞ａを除外することが可能であり得、したがって、ａに続きｅに先行する事象を検索するだけでよい。
【００３９】
明示的推移閉包手法
様々な実施形態では、明示的推移閉包手法は、特定の１対の事象間の経路が存在するかどうかを確定するのにかかる時間を低減させるのを助けるために、因果のグラフ表現に注釈を付加する。このケースでは、注釈は、全因果的関係、または直接的因果的関係の推移閉包を、具体的に表す縁部である。図６は、推移縁部を破線としてもつ例示的グラフの一部を示しており、ａ〜＞ｅは、単一の推移縁部として表されている。
【００４０】
これらの注釈は、因果的問題に対する答えを一定の時間で提供することができるが、注釈を計算するのにＯ（ｎ３）の時間がかかり、それらを記憶するのにＯ（ｎ２）の空間をとる。
【００４１】
表手法
様々な実施形態では、ａ〜＞ｂをほぼ一定の時間で見つけることを可能にする、因果注釈方法が使用される。この方法はまた、明示的推移閉包方法に基づいて注釈を記憶するよりも著しく小さい空間しか必要としないこともあり得る。データ構造に関するいくつかの実際的問題については、セクションの最後でより詳細に論じる。
【００４２】
実施形態では、表ベースの手法の最初の動作は、直接的因果グラフを因果的連鎖に区分することであり、その場合、因果的連鎖は、連鎖中の各事象が連鎖中の他のすべての事象に因果的に関係している、事象の不完全なシーケンスである。
【００４３】
図７は、因果的連鎖に区分された図３の因果のグラフ表現を示す。この区画は、唯一のものではない。この因果グラフを区分するための、他の、場合によってはより優れた方法が存在し得る。しかし、様々な実施形態では、これは「完全な」区画であり、すなわち、因果的連鎖のいずれもマージすることはできない。これを理解するために、連鎖ｃ２とｃ３をマージすることを考える。事象ｂおよびｃは、ｃ２中の事象の多くに因果的に関係していないので、それらの事象をもつ同じ因果的連鎖に入ることが許されない。
【００４４】
図７が示すように、多くの縁部は、どんな因果的連鎖の一部でもない。実際、各連鎖は、選択により、単一の事象まで小さくすることができる。しかし、以下で説明されるように、可能な最大の因果的連鎖を保持することは有益である。
【００４５】
次の動作は、因果的連鎖に相対的な各事象の位置を用いて、因果のグラフ表現に注釈をつけることである。たとえば、事象ａは、連鎖ｃ２中の第１の事象である。事象ｂは、連鎖ｃ３中の第１の事象であるが、連鎖ｃ２中の第１の事象に続く。事象ｃは、連鎖ｃ３中の第２の事象であるが、連鎖ｃ２中の第１の事象に続く、などである。これらの注釈は、表の形をとることができ、その場合、因果的先行物をもつ各連鎖がエントリを有し、各エントリは、その連鎖中の最後の先行物の位置＋１を含む。ある事象がその連鎖中の第１の事象である場合、それ自体の連鎖に対する表エントリは、値１を含む。この例では、ａに対する表は、ｃ２：１を含む。ｂに対する表は、ｃ２：２およびｃ３：１を含む。事象ｃに対する表は、ｃ２：２およびｃ３：２を含む、などである。別の見地から見ると、各因果表は、先行物波面を表すデータを含み、その場合、特定の事象に対するすべての先行する事象が、その波面の上または後にある。このようにして、各因果表は、先行物波面（以下では、単に波面と呼ばれることもある）上にある事象を識別し、したがって、これらの因果表はまた、先行物波面表（または単に、波面表）としても知られ得る。本明細書では、これらの語、すなわち「因果表」、「先行物波面表」、および「波面表」は、同義語とみなされ得る。
【００４６】
事象に対する因果的連鎖を（多くの因果的連鎖スキーマで実現可能な）ほぼ一定の時間で確定することができると仮定すると、ｎ個の因果的連鎖および１事象あたり最大ｐ個の先行物での、このアルゴリズムの複雑さは、Ｏ（ｎｐ）である。通常は、各事象が有することのできる直接的先行物の数に対する小さな上界が存在し（３）、すなわち、追加される各事象に対して先行物波面表を計算する複雑さは、Ｏ（ｎ）となる。
【００４７】
実施形態では、２つの事象ａおよびｂの間の因果的関係を評価するための方法は、両者についての先行物波面（ＰＷ）表が与えられた場合、以下のようになる。
両ＰＷ表中の、ａの因果的連鎖に対するエントリを検索する。ｂの値がａの値よりも大きい場合、ａ〜＞ｂである。
【００４８】
両ＰＷ表中の、ｂの因果的連鎖に対するエントリを検索する。ａの値がｂの値よりも大きい場合、ｂ〜＞ａである（適切に構築されたＰＷ表であれば、両方の条件が発生することはなくなる）。
【００４９】
２つの条件がどちらも当てはまらない場合、ａ〜＞ｂでもｂ〜＞ａでもない。
ＰＷ表が特定の連鎖に対するエントリを有さない場合、その連鎖に対する値は、０となると想定される。
【００５０】
この例では、事象ａは、ＰＷ表｛Ｃ２：１｝を有し、ｅはＰＷ表｛ｃ２：２、ｃ３：３、ｃ４：２、Ｃ６：５｝を有する。ｅの連鎖（ｃ６）に対するａのエントリをｃ６に対するｅのエントリと比較すると、０＜５となり、すなわち、ｅ〜／＞ａである。ａの連鎖（ｃ２）に対するｅのエントリをｃ２に対するａのエントリと比較すると、２＞１となり、すなわち、正に予想されるように、ａ〜＞ｅである。
【００５１】
これらの実施形態では、この手法は、ＰＷ表のサイズに関わらず、４回の検索および２回の比較しか必要としない。検索は、最もよくある挙動であると予想されるので、これは非常に望ましい特性である。しかし、これらの利点は一般に、ＰＷ表が、最悪のケースでは、因果的連鎖が存在するのと同じだけ多くの要素を有することを含めた、その他の因子とバランスがとられる。
【００５２】
この技法を実装する際に考慮されるべき、前に触れた別の因子は、分析の完了に必要な演算Ｏの数である。具体的には、連鎖数が事象数に依存する場合、各ＰＷ表ごとにＯ（ｎ）の空間を、または完全な１組の注釈ごとにＯ（ｎ２）の空間を必要とすることになる（明示的推移閉包と同じ）。さらに、連鎖中の事象数に対する限界が存在しない場合、ＰＷ表要素はそれぞれ、記憶するために無制限の空間を必要とし得る。
【００５３】
表の効率的な維持
様々な実施形態では、図８に示されているように、ＰＷ表は、システムによって認識される因果的連鎖の合計数にそのサイズが等しいアレイを用いて実装される。次に、各因果的連鎖に数が割り当てられ、その数は、その連鎖に対応する値に対する索引である。これは、多数の因果的連鎖が存在する場合、非常に大きな表現を生み出しがちとなり得、また、アレイの多くが未使用となるか、または冗長な情報を含み得る。
【００５４】
リンク表技法
あるいは、他の実施形態では、図９に示されているように、各因果的連鎖に索引が割り当てられてもよい。しかし、先に論じたように、各ＰＷ表に対して完全なアレイを割り振る代わりに、アレイは、必要に応じて一時に１要素だけ、割り振られる。有用なデータを含む各要素はまた、有用なデータを含む次の要素へのポインタも含む。索引は、アレイへのオフセットに基づき、もはや暗黙的ではないので、様々な実施形態では、各要素の索引は、要素とともに同じく記憶される。特定の索引に対するエントリを見つけるために、様々な実施形態では、すべての要素の線形探索が行われ、所望の要素に遭遇するまで、索引を本発明者らの所望の索引と比較する。最悪のケースのシナリオでは、この技法は、本来の手法のメモリの最大３倍を必要とする可能性もある。
【００５５】
チャンク割振り表
様々な実施形態では、ＰＷ表の最大サイズがわかっており、そのサイズが因果的連鎖の合計数を満足に下回るとみなされる場合、これは、各ＰＷ表に必要なメモリのすべてが一度に割り振られ得るこの疎方法の使用を、正当化し得る。このケースでは、すべての要素が、それらの間に空間を空けずにメモリの単一のチャンク内にパックされるので、どの要素も次の要素へのポインタを含む必要がない。特定の要素を見つけることは、二分探索を用いて実装される。第１に、中間要素の索引を読み取る。第２に、中間要素の索引が、求められている索引に等しい場合、検索の結果としてその要素が返される。第３に、中間要素の索引が、求められている索引よりも大きい場合、ブロックの下半分に対して、第１の動作を実行する。第４に、中間要素の索引が、求められている索引よりも小さい場合、ブロックの上半分に対して、第１の動作を実行する。
【００５６】
ハッシュ表
様々な実施形態では、ＰＷ表は、ハッシュ表として記憶されてもよい。これは、ハッシュ関数およびハッシュ表ローディングの品質に応じて、明示的アレイでのケースのように、要素の事実上ほぼ一定時間の検索と、リンクリストまたはチャンク割振り疎アレイの高い記憶効率とをもたらし得る。しかし、高速な検索を確保するために、ハッシュ表はしばしば、記憶されるデータの量よりもはるかに大きくする必要がある。
【００５７】
連鎖索引付き表
ブロック割振り方法での１つの問題は、特定のキーのオフセットが、同じ因果的連鎖中でも、ＰＷ表ごとに異なり得ることである。このため、各検索ごとに二分探索を行う必要がある。キーの位置がＰＷ表ごとに異なり得る理由は、各事象が、連鎖中の前の事象ではなく１つまたは複数のセルをもつＰＷ表を必要とすることがあり、すべての要素がアレイ順に存在しなければならないという暗黙的要件が存在するからである。
【００５８】
様々な実施形態では、この要件を緩和するために、連鎖索引付き方法が使用される。図１１に示されているように、各ＰＷ表のサイズは、必要とされるエントリの数にサイジングされるが、エントリは、その他の因果的連鎖のそれぞれがＰＷ表を含む連鎖にいつ知られるようになるかに基づいて、順序付けられる。したがって、各因果的連鎖ごとに、各索引が、その索引を含むすべてのアレイ中の同じ場所に現れる。
【００５９】
混合カウンタ方法
様々な実施形態では、混合カウンタ方法が使用される。これらの実施形態では、混合カウンタ方法は、各事象にＰＷ表を一様に割り当てる代わりに、２つ以上のタイプのカウンタを保持する。この手法は、その直接的因果的関係がその連鎖中にもある因果的連鎖中に、多数の事象が存在するとき、うまく働く。
【００６０】
２値混合カウンタ
様々な実施形態では、２値混合カウンタ方法が使用される。これらの実施形態では、少なくとも次の２つのタイプの事象が存在すると想定される。タイプｅ事象は、自己の因果的連鎖の外部に直接的先行物を有さず、タイプｆ事象は、自己の因果的連鎖の外部に少なくとも１つの直接的先行物を有する。
【００６１】
図１２に示されているように、破線の輪郭をもつ事象はタイプｅであり、実線の輪郭事象はタイプｆである。
タイプｅ事象は次に、最新のタイプｆ事象に戻るカウントを維持するスカラーカウンタが割り当てられ、タイプｆ事象だけが、完全なＰＷ表を必要とする。しかし、２つの事象の間の因果を確定することは、少々、より複雑になる。具体的には、事象ａおよびｂの因果は、ａおよびｂがタイプｅまたはｆかどうかを確定することとなる。タイプｆ事象については、それぞれのＰＷ表中の、ａの因果的連鎖およびｂの因果的連鎖に対する値を検索する。タイプｅ事象については、最新のタイプｆ事象中の、ａの因果的連鎖およびｂの因果的連鎖に対する値を検索し、それ自体の連鎖からの値にスカラーカウンタを加える。上記と同様に、得られた値を比較する。ｂの因果的連鎖に対する事象ａの値が、ｂの自己の値よりも大きい場合、ｂ〜＞ａである。同様に、ａの因果的連鎖に対する事象ｂの値が、ａの自己の値よりも大きい場合、ａ〜＞ｂである。そうでない場合、関係が存在しない。
【００６２】
この場合も、適切に維持されたＰＷ表では、ａの因果的連鎖に対するｂの値がａの自己の値よりも大きいのと同時に、ｂの因果的連鎖に対するａの値がｂの値よりも大きくなることはあり得ない。最悪のケースでは、２値混合カウンタを使用して２つの事象の間の因果を計算するには、現在、最大８回の検索、２回の加算、および２回の比較を必要とし得る。
【００６３】
３値混合カウンタ
様々な実施形態では、３値混合カウンタ方法が使用される。これらの実施形態では、３つのタイプの事象および２つのタイプの因果的連鎖が存在する。この方法は、因果的連鎖中で見つかる交点数の間に、明らかな相違が存在するとき、うまく働く。因果的連鎖のタイプには、タイプ１およびタイプ２がある。
【００６４】
タイプ１因果的連鎖は、莫大な数の他の因果的連鎖との直接交点を有する。
タイプ２因果的連鎖は、ごく少数の他の因果的連鎖との直接交点を有し、それらの大部分は、タイプ１因果的連鎖である。
【００６５】
これらの因果連鎖タイプの定義は、各アプリケーションごとに必要な記憶空間を低減するのを助ける因子に、一部基づく。これらの因子は、因果的連鎖をどちらかのタイプに割り当てる際に、何らかの柔軟性をもたらす。
【００６６】
事象の３つのタイプには、タイプｅ、タイプｆ、およびタイプｉがある。タイプｅは、自己の連鎖の外部に直接的先行物を有さない、どちらかのタイプの連鎖上の事象である。タイプｆは、自己の因果的連鎖の外部に先行物を有する、タイプ１連鎖上の事象である。タイプｉは、自己の因果的連鎖の外部に先行物を有する、タイプ２連鎖上の事象である。
【００６７】
この方法では、タイプｅ事象は、最新のタイプｆまたはタイプｉ事象に戻るようにカウントする、スカラーカウンタが割り当てられる。タイプｆ事象は、完全なＰＷ表を得るが、タイプｉ事象は、完全なＰＷ表を得るか、あるいはタイプ１連鎖上のタイプｅまたはタイプｆ事象へのポインタを有することができる。
【００６８】
分割事象空間
様々な実施形態では、効率をさらに高めるために、事象空間が、部分空間に区分され、したがって、単純な公式化を、各部分空間に適用してもよい。事象空間の範囲は、アプリケーション依存である。一例としては、組織／実体用の１つまたは複数のミッションクリティカルなアプリケーションをサポートする、ネットワーク化コンピューティング環境がある。これらの実施形態では、この構成により、因果的連鎖数および１因果的連鎖あたりの事象数をどちらも制御することが可能になる。区画が因果的に一貫していることを条件として、同じ部分空間内の事象間の因果比較の完了は、常に比較的一定となり得る。異なる部分空間からの事象間で行われる因果比較は、部分空間数および境界事象数に一部基づく、追加の計算時間を必要とする。
【００６９】
図１３は、４つの部分空間またはセルに区分された事象空間を示す。部分空間またはセルは事実上、いくつかの事象用の容器である。境界事象を追加することによって、異なる部分空間またはセル内の事象間の接続が促進される。図１４は、適切な境界事象をもつ、図１３の区分因果グラフを示す。２つの異なる部分空間内の事象間の因果的関係を計算するために、各事象とその部分空間に対する１つまたは複数の境界事象の間の因果的関係がまず計算され、その後、異なる部分空間上の境界事象間の因果的関係が計算される。たとえば、分割空間内の事象ａと事象ｅの間の因果的関係を確定するために、システムはまず、ａ〜＞ａｂ１、ａ〜＞ａｃ１、ｃｄ１〜＞ｅ、およびｃｄ２〜＞ｅを確定することになる。次に、システムは、ａｃ１〜＞ｃｄ１、およびａｃ１〜＞ｃｄ２を確定することになる。最後に、システムは、１つの事象から別の事象への適用可能な経路を構築し、その結果、２つの経路を通るａ〜＞ｅ、すなわち、ａ〜＞ａｃ１〜＞ｃｄ１〜＞ｅおよびａ〜＞ａｃ１〜＞ｃｄ２〜＞ｅ、したがってａ〜＞ｅという結論が得られる。もちろん、ｅ〜＞ａは０本の経路を通り、したがってｅ〜／＞ａである。
【００７０】
前に述べたように、分割事象空間技法は、部分空間区画がほぼ一貫している場合に、よりうまく働く。すなわち、１本の矢印が部分空間ａから部分空間ｂを指すならば、部分空間ｂから部分空間ａを指す矢印がなくなる場合に、また、より制限的には、末尾から先頭へと矢印をたどることによって部分空間ａから部分空間ｂへと経路を追跡することができるならば、部分空間ｂと部分空間ａの間に同様の経路が存在しない場合に、よりうまく働く。部分空間区画がほぼ一貫しているわけではない場合、同じ部分空間内の事象間の因果を確定するときに、境界事象を評価する必要が生じる。
【００７１】
ＰＷ表を使って、部分空間内の因果を確定するとき、境界事象はそれぞれ、それらが属する各部分空間ごとに別個のＰＷ表を維持しなければならない。これらの境界事象はまた、境界事象の間の関係を直接確立するために、高次ＰＷ表を維持してもよい。
【００７２】
階層分割事象空間
様々な実施形態では、階層分割事象空間方法が使用される。これらの実施形態では、部分空間は、事象または他の部分空間を含むことが可能である。これにより、境界事象間を迅速に確定する方法が得られる。極められた結果、この手法は、ＰＷ表なしで因果問題を迅速に（Ｏ（ｌｇ  ｎ））解決するための方法を提供する。たとえば、各事象は部分空間を含み、これらの部分空間は、非常に高次の単一の部分空間内にすべての事象が含まれるまで、より高次の部分空間などにグループ化される。
【００７３】
事象間の関係を確定するには、各事象が別個の部分空間内にあるが、それらの部分空間は隣同士である階層レベルを、まず見つけることを利用する。分割の各側で、照会事象と境界事象の間で同じアルゴリズムを実行する。そのプロセスは、答えが存在するまで繰り返される。
【００７４】
マルチフェーズ記憶手法
様々な実施形態では、マルチフェーズ手法が使用される。これらの実施形態では、この手法は、記憶フェーズに応じて、異なる量の記憶を必要とする。記憶フェーズは、異なるタイプの記憶媒体の原因となり、空間、アクセス時間、およびその他の因子について最適化する。部分空間は、時間の経過により、１つのフェーズから別のフェーズに移ることができる。マルチフェーズ記憶は、記憶部分空間のネットワークに不均一に適用されたとき、すなわち、システム中の互いに異なるセルが互いに異なる記憶フェーズにあるとき、多大な利点を示し得る。
【００７５】
図１５は、マルチフェーズ記憶の極端なケースを示す。１つのフェーズでは、部分空間は、どんな因果マーク付けもなく表され、第２のフェーズでは、部分空間全体が、完全にマーク付けされる。この極端なケースでは、２つの記憶フェーズが存在し得る。フェーズ１は、因果最適化タグをまったく有さず、フェーズ２は、すべての事象が（ＰＷ表、または完全な推移閉包で）完全にタグ付けされる。この極端な手法は、不均一な環境ではうまく働かない。フェーズ１からフェーズ２に部分空間を移動するには、いくつかの他の部分空間も移動する必要があるからである。境界部分空間についての関係を計算するためには、その境界の他の側が計算される必要がある。
【００７６】
図１６に示されているように、様々な実施形態では、混合手法は、フェーズ１が、境界事象を識別するようにさせ、フェーズ２が、２値または３値カウントを用いて部分空間を再構築するようにさせる。このようにして、極端なケースの空間節約の多くが維持されるが、因果タグは、純粋に局所的な情報に基づいて再構築されてもよく、第２のフェーズに必要な記憶空間も低減される。たとえば、先行物事象として境界事象を有さない事象は、次の完全にタグ付けされた事象へのカウンタを含んでもよい。
【００７７】
したがって、特にネットワーク管理用の、因果的関係分析を行うための様々な新規な方法、およびその方法の様々な態様を実施する機能を備えた機器について説明してきたことが、以上の説明からわかる。本発明を前述の実施形態に関して説明してきたが、本発明は説明された実施形態だけに限定されないことを、当業者なら理解するであろう。本発明は、別記の、本特許出願の添付の特許請求の範囲の趣旨および範囲内の改変および変更を加えて、実施することもできる。したがって、この説明は、本発明に対して制限的なものとしてではなく、例示的なものとして、みなされるべきである。
【図面の簡単な説明】
【００７８】
【図１】本発明の様々な実施形態による使用に適したコンピューティング環境のブロック図である。
【図２】本発明の様々な実施形態による例示的なコンピューティングシステムのブロック図である。
【図３】本発明の様々な実施形態による、因果的に関係している事象のグラフ表現を示す図である。
【図４】本発明の様々な実施形態による、潜在的に因果的に関係している事象のグラフ表現を示す図である。
【図５】図５Ａは、本発明の様々な実施形態による、事象因果関係を確定するための線形因果探索の進行を示す図である。
【００７９】
図５Ｂは、本発明の様々な実施形態による、事象因果関係を確定するための線形因果探索の進行を示す図である。
図５Ｃは、本発明の様々な実施形態による、事象因果関係を確定するための線形因果探索の進行を示す図である。
【００８０】
図５Ｄは、本発明の様々な実施形態による、事象因果関係を確定するための線形因果探索の進行を示す図である。
【図６】本発明の様々な実施形態による、推移縁部とともに事象を示す因果のグラフ表現を示す図である。
【図７】本発明の様々な実施形態による、因果的連鎖に区分された図３の因果のグラフ表現を示す図である。
【図８】本発明の様々な実施形態による、因果表を表すためのアレイを示す図７の因果の区分グラフ表現を示す図である。
【図９】本発明の様々な実施形態による、因果表を表すためのリンクリストを示す図７の因果の区分グラフ表現を示す図である。
【図１０】本発明の様々な実施形態による、因果表に対するパック表現を示す図７の因果の区分グラフ表現を示す図である。
【図１１】本発明の様々な実施形態による、各因果的連鎖が他のすべての因果的連鎖のマスタ索引を維持する事象表を示す図７の因果の区分グラフ表現を示す図である。
【図１２】本発明の様々な実施形態による、どちらも２値カウンタを含む２つの事象タイプを示す因果の区分グラフ表現を示す図である。
【図１３】本発明の様々な実施形態による、部分空間またはセルに区分された因果グラフをさらに示す図７の因果の区分グラフ表現を示す図である。
【図１４】本発明の様々な実施形態による、部分空間またはセル境界での境界事象を示す図１３の因果の区分グラフ表現を示す図である。
【図１５】本発明の様々な実施形態による、事象部分空間内の事象のマルチフェーズ記憶を示す図である。
【図１６】本発明の様々な実施形態による、２フェーズの境界事象部分空間因果確定を示す図である。
【図１】
2008547313.tif 000002
【図２】
2008547313.tif 000003
【図３】
2008547313.tif 000004
【図４】
2008547313.tif 000005
【図５】
2008547313.tif 000006
【図６】
2008547313.tif 000007
【図７】
2008547313.tif 000008
【図８】
2008547313.tif 000009
【図９】
2008547313.tif 000010
【図１０】
2008547313.tif 000011
【図１１】
2008547313.tif 000012
【図１２】
2008547313.tif 000013
【図１３】
2008547313.tif 000014
【図１４】
2008547313.tif 000015
【図１５】
2008547313.tif 000016
【図１６】
2008547313.tif 000017