(57)【要約】本願は、複数の別個のプログラムコンポーネントを含むコンピュータソフトウェアプログラムの実行を処理するための手法に関する。より詳細には、本願は、コンピュータプログラムの別個のコンポーネント間の対話に関する手法を記載し、プログラムコンポーネントが高い確定性を伴って実行できるようにする。コンピュータプログラムの１つ以上のコンポーネントの実行が、複数の連続する実行フレームで実行されるように動作可能な実行環境であって、前記実行環境は、ｉ）異なる実行フレームにおける、あるコンポーネントと別のコンポーネント間の通信を許可し、かつｉｉ）同一の実行フレームにおける、あるコンポーネントと別のコンポーネント間の通信を阻止するように更に動作可能である実行環境が記載される。この実行環境を利用するデバッガも記載される。
2009541892.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータプログラムの１つ以上のコンポーネントの実行が、複数の連続する実行フレームで実行されるように動作可能な実行環境であって、前記実行環境は、
ｉ）異なる実行フレームにおける、あるコンポーネントと別のコンポーネント間の通信を許可し、かつ
ｉｉ）同一の実行フレームにおける、あるコンポーネントと別のコンポーネント間の通信を阻止するように更に動作可能である実行環境。
【請求項２】
前記実行環境は、近くの実行フレームのコンポーネント間の通信のみを許可するように動作可能である請求項１に記載の実行環境。
【請求項３】
通信は、他のコンポーネントへのメッセージの送信、または他のコンポーネントからのデータの読み出し、の少なくとも一方を含む請求項１または２に記載の実行環境。
【請求項４】
通信は予め決められた順序で処理される請求項１、２または３に記載の実行環境。
【請求項５】
コンピュータプログラムの１つ以上のコンポーネントの実行が、複数の連続する実行フレームで実行されるように動作可能な実行環境であって、前記実行環境は、前記コンピュータプログラムのコンポーネント間の通信を所定の順序で処理するように更に動作可能である実行環境。
【請求項６】
異なる実行フレームにおけるコンポーネント間の通信を許可し、同一の実行フレームにおけるコンポーネント間の通信を阻止するように更に動作可能である請求項５に記載の実行環境。
【請求項７】
前記実行環境は、近くの実行フレームのコンポーネント間の通信のみを許可するように動作可能である請求項５または６に記載の実行環境。
【請求項８】
通信は、他のコンポーネントへのメッセージの送信、または他のコンポーネントからのデータの読み出し、の少なくとも一方を含む請求項５、６または７に記載の実行環境。
【請求項９】
１つ以上のコンポーネントを投機的に実行するように動作可能である請求項１〜８のいずれか１項に記載の実行環境。
【請求項１０】
少なくとも１つのコンポーネントはオブジェクトである請求項１〜９のいずれか１項に記載の実行環境。
【請求項１１】
前記実行環境が複数のマシンに分散される請求項１〜１０のいずれか１項に記載の実行環境。
【請求項１２】
前記マシンの１つの前記実行環境は、そのマシンのウェブブラウザ内で実装される請求項１１に記載の実行環境。
【請求項１３】
前記マシンの１つの前記実行環境は、そのマシンのウェブブラウザ内にインストールされるように動作可能なブラウザプラグインによって実装される請求項１１または１２に記載の実行環境。
【請求項１４】
前記マシンの１つの前記実行環境は、そのマシンのウェブブラウザが対応している言語で記述された実行時プログラムによって実装される請求項１１、１２または１３に記載の実行環境。
【請求項１５】
前記実行環境は複数のパラレルプロセッサに分散されている請求項１〜１４のいずれか１項に記載の実行環境。
【請求項１６】
ユーザが前記システムと対話しているときに、レーテンシを意識させないように投機的実行を使用するように動作可能である請求項１〜１５のいずれか１項に記載の実行環境。
【請求項１７】
複数のコンピュータによる、または複数のプロセッサによる、または異なる時点での実行のために、１つ以上のコンポーネントの実行を複製するように動作可能である請求項１〜１６のいずれか１項に記載の実行環境。
【請求項１８】
コンピュータで実行されると、前記コンピュータに、請求項１〜１７のいずれか１項に記載の実行環境を提供させるプログラムを格納しているコンピュータ可読記憶媒体。
【請求項１９】
請求項１〜１８のいずれか１項に記載の実行環境を有するコンピュータシステム／装置。
【請求項２０】
請求項１〜１９のいずれか１項に記載の実行環境内での実行のためにコンピュータプログラムを記述する方法であって、前記プログラムは複数のコンポーネントを含み、前記コンポーネントを定義しているコードは、前記実行環境によって、複数の連続する実行フレームで実行されるように複数のコードフラグメントに分割される方法。
【請求項２１】
サーバ実行手段を有するサーバ装置およびクライアント実行手段を有する少なくとも１つのクライアント装置を備えた分散コンピュータシステムであって、前記クライアント実行手段は、コンピュータプログラムのコンポーネントの実行が、サーバ実行環境とクライアント実行環境の両方によって複製されるように、前記サーバ実行環境によって前記クライアント装置のブラウザ内で実行されるように前記プログラムコンポーネントを実行するように動作可能である分散コンピュータシステム。
【請求項２２】
前記サーバ実行手段および前記または各クライアント実行手段は、請求項１〜１８のいずれか１項に記載の実行環境を有する請求項２１に記載の分散コンピュータシステム。
【請求項２３】
分散コンピュータシステムのサーバ装置であって、前記分散コンピュータシステムは前記サーバ装置および少なくとも１つのクライアント装置を有し、前記サーバ装置はサーバ実行環境を有し、前記サーバ装置によって実行されるコンピュータプログラムのプログラムコンポーネントが、前記サーバ実行環境および前記クライアント実行環境の両方によって複製されるように、そのクライアント実行手段による実行のために、前記クライアント装置に送信するように動作可能であるサーバ装置。
【請求項２４】
前記サーバ実行手段は、請求項１〜１８のいずれか１項に記載の実行環境を有する請求項２３に記載のサーバ装置。
【請求項２５】
前記コンピュータプログラムはコンピュータゲームを含み、前記サーバ装置によって前記クライアント装置に送信される前記プログラムコンポーネントは、前記コンピュータゲームのゲームロジックの少なくとも一部を定義しているコードを含む請求項２３または２４に記載のサーバ装置。
【請求項２６】
コンピュータプログラムで発生するエラーを特定するためのデバッガであって、前記デバッガは、コンピュータプログラムの１つ以上のコンポーネントの実行が、複数の連続する実行フレームで実行されるように動作可能な実行環境を有し、前記実行環境は、
ｉ）異なる実行フレームにおける、あるコンポーネントと別のコンポーネント間の通信を許可し、かつ
ｉｉ）同一の実行フレームにおける、あるコンポーネントと別のコンポーネント間の通信を阻止するように更に動作可能であるデバッガ。
【請求項２７】
コンピュータプログラムで発生するエラーを特定するためのデバッガであって、前記デバッガは、コンピュータプログラムの１つ以上のコンポーネントの実行が、複数の連続する実行フレームで実行されるように動作可能な実行環境を有し、前記実行環境は、前記コンピュータプログラムのコンポーネント間の通信を所定の順序で処理するように更に動作可能であるデバッガ。
【請求項２８】
実行中にユーザが前記コンポーネントの状態を検査可能にするように動作可能な検査手段を更に有する請求項２６または２７に記載のデバッガ。
【請求項２９】
実行中にユーザが前記コンピュータプログラムの前記コンポーネントの１つと通信できるようにすることにより、前記実行中のプログラムとの対話を可能にするように動作可能な対話手段を更に有する請求項２６、２７または２８に記載のデバッガ。
【請求項３０】
ユーザが、前記コンポーネントの１つ以上を含む値を直接変更可能にするように動作可能な変更手段を更に有する請求項２６〜２９のいずれか１項に記載のデバッガ。
【請求項３１】
特定のフレームにおける前記または各コンポーネントの状態に関する情報を含む保存されたフレームを生成するように動作可能な保存手段を更に有する請求項２６〜３０のいずれか１項に記載のデバッガ。
【請求項３２】
その後の実行のために前記保存されたフレームの再ロードを可能にするように動作可能な復元手段を更に有する請求項３１に記載のデバッガ。
【請求項３３】
現在の実行状態を以前の特定のフレームの実行状態に戻すために、フレームまたはフレームの組の破棄を可能にするように動作可能なアンドゥ手段を更に有する請求項２６〜３２のいずれか１項に記載のデバッガ。
【請求項３４】
コンピュータで実行されると、前記コンピュータに、請求項２６〜３３のいずれか１項に記載のデバッガまたは請求項２３、２４または２５に記載のサーバ装置を提供させるプログラムを格納しているコンピュータ可読記憶媒体。
【請求項３５】
請求項２６〜３３のいずれか１項に記載のデバッガを有するコンピュータシステム／装置。
【請求項３６】
実質的に明細書に記載し添付の図面に示した通りの実行環境／分散コンピュータシステム／サーバ装置／デバッガ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の別個のプログラムコンポーネントを含むコンピュータソフトウェアプログラムの実行を処理するための手法に関する。より詳細には、本発明は、コンピュータプログラムの別個のコンポーネント間の対話に関する。
【背景技術】
【０００２】
コンピュータプログラムが複数のプログラムコンポーネント（例えばプログラムオブジェクトまたは演算）に分割され、これにより、いくつかのコンポーネントを並列に実行できるようになるか、または１つ以上のコンポーネントを順次実行できるようになることが一般的であることが知られている。プログラムオブジェクトなどのプログラムコンポーネントは、データと、そのデータを操作するために必要な手順を含むコンピュータプログラムを構成する別個のアイテムであるとみなすことができる。
【０００３】
いくつかの別個のプログラムコンポーネントを含むコンピュータプログラムの実行中に、プログラムコンポーネント間で対話が行われることがある。このため、複数のユーザが、１つ以上のプログラムコンポーネントを介して、これらのコンポーネントに与えられる入力データによって互いに対話することが可能となる。実際、複数のユーザが、仮想世界を共有し、その仮想世界内で、多くの場合リアルタイムに相互に対話することが切望されることが多い。例えば、コンピュータゲームの分野では、複数のユーザインタフェースを有する１台のマシンによって、あるいは、複数のマシンを有するコンピュータシステムによって、２人以上のユーザが仮想ゲーム世界に参加することが望ましい。このために、異なるマシンまたは同じマシンで実行している別個のプログラムコンポーネント間で対話が行われる。異なるマシンで実行している２つのプログラムコンポーネント間の対話は、コンピュータプログラムのドメイン内で、通常はネットワーク（例えばローカルエリアネットワーク（ＬＡＮ）またはインターネット）を介して行われるが、他の通信媒体も存在する。同じマシンで実行している別個のプログラムコンポーネントが対話する際には、この通信が、何らかのネットワーク以外のメカニズムによるもののこともあり、これには、例えば、共有メモリ、Ｕｎｉｘ（登録商標）ドメインソケットや、ネットワークチャネルでないその他の通信チャネルの使用がある。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
コンピュータプログラムの分散または並列実行は、多くの理由により特に問題となる。コンピュータプログラムの複数のコンポーネントの実行を実装する際に扱うべき主な問題の１つに、同じユーザ入力を与えて、２台の異なるマシン／プロセッサによって、または異なる時間に、同じコードセクションを実行しても、得られる結果が変わる傾向があるという点がある。この理由は、ほとんどの並列プログラミングシステムが、プログラムの異なるコンポーネントが完了および対話するタイミングに依存して、異なる演算結果を与えるためである。このため、並列プログラミングシステムは、多くの場合、不確定である（non-deterministic）、つまり、プログラムの実行の結果を予測することができないと言われている。よく書けたプログラムに基づくシステムであっても、不確定性の課題により、問題に直面することがある。また、最も経験豊富なコンピュータプログラマにとっても、分散プログラムの記述および実装は、非常に困難である。
【０００５】
分散システム内の不確定性により、異なるマシン上の対応するオブジェクト状態間にばらつきが生じる。分散システムに含まれる異なるマシン上の対応するオブジェクトの実行間の矛盾、このため、シミュレーションおよび／または表現により、挙動が急速に目に見えて異なってくる。場合によっては、このばらつきにより、異なるコンピュータ上で、プログラムの結果が変わってしまうこともある。
【０００６】
不確定性の問題は、分散システムの特定の問題であり、（同じユーザ入力を与えたときに）あるマシン上の特定のプログラムコンポーネントの実行の結果と、別のマシン上の同じプログラムコンポーネントの実行の結果の間のばらつきは、プログラムの結果、ひいてはシステムの価値を損なう。例えば、複数のユーザが、それぞれ、仮想世界を占めるオブジェクトによって、自身の仮想世界の視野を提示され、互いに対話するオンラインゲームの分野では、異なるマシン上の対応するオブジェクト間に目に見えて異なる挙動が生じないことは、ゲームの連続性を保証するために不可欠である。
【０００７】
異なるマシンによる、対応するプログラムコンポーネントまたはオブジェクトの実行から得られる実行結果のばらつきの可能性を避けるために、プログラムの実行の全てをサーバマシンで行ない、必要であれば、この実行結果に関する詳細をクライアントに送信することが、分散プログラムの提供業者に周知である。この場合、クライアントマシンは、単にユーザ入力を受け付け、クライアントマシンのユーザに、実行結果を視覚的出力および音声出力の形で提示するように機能するアプリケーションを実行するように動作可能であり、プログラムのどの部分の実行も行わない。
【０００８】
しかし、この方法は、サーバとクライアント間で実行結果に関する詳細を送信する際に、システムが利用可能な帯域幅のキャパシティのかなりの部分を使用する。また、レーテンシの問題による影響も受ける。特に、ネットワークを介して何百または何千人ものプレーヤに同時に対応しようとする世界的ＭＭＯＧ（大規模マルチプレーヤオンラインゲーム）の技術分野では、帯域幅の消費とレーテンシの問題が誇張される。実際、ネットワークを介してマシン間で伝達される情報量は、一部のゲームでは途方もなく多くなりうる。
【０００９】
データの同時アクセスと変更によって発生する不正確かつ矛盾するプログラム状態を阻止しようとするために、「ロック」として知られるプロセスを使用する分散および並列プログラミングシステムが知られている。これは、プログラムのある部分が、特定のデータ構造を使用中にこれをロックし、このデータ構造がロックされている間は、プログラムの他の部分がこの構造に一切アクセスできなくするメカニズムである。ロックは、プログラマが行うのが困難であり、エラー（例えばレース条件）を発生させやすく、並列性を制限し、プログラムが永久に動作を停止するデッドロックを引き起こすことがある。頻繁に起こる別の問題は、使用中のネットワークの通信帯域幅およびレーテンシによって生じる。ネットワークは、相対的に通信が遅く、プログラムの２つの部分が異なるコンピュータで実行しているが、これらの間に多くの通信が必要な場合、ネットワークがボトルネックとなる。プログラムの全ての部分が同じメモリシステムにアクセスしている場合は、メモリがボトルネックとなる。
【００１０】
別の問題として、矛盾する不適切なデータアクセスや、シングルスレッドの非分散プログラムでは発生しえないエラーの発生がある。考えられるエラーの原因が膨大に存在するため、堅固なソフトウェアを記述することが困難である。プログラムのセクションが、分散システム内のどのコンピュータ上で実行していてもよく、分散システム内のどのコンピュータにあるデータにもアクセスすることができる。このため、プログラム内の異なるデータ部分を参照するために、異なる手法を使用しなければならない。このため、ローカルコンピュータでのみ機能する高速な方法あるいは、どのコンピュータでも機能するが低速で複雑な方法のいずれを使用するかを、プログラマが決定することが困難となりうる。
【００１１】
別の問題は、ユーザの対話の予測不可能な性質に起因する。メッセージがユーザのコンピュータからサーバに取得され、他の全ユーザに伝達されるまでに時間がかかるため、システム内でユーザが変更を行ってから、その変更を他の全ユーザが認識できるようになるまでタイムラグがある。このため、このような分散システムのユーザ入力に対する応答性が低下する。複数のユーザが、プログラムと対話し、かつ互いに対話するためにインターネットを使用している場合、ネットワークレーテンシ（あるコンピュータから別のコンピュータにメッセージが届くのにかかる時間）によって、システムをインタラクティブに維持し、ネットワーク上でプログラム状態を矛盾のない状態に保つ上で問題となる。
【００１２】
公知の分散プログラミングシステムの一例に、メッセージパッシングインタフェース（Message Passing Interface：ＭＰＩ）がある。これは高性能コンピューティングで多用されている。しかし、この問題として、データアクセスの矛盾、ロック、ブロック、レース条件およびデッドロックが発生するという点が挙げられる。通信ボトルネックは明白であり、プログラマが認識できる。更に、このインタフェースは確定的でなく、インタラクティブな用途のために設計されていない。別の分散プログラミングシステムとして、通信逐次プロセス（Communicating Sequential Processes：ＣＳＰ）がある。これは、モデリングネットワークプロトコルに主として使用され、多くの場合、実際のソフトウェアの開発には使用されない。ロック、ブロックおよびデッドロックが発生し、インタラクティブな用途のために設計されていない。分散プログラミングシステムの別の例として、マルチスレッド、リモートプロシージャコール、および分散関数型プログラミングなどがある。マルチスレッドは共有メモリを必要とするため、共有メモリが通信ボトルネックとなる。また、スケーラビリティが限られている。リモートプロシージャコールは、プログラマにとって単純なシステムである。しかし、並列化に適しておらず、このため拡張性がさほど高くない。
【００１３】
プログラム中で並列性を処理するための公知の方式は、演算のＳｉｍｕｌａモデルを使用する。これは、コルーチン制御構造に基づいている。Ｓｉｍｕｌａにより、Ｓｉｍｕｌａプログラムのユーザからは並列に実行しているようにみえるオブジェクトを含む準並列プログラムが可能となる。実際には、オブジェクトは順次実行されているが、実行を休止および再開し、実行をオブジェクト間で移行させることが可能であり、協調的なスケジューリングが可能である。この準並列の効果を得るためには、Ｓｉｍｕｌａのプログラマが、制御の移行を明示的に記述しなければならない。Ｓｉｍｕｌａはオブジェクトがローカルであることを想定しており、共有されたグローバルデータにアクセスすることができる。Ｓｉｍｕｌａの問題は、完全なコルーチンを可能にすることで、プログラムが、実行の移行によって複雑化するため、理解が困難となることにある。
【００１４】
さらに別の公知のモデルとして、演算のいわゆる「アクターモデル」がある。各アクターは、メッセージの受信などのイベントに応答し、このため、その実行はイベント駆動的である。これにより、アクター内およびアクター間での並列性が可能となる。しかし、アクターが特定の順序で実行されることが保証されず、アクター間で送信されるメッセージが特定の順序で到着することが保証されないという問題がある。このため、その後の実行において、メッセージが受信される順序が変わる可能性があるため、アクターベースのプログラムは必ずしも確定的とは限らない。
【００１５】
上記の問題の一部は、分散関数型プログラミングを使用して解決することができる。これは、時として、Ｅｒｌａｎｇ（分散システム用にＥｒｉｃｓｓｏｎなどが使用するプログラミング言語）などの高度にスケーラブルなシステムで使用される。これを使用すれば、ロック、ブロック、レース条件またはデッドロックを発生させずに分散関数型プログラミングを行うことが可能となる。Ｅｒｌａｎｇは、確定的でもあるが、通常は、インタラクティブなプログラムの記述に使用されない。また、Ｅｒｌａｎｇのほかに、分散実行を可能にする関数型言語のほかの例がある。このような言語にＯｚがあり、これは関数型プログラミング言語と命令型プログラミング言語を合わせたような言語であり、ＭＬ、およびＨａｓｋｅｌｌ：Ａｌｉｃｅ、ＧＰＨ、およびＧｏｏｇｌｅのＭａｐｒｅｄｕｃｅシステムの分散版である。
【００１６】
このため、同じユーザ入力を与えたときに、２台の異なるマシン／プロセッサ上、または異なる時間での、所定のプログラムコンポーネントの実行から得られる結果のばらつきの可能性を低減させることが求められている。つまり、高い確定性を伴ったコンピュータプログラムの実行を保証することが望ましい。
【課題を解決するための手段】
【００１７】
本発明の第１の態様によれば、コンピュータプログラムの１つ以上のコンポーネントの実行が、複数の連続する実行フレームで実行されるように動作可能な実行環境が提供され、前記実行環境は、
ｉ）異なる実行フレームにおける、あるコンポーネントと別のコンポーネント間の通信を許可し、かつ
ｉｉ）同一の実行フレームにおける、あるコンポーネントと別のコンポーネント間の通信を阻止するように更に動作可能である。
【００１８】
好ましくは、実行環境は、近くのフレームのコンポーネント間の通信のみを許可するように動作可能である。好ましくは、実行環境は、コンポーネント間の通信を所定の順序で処理するように更に動作可能である。
【００１９】
本発明の第２の態様によれば、コンピュータプログラムの１つ以上のコンポーネントの実行が、複数の連続する実行フレームで実行されるように動作可能な実行環境が提供され、前記実行環境は、前記コンピュータプログラムのコンポーネント間の通信を所定の順序で処理するように更に動作可能である。
【００２０】
コンポーネント間の通信は、メッセージの送信、または他のコンポーネントの状態の少なくとも一部の読み出しの少なくとも一方を含むことができる。通信は、隣接するフレームのコンポーネント間、または２つ以上のフレームを挟んだフレームのコンポーネント間で行うことができる。好ましくは、実行環境は、メッセージを所定の順序で処理するように動作可能である。コンポーネントは、オブジェクト（すなわち、データと、そのデータに操作するために必要なプロシージャを含むコンピュータプログラムの一部を形成している別個のアイテム）を含むことができる。
【００２１】
本発明の第１および第２の態様を実施する実行環境は、プログラムコードの「フレーム」（すなわち時間または作業の単位）での実行を容易にし、プログラムの少なくとも１つのコンポーネントが各実行フレームに含まれているように有利に構成されうる。同じ状態にある、対応するオブジェクト（すなわち、別個のコンポーネント部分、例えば２台の異なるマシンで実行されているゲーム内のキャラクタを実装している部分など）が、２台の別のコンピュータまたは２つの別の時点で同じコードを実行する場合に、オブジェクトの新しい状態が２台のマシンまたは２つの時点で有利に同じとなるという点で、本発明の第１および第２の態様の実施形態は有利である。本発明の第１および第２の態様を実施する実行環境は、分散環境におけるコンピュータコンポーネントの高い確定性を伴った実行を容易にするという点で、分散型の実装において特に有利である。また、プログラムを連続するフレームに分割することにより、異なるプログラムコンポーネントまたは異なるオブジェクトの並行実行が有利に可能となる。このため、任意の所定のフレームで、複数のプログラム部分の実行を並列に行うことができる。
【００２２】
好ましくは、本発明の実施形態によれば、メッセージは、オブジェクト間で、あるいは外部世界（例えばユーザまたはＣ＋＋プログラム）とオブジェクト間で送信することができる。メッセージにより、システムおよび外部世界内のオブジェクト間通信が可能となる。メッセージは、ネットワークに送信することができる。メッセージは、特定のフレーム番号およびターゲットオブジェクトに伝達される。同一フレームにおけるコンポーネント間の通信を阻止するように動作可能である本発明の実施形態によれば、オブジェクトがメッセージを送信すると、そのメッセージは、別の後続のフレームでしか受信することができない。オブジェクトによるメッセージの受信は、好ましくは、各フレームの各オブジェクトに、着信メッセージのキューを提供することによって実装できる。キューは、好ましくは、ネットワークの整合性を保つために、確定的な配列（deterministic
ordering）方法を使用して配列されなければならない。
【００２３】
確定的な配列方法では、所定のフレームの所定のオブジェクトに対して受信されたメッセージの組の全体を以下に基づいてソートする。
１）送信順
２）送信側の識別情報
【００２４】
このため、オブジェクトが、Ａとこれに続くＢの２つのメッセージを送信した場合、受信側は、Ａ、Ｂの順で受信する。このように、到着順は、送信順と同じである。２つのオブジェクト（１）および（２）が２つのメッセージＡ１とＢ１、およびＡ２とＢ２をそれぞれ送信した場合、受信側は、Ａ１  Ｂ１、次にＡ２  Ｂ２の順でこれらを受信する。この結果、順序が、ローカルに（１つの送信側からのメッセージ内で）保たれると共に、グローバルに保たれる（複数の送信側からのメッセージが、送信側のＩＤによって配列される）。送信側が複数存在する場合、送信行為が重複し、例えばオブジェクト（１）と（２）が並行に実行しうる。好ましくは、ユーザ入力メッセージもソートできるように、クライアントに与えられるＩＤに対して更に配列が行われる。例えば、２つのクライアントが同じオブジェクトにユーザに入力メッセージを送信した場合に、クライアントＩＤによって順序が決定される。
【００２５】
本発明においては、「外部世界」とは、本提案発明の実行環境内で実行されるプログラムを記述するための好適な条件に従わない別の言語で記述されたソフトウェアを指す。外部世界は、ユーザから情報を受信したり、ネットワークを介してデータのストリームを送信したり、またはユーザに結果を表示するなどの重要な作業を行う。外部世界は、好ましくは、後述するシステムの好適な条件に違反してはならない。外部世界は、本発明を実施するシステム内のオブジェクトにメッセージに送信することができ、システム内のオブジェクトへの参照を保持し、システムにオブジェクトを作成し、複製または投機的に実行するオブジェクトの組を作成するか、あるいは、システム内のオブジェクトの状態を読み出しうる。外部世界は、システム内のどのオブジェクトの状態も変更することができないが、オブジェクトは関数を介して呼び出すことができる。しかし、このような関数呼び出しによって、異なるマシン上の対応するオブジェクトの実行間にばらつきが生じないことを保証するために、関数呼び出しは、好ましくは、関数に対する引数が等しく、関数が呼び出されたフレーム番号が等しければ、常に、システム内の全コンピュータで全く同じ結果を返さなければならない。このような関数呼び出しは、好ましくは、呼び出しオブジェクトのローカル状態を変更できてはならない。
【００２６】
コンピュータプログラムを一連のフレーム（すなわち時間または作業の単位）に分割することにより、プログラムコンポーネントの状態が矛盾なく定められるように同期が可能となり、有利である。本発明の好ましい実施形態によれば、オブジェクトは、フレーム内でのみ、見える状態（visible
state）を変更でき、前のフレームの終点でのみ、他のオブジェクトの値を読み出すことができる。また、メッセージは、コンピュータプログラムの所定のフレームに添付されるか、またはこれに関連付けられる。フレームがクロックに添付されてもよく、これにより、新しいフレームが、（例えば）５０分の１秒ごとに起動されても、新しいフレームが最後のフレームの終了時に直ちに開始されても、あるいは、フレームがパイプラインで実行され、個々のオブジェクトの実行が、実行を完了するために十分な入力データが利用可能になるたびに開始されてもよい。
【００２７】
フレームは階層構造を有していてもよく、この場合、全体的なフレームクロックがサブフレームに分割される。この構成により、オブジェクトの組が、複数のオブジェクトに分散されている特定のアルゴリズムについて、非常に高速なフレームカウンタで動作することが可能となり有利である。最も粒度の大きなフレームはネットワークフレームに対応し、最も粒度の小さい好ましいフレームは、現在のプロセッサ上でのオペレーションに対応することが想定される。本発明の実施形態によれば、オブジェクトの状態は、フレームの始点または終点においてのみ参照することができ、このため、あるフレームの始点における状態は、その前のフレームの終点の状態に等しくなる。
【００２８】
このようにして実行環境を構成することにより、本発明の第１または第２の態様を実施する実行環境内での実行のためのプログラムを記述しているプログラマは、命令型プログラミングを使用して、オブジェクトとその挙動を有利に定義することができる。したがって、システムを、通常の命令型プログラミング言語とほぼ同じように容易にプログラムすることができる。また、フレーム構造と、本発明の第１の態様の実施形態によってフレーム内通信が禁止されているため、ソフトウェアをあたかも分散関数型プログラミング言語であるかのように並列化し、考える（reason）ことが可能である。
【００２９】
いうまでもなく、フレーム内通信を阻止するように動作可能な本発明の第１の態様を実施する実行環境の結果、フレームの始点におけるシステムの状態は、その前のフレームの終点におけるシステムの状態およびシステムが受け取った任意の外部メッセージのみの関数である。フレームの始点におけるシステムの状態は、そのフレームの始点における全オブジェクトの状態と、その前のフレームから送信された全メッセージからなる。このため、複数のオブジェクトを含むコンピュータプログラムについて、システムの全オブジェクトのサブセットを定義することが可能である。サブセットは真部分集合であっても、１つのオブジェクトが存在する場合には、非自明な部分集合であってもよい。特定のフレームでのシステム内のオブジェクトのサブセットの状態は、その前のフレームの始点におけるこれらのオブジェクトの状態と、以前のフレームからオブジェクトのサブセットに送信された全メッセージとの関数である。
【００３０】
数式化すると、Ｏｎ，ｉがフレームｎの始点におけるオブジェクトｉの状態であり、Ｍｎ，ｉがフレームｎからフレームｎ＋１までにオブジェクトｉから送信されたメッセージのリストであり、ｆｎ，ｉがフレームｎにおけるオブジェクトｉの挙動に対応する関数であるとすると、以下の式が成立する。
（Ｏｎ＋１，ｉ，Ｍｎ＋１，ｉ）＝ｆｎ＋１，ｉ（Ｏｎ，ｉ  Ｍｎ，ｉ）
【００３１】
これは、フレームｎの関数であり、フレームｎ＋１の状態を返す。上記式からわかるように、フレームｎ＋１の全体の状態はフレームｎのみの関数である。つまり、フレームｎ内に相互依存が存在せず、このため、フレームｎ内の全オブジェクトを有利に並列に実行することができる。
【００３２】
本発明の別の重要な利点は、プログラムオブジェクトの高度な並列実行を可能にするその能力である。このため、プログラム内のオブジェクトの数が増え、シングルプロセッサでは不十分になった場合に、プログラムコードの実行を、複数のプロセッサに容易に分散させることができる。更に、並列性および高い確定性は、本発明の第１および第２の態様の原理に従って実行するように記述されたプログラムの潜在的な特徴であるため、これを実現するために、プログラムコードを変更する必要がない。このように、本発明の実施形態は、大規模なデプロイメント（展開）の実施を容易にし、これにより、例えば、ネットワークを介して対話している多数のユーザに対応するために、数多くのオブジェクトが関与する複雑なコンピュータゲームを分散方式で実行することができる。
【００３３】
プログラムのテスト工程中に直面する問題を考えると、本発明の更に別の利点は明らかである。コンピュータゲームなどのプログラムのテスト工程では、オペレータが、特定の入力を使用して、手動でコードのセクションを辿り、プログラムが所望のように機能するかどうかをテストする。しかし、このようなテスト方式は、実行環境が複数のマシンに分散されており、実行が確定的でない大規模な分散または並列プログラムに適用するのは容易ではない。
【００３４】
このため、いうまでもなく、本発明の実行環境内での実行のために記述され、高い確定性を伴って実行されることの利益を受けるプログラムは、より容易にテストすることができ、プログラムが、テスト時だけではなく、デプロイメント後にも「正しく」実行することを、ゲーム開発者／提供業者が確信できるという利点を備える。
【００３５】
サーバマシンと１台以上のクライアントマシンを有する分散型デプロイメントシナリオの場合、クライアント実行環境（またはクライアント「実行時システム」）が、ユーザのコンピュータシステムにネイティブに（natively）インストールされるソフトウェアプログラムによって有利に実装されうる。しかし、多くの場合、ユーザが、クライアントマシンにソフトウェアをダウンロードして、インストールする必要があることが、分散プログラムの潜在的な参加者の参加を妨げる壁となっている。例えば、ユーザが、ネットワークを介して仮想世界を共有し、その仮想世界の中で互いに対話することを望んでいるオンラインゲームの場合、ユーザが、最初に自分のマシンにソフトウェアをダウンロードし、インストールする必要がなくても参加できるゲームを提供業者が提供できることは、技術的にも商業的にも有利である。
【００３６】
この点で、本発明の一実施形態によれは、クライアント実行環境は、クライアントのウェブブラウザ内で実装されうる。ブラウザとは、ユーザが、ネットワーク（例えばワールドワイドウェブまたはローカルエリアネットワーク）上で、文字および画像を表示し、これらと対話できるようにするソフトウェアアプリケーションであることは、当業者にとって周知である。ウェブブラウザは、現在使用されている例としてはインターネットエクスプローラやネットスケープナビゲータがあり、ＨＴＭＬ情報を、ユーザのマシンに表示するためにフォーマットする。また、ブラウザは、Ｊａｖａ（登録商標）Ｓｃｒｉｐｔなどの多くの言語のほか、ブラウザに搭載されているか、場合によっては後から自動的にインストールされるプラグイン実行時システムを介して実行される、プラグインベースのアプリケーションの実行に直接対応している傾向がある。いうまでもなく、プラグインとは、ウェブブラウザの機能を拡張するソフトウェアモジュールである。例えば、プラグインの一般的な利用として、アニメーションなどの特化したコンテンツに対応するように、ブラウザを拡張することがある。
【００３７】
このため、本発明の第１の態様および第２の態様の実施形態によるクライアント実行環境は、ネットワークを介してオンデマンドでダウンロードされ、オンザフライでユーザのウェブブラウザにインストールされるブラウザプラグインによって実装されうる。別法では、あるいは上記に加えて、クライアント実行環境は、ブラウザが対応している言語（例えばＪａｖａ（登録商標）Ｓｃｒｉｐｔ）で記述された実行時プログラムによって実装され、この実行時プログラムは、本発明を実施する実行環境内での実行のために記述されたコードまたはスクリプトを実行することができる。
【００３８】
ウェブブラウザ内でのクライアント実行環境の実装は、ユーザのＰＣに追加のソフトウェアをインストールする必要なく、ユーザが分散プログラム（例えばオンラインゲーム）に参加できるようにするという点において極めて有利である。また、実行時プラグイン／プログラムは、実行時にユーザのブラウザにダウンロードできるため、ブラウザ組み込み型の実行時システムは、ネイティブにインストールされているクライアントソフトウェアの補助（supplement）として有利となりうる。これにより、クライアントのコンピュータシステムは、ユーザのマシンにインストールされている旧バージョンでは実行できない、最新の仕様に従って記述された新機能を導入するコードまたはスクリプトを実行できるようになる。
【００３９】
このため、いうまでもなく、本発明を実施する分散コンピュータシステムは、サーバ実行環境内で実行するために記述されたコードを変更する必要なく、スタンドアロンのクライアントアプリケーションからブラウザ組み込み型クライアントまでの、異なるタイプの実行時環境で実行される（すなわち、異種のクライアントプラットフォーム内で実装される）クライアントに有利に対応することができる。このため、本発明を実施するシステムによって提供される大きな利点は、本発明のフレーム構造内で実行するために記述されたコードまたはオブジェクトは、変更なしで、本発明を実施し、しかしその実行環境が実装されている任意の実行環境で再利用することができる点にある。これにより、クライアントプラットフォームとサーバプラットフォームの両方のゲームロジックを記述および保守する必要がなくなることで、オンラインゲーム等の分散プログラムを実装するための開発作業を実質的に低減できる。このため、プログラム開発者は、あらゆるプラットフォームでの整合性を保証することに長時間を費やす代わりに、プログラムのインタフェースに関わる細かい事項に集中することができる。
【００４０】
異種システムプラットフォームのためにプログラムコードを記述／変更する必要がなくなることは、本発明の実行環境内での実行のために開発されたプログラムの大きな利点であるが、特定のクラスのクライアントプラットフォーム内でより最適に実行するために、プログラムの提供業者が、第１の基本的なクライアントアプリケーションのほか、おそらくより高度なグラフィカルな効果を有する第２の高性能のクライアントアプリケーションを提供できることが、場合によっては有利となりうる。例えば、第１の基本的なクライアントアプリケーションは、分散プログラムへの即時の参加を可能にするダウンロード可能なブラウザプラグイン内で実行可能であり、高性能版は、参加者が、クライアント実行環境を提供するためのソフトウェアを自分のマシンにインストールした場合に利用可能である。更に、クライアントのリソースおよび能力により適切に合うように、特定のクライアントマシンで実行するために、サーバによって送信されるコードの複雑さのレベルを変える（高度または簡略にするなど）ことができる。このため、この場合、サーバは、クライアントに送信されるコードを適合させる機能を有するようになる。
【００４１】
このため、例えば、分散実行を目的としたコンピュータゲームの提供業者／開発者は、以下のようにそのコンピュータゲームのプログラムを開発しうる。
【００４２】
１）一般的なサーバ実行環境内で実行するためのゲームプレイのコード（すなわちゲームロジック）を記述し、このゲームプレイコードは、任意のクライアントプラットフォーム内で実装されるクライアント実行環境によって実行されるように適用可能である。
２）クライアントで実行されると、クライアントマシンにグラフィックを表示し、ユーザ入力を受け取るために、ゲームプレイコードと対話するクライアントアプリケーション（Ｊａｖａ（登録商標）アプレットなど）を記述する。
３）任意選択で、ステップ１で記述されたゲームプレイコードの変更に基づいて、特定の追加のターゲットプラットフォーム（例えばコンソール、携帯電話、ＰＣ、ウェブベースのクライアント）用のクライアントアプリケーションを記述する。このため、所定のターゲットプラットフォーム用に記述されるクライアントアプリケーションは、ステップ１で記述されたゲームプレイコードの高性能版のこともあれば、簡略版のこともある。例えば、高性能のクライアントアプリケーションは、変更なしのゲームプレイコードを実行するように動作可能であり、能力またはリソースが比較的限られているクライアントアプリケーションは、そのクライアントプラットフォームのために特に記述されたゲームプレイコードの簡略版を実行するように動作可能であることが考えられる。
４）クライアントアプリケーションを配布し、クライアントが接続するためのサーバシステムを動作させる。
【００４３】
クライアントマシンのブラウザ内にクライアントが実装される、ネットワークを介したプログラムの実行を管理するための多くの手法が、特にオンラインゲームの分野でこれまでに提案されている。例えば、クライアントのウェブブラウザ内でゲームコードを実行するために、ウェブブラウザ、およびＪａｖａ（登録商標）またはＦｌａｓｈ等のプラグインなどのクライアントサイド技術に完全に依存したブラウザベースのゲームが知られている。しかし、ウェブブラウザのセキュリティモデルは、一般に、コードが第三者と通信する能力を制限しており、通常、コードの取得元の発信元サーバへの接続のみを許可するため、このようなプラグインベースのゲームは、通常、シングルプレーヤゲームに制限されている。
【００４４】
また、サーバ側で全てのゲームコードが記憶され、実行される、いわゆるサーバサイドゲームも公知である。このようなゲームは、ブラウザが対応している言語で記述されたクライアントサイドアプリケーションを送信し、このアプリケーションにより、ユーザは、そのユーザのオンラインゲームから即時の応答を得られるようになる。この場合、クライアント側のコードは、単にゲームのインタフェースを提示し、ユーザ入力をサーバに中継して、ユーザに表示されるゲームを更新するためにサーバに応答する程度の動作しかしない。ゲームクライアントは、ゲームコードを実際に実行しておらず、単にユーザから入力を受け付けてサーバに送信し、ゲームの表示のためにサーバから更新を受け付けるだけである。しかし、クライアントがダムであるため、このようなシステムはネットワークトラフィックに関連する問題の影響を受ける。クライアントマシンにゲーム世界の現在の状態が正しく表示されることを保証するために、クライアントとサーバ間で必要な通信の結果、帯域幅の消費が大きくなる。更新を表示させるためには、更新を、クライアント、サーバ、クライアントへと往復させる必要があるため、レーテンシも問題となる。
【００４５】
このため、既に考察されたマルチプレーヤネットワークゲームの帯域幅の要件と応答性を改善する分散システムを提供することが求められている。
【００４６】
本発明の第３の態様によれば、サーバ実行手段を有するサーバ装置およびクライアント実行手段を有する少なくとも１つのクライアント装置を備えた分散コンピュータシステムであって、クライアント実行手段は、プログラムの少なくとも１つのコンポーネントの実行が、サーバ実行環境とクライアント実行環境の両方によって複製されるように、サーバ実行環境によってクライアント装置のブラウザ内で実行されるようにプログラムコンポーネントを実行するように動作可能である分散コンピュータシステムを提供する。
【００４７】
サーバ装置および１台以上のクライアントのそれぞれにプログラムのコンポーネントの実行を複製するためには、サーバ実行環境および前記または各クライアント実行環境の両方が、同じ初期条件（例えば前記プログラム部分に含まれるオブジェクトの初期状態）および入力データ（例えばユーザ入力）を与えられたときに、そのプログラムコンポーネントを含むプログラムコードの実行が、各実行環境によって基本的には同じ結果を与えるように構成され、動作可能である必要がある。参加している各装置の実行環境は有利に確定的である。好ましくは、参加している１台以上の装置の実行環境は、本発明の第１または第２の態様による実行環境を有する。
【００４８】
分散型コンピュータゲームにおいては、例えば、サーバおよびクライアントのそれぞれで実行される「プログラムコンポーネント」は、好ましくは、「ゲームロジック」（ゲーム世界の中のオブジェクトおよび／または許容されるアクション）の少なくとも一部を定義するコードを含む。このため、ゲームロジックコードは、ユーザ入力およびプリプログラムされた挙動パターンに応答して、プログラムの関連するオブジェクトに対してアクションを実行する。
【００４９】
本発明の任意のクライアント実行環境は、クライアントマシンに備えられたものであっても、ユーザのマシンのブラウザ内に実装されるものであっても、好ましくは、アプリケーションが以下を実行可能にすべきである。
−サーバ装置に接続する／サーバ装置から切断する。
−本発明の第１の態様の実行環境での実行のために記述されたプログラム演算を取得および実行する。
−クライアント上でプログラム演算を検査する。
−例えばユーザ入力データを送信するために、クライアントマシンでローカルに実行している、あるいは別のクライアントまたはサーバでリモートに実行しているプログラム演算間の通信を可能にする。
【００５０】
この点で、クライアント実行時システムは、本発明の実行環境内での実行のために記述され、サーバから送信され、サーバおよび他のクライアントで実行しているコードと対話するコードの実行を可能にする。このようにして、分散コンピュータシステムに含まれる全マシンにおいて、本発明を実施する実行環境内で実行されうるプログラムコードを記述するために、一般的な言語を使用することにより、クライアントおよびサーバは、確定的に並列演算（すなわち同じフレームに属する演算）を複製するように動作可能となり、有利である。
【００５１】
本発明の実行環境内でプログラムの実行を可能にするためには、プログラムは、好ましくは適切に構成されていなければならない。このために、プログラムは、好ましくは、以下の好ましい条件の組を考慮して記述されている必要がある。これらの好ましい条件は、言語で記述可能な内容を制限し、ネットワークでプログラムコードを安全に配布できるように保証する。これらの好ましい条件を以下に挙げる。
【００５２】
（１）プログラムは、ゆるく結合している独立した演算に分割されるように記述され、各演算は、任意の時点において実行状態にあるインスタンスを０以上有する。
（２）各演算インスタンスは、挙動（コード）および状態（データおよび実行ポイント）を有する。
（３）実行が「フレーム」に分割されている。
（４）各フレームについて、システムは、システム内の全演算を順次、１つずつ実行し、「次フレーム」ステートメントに達するまでコードを実行する。
（５）演算間の通信に関して、演算は、他の演算に対する参照を有し、他の演算の状態の読み出しに関与し、自身のローカル状態を変更し、他の演算からメッセージを受信し、他の演算にメッセージを送信しうる。
（６）演算は、他の演算を直接変更することはできず、演算にメッセージを送信し、演算の状態を読み出すことだけができる。
（７）演算がその状態を変えた場合、変更は、演算自身は直ちに認識できるが、他の演算は次のフレームまで認識することができない。
（８）演算は、別の演算を生成することができる。この別の演算は、次のフレームから存在し始める。わかりやすくするために、以下の説明では「演算」をオブジェクトと呼ぶ。しかし、他の形式の演算も同様に使用できることができることが理解されよう。
【００５３】
好ましくは、オブジェクトの各インスタンスの各フレームは、オブジェクトデータとオブジェクト実行ポイントを含む。このため、実行ポイントがエラーであるか終了の場合の演算の終了の場合を除き、どのフレームの始点および終点でも、実行ポイントは「次フレーム（next−frame）」ステートメントとなる。「次フレーム」ステートメントは、フレームで実行される最後の命令である。好ましくは、使用時には、本発明を実施する実行環境は、「次フレーム」ステートメントまで各フレームを実行するように動作可能である。このため、オブジェクトのコードが実行されるときには常に、オブジェクトの状態が反復的に変更される。しかし、好ましい実施形態によれば、反復的な変更および中間状態は他の任意のオブジェクトからは決して認識できず、他のオブジェクトからは、前のフレームの終点における状態しか認識することができない。
【００５４】
プログラムを記述する際にプログラマに課したこの好ましい条件と、実行環境の特徴とにより、ネットワーク内の全てのコンピュータにわたって、コードが矛盾のない確定的な方法で常に実行されるシステムを有利に実現することができる。同じ状態の同じオブジェクトが、２台の異なるコンピュータで、または異なる２つの時点で同じコードを実行した場合、オブジェクトの新しい状態が同じとなる。本発明の特徴のみによって高い確定性を実現できるものの、システムは、浮動小数点演算に関して厳密な正確な規則を規定し、乱数発生器のためのシード値を記憶し、値を常に定義された状態に初期化し、基本型が同じサイズになるように保証し（例えば、整数範囲は一貫していなければならない）、オーバーフロー／アンダーフローの処理が一貫することを保証し、プラットフォームによってプログラムの意味規則（semantics）が変わらないようにする必要がある。
【００５５】
前述のように記述されたプログラムは、有利に分割し、ネットワーク上で実行することができる。本発明の実行環境内での実行に適した言語で記述されたプログラムは、通常オブジェクトのインスタンスのセットから構成される。オブジェクトインスタンスの完全なセットを任意の数のサブセットに分割することは有利となりうる。オブジェクトのサブセットは、システム内の他のコンピュータに、有利に移動または複製することができる。複製されたオブジェクトのサブセットは、サブセットの外部のオブジェクトからサブセット内のオブジェクトへの任意のメッセージを、サブセットのコピーを有する全てのマシンに複製するだけで、対応するフレーム番号に対して、ネットワーク内の全マシン上で同じ状態に同期され、有利である。このため、あらゆるオブジェクトは、各フレームについて状態を変更することができる。フレームには番号が付されうる。このため、「同期」とは、オブジェクトインスタンスがネットワーク内のどのマシンに記憶されていても、任意の所定のフレームについて、オブジェクトのインスタンスが正確に同じ状態にある状態と定義される。ネットワーク内のオブジェクトの全ての複製されたインスタンスを同じ状態に保つことは、特に好ましい実行環境の役割である。言語に関する好ましい条件では、本発明の実行環境による実行のためのプログラムにより、メッセージがサブセットの外部からサブセット内に送られているかどうかを決定できるようにするだけで、システムが、状態の同期が保たれることを保証するために、ネットワークに送る必要のある情報を計算することが有利に容易となる。
【００５６】
実行環境または実行環境の一部（例えば、特定のクライアントマシン内に実施される）は、正しい予測をするための情報の全てが入手可能ではない場合であっても、将来のフレームを先に投機的に実行することが可能となり有利である。システムは、実際の入力データと推測されたデータ（および推測され省略されたデータ）との組み合わせを取得して、現在利用可能な入力情報より前に実行することができる。このことは、レーテンシによりネットワークから送られるデータに遅延が発生している間に、システムが、ローカルのユーザ入力に応答し続けるために有用である。コンピュータは、実際のシステム状態と投機的なシステム状態を保持することができ、このため、ユーザ入力に対して迅速に応答が行われるが、推測されたデータがシステムに恒久的な影響を与えないように保証する。このため、推測された状態が誤っていると判定された場合、実際の状態にロールバックさせることが常に可能である。
【００５７】
プログラム開発で最も時間のかかる段階の１つはプログラムの「デバッグ」をすべき段階である。「デバッグ」とは、エラーまたは「バグ」を特定して修正し、コンピュータプログラムから取り除く工程を指す。デバッガは、プログラムが、通常モードではなくデバッグモードで実行されるようにするソフトウェア部分である。このため、デバッガは、実行中のアプリケーションの内部状態を調べ、主に実行時プログラムエラーの根本的原因を特定するために使用されるアプリケーションである。デバッガは、多くの場合、実行中のアプリケーションのエラーの点で起動されるか、実行中のアプリケーションをエラーが発生するまで実行するテストの場合に使用される。従来のデバッガが提供する主な機能を以下に挙げる。
（１）イントロスペクション−デバッガは、ユーザは、各ステートメントの実行時に、オブジェクトの状態を調べたり、そのステートメントのソースコードを見ることができるようにする。
（２）停止−デバッガは、プログラムの任意の点で、プログラムの実行を停止または中断できるようにする。
（３）対話−デバッガは、ユーザが、ビューによりプログラムの内部状態を調べ、変更し、エラーを修正するために、各種コマンドを発行できるようにする。
【００５８】
プログラムのデバッグは、複雑で時間がかかる作業である。特に、不確定であるプログラムは、所定の入力に対してプログラムが正しく実行されたからといって、二度目に同じ入力によりそのプログラムが正しく実行される保証がないという問題がある。これにより、ａ）特定の状況でのみ発生するため発見が難しい、ｂ）発生状況を正確に再現しなければならないため再現が難しい、ｃ）一部の環境のみにおいて、例えば、開発者のコンピュータでなくエンドユーザのコンピュータのみで起こるバグが発生する。実際、確定的な実行を行わなければ、プログラムのエラーを、必ずしもデバッガ実行環境で再現できるとは限らない。更に悪いことに、異なる環境でプログラムを実行する試験条件の場合、デプロイメント後にようやくエラーが明らかになることがある。
【００５９】
この問題は、ネットワークを介した複数のマシンによる分散実行のために、既にデプロイメントされているかデプロイメントが計画されているプログラムをデバッグしようとする場合に複雑化する。デプロイメント前に徹底的にデバッグされた分散プログラムのデプロイメント後であっても、分散プログラムの提供業者が、開発段階で特定されず修正されなかった、特定のエンドユーザのコンピュータで発生するエラーの修正を求められることがある。これは、特に、プログラムの実行結果が、実行プラットフォームの特定の状況に、ある程度依存するシステムの問題である。
【００６０】
このため、プログラムが実行される状況および環境の依存の少ないデバッグツールを提供することが求められている。
【００６１】
本発明の第４の態様によれば、コンピュータプログラムで発生するエラーを特定するためのデバッガであって、前記デバッガは、コンピュータプログラムの１つ以上のコンポーネントの実行が、複数の連続する実行フレームで実行されるように動作可能な実行環境を有し、前記実行環境は、
ｉ）異なる実行フレームにおける、あるコンポーネントと別のコンポーネント間の通信を許可し、かつ
ｉｉ）同一の実行フレームにおける、あるコンポーネントと別のコンポーネント間の通信を阻止するように更に動作可能であるデバッガが提供される。
【００６２】
本発明の第５の態様によれば、コンピュータプログラムで発生するエラーを特定するためのデバッガであって、前記デバッガは、コンピュータプログラムの１つ以上のコンポーネントの実行が、複数の連続する実行フレームで実行されるように動作可能な実行環境を有し、前記実行環境は、前記コンピュータプログラムのコンポーネント間の通信を所定の順序で処理するように更に動作可能であるデバッガが提供される。
【００６３】
本発明の第４および第５の態様を実施するデバッガの主な利点は、デバッグ工程中にプログラムが実行される環境のフレーム構造の結果、デバッガの実行環境内でデバッグされるプログラムの実行が、高い確定性を示し有利であることにある。このように、実行が行われる場所を問わず、プログラムが同様に実行することが保証される。更に、ある場所（例えばユーザのマシン）でプログラムに提供される入力を記録することで、そのプログラムの実行を、別の場所（例えば開発者のマシン）に有利に再現することができる。
【００６４】
好ましくは、デバッガは、実行中にコンピュータプログラムがユーザによって検査可能にするように動作可能な検査手段を有する。このため、ユーザは、所定のフレーム内でオブジェクトの状態を検査し、これらのオブジェクトの現在の実行点を、ソーススクリプト中のオブジェクトの記述表現と関連付けことができる。デバッガが、実行中のオブジェクトの状態の視覚表示または仮想世界のビューを提供することができるように、表示手段が一般に提供される。
【００６５】
好ましくは、デバッガは、ユーザがコンピュータプログラムの演算と通信できるようにすることによって、実行中のプログラムと対話することを可能にする対話手段を有する。このため、例えば、ユーザは、メッセージの受信後のオブジェクトの実行をテストおよび検査するために、そのオブジェクトにメッセージを送信することができる。
【００６６】
好ましくは、デバッガは、ユーザがフレームにおけるオブジェクトの状態内の値を直接変更可能にするように動作可能な変更手段を有する。これは、ユーザが、デバッグされているプログラムが、異なる値をどのように処理するかをテストできるようにするという点で有利である。
【００６７】
また、デバッガは、後続フレームを作成するように動作可能な手段を有するシミュレーション実行手段も提供しうる。この実施形態によれば、実行環境はフレームを実行し、後続フレームが作成されるように動作可能であり、実行手段は、その後、この後続フレームを実行するように動作可能である。この特徴は、例えば、プログラムが、特定のフレームの変更または修正後に、どのように実行を続けるかを調べるために、ユーザが特定のフレームより前に投機的に実行できるようにするという点で特に有利である。
【００６８】
特に好ましい実施形態によれば、デバッガは、特定のフレームに属する全てのオブジェクト状態を保存可能な保存手段を有しうる。復元手段は、その後の実行のために保存されたフレームの再ロードを可能にする。これにより、ユーザは、あるコード経路をテストし、次に保存されたフレームに戻り、別のコード経路をテストすることができるため、有利である。一部の用途では、本発明の実行環境内でのプログラムの確定的な実行の結果、コードの特定の部分またはセクションに含まれる全てのフレームにおけるオブジェクト状態の履歴を記憶することが有利となり、これにより実行の再現または再生が事実上可能となるが、これは必要でない。具体的には、テストされているプログラムへの入力のログと共に、定期的に（例えば５０フレーム毎または１００フレーム毎など）フレーム状態を保存することが好ましく、これにより、状態の履歴を毎回、事実上再現することができ、状態の履歴を保存する必要がなくなる。
【００６９】
本発明を実施するデバッガはアンドゥ手段を有利に有する。この特徴により、現在の実行状態を以前の特定のフレームに戻すために、フレームまたはフレームの組を破棄できるようになる。これは、その後ユーザが、エラーの原因を特定するために、おそらく実行をゆっくり繰り返すことによって、コードの特定のセクションの状態を再検査できるようにするために、再生手段が提供されうるという点で有利である。アンドゥ手段の操作後、または復元手段によるフレーム状態の復元後に、特定の状態から実行を再生できる能力は、同じ初期の開始パラメータを与えると、プログラムが常に同じように実行することを保証するデバッガ実行環境の確定的な性質の結果得られる。公知の不確定的なプログラムをデバッグする作業を与えられたユーザの不満の１つに、例えば、実行されたフレームが、条件の組を満たしていることを示さなかった場合、または実行中のプログラムによってアサーションの違反が発生した場合に、エラーが明らかになるが、同じユーザ入力を用いて、プログラムを再実行しようとしても、実行がわずかに異なっているために、エラーを再現できないことがあるという点が挙げられる。デバッグツール内で実行を再生する、すなわち正確に複製する能力は、確定性の性質の利益を受けることができない公知のデバッグツールに対する大きな改良である。
【００７０】
商業的視点からいえば、本発明を実施するフレームベースのデバッガにより、分散並行プログラム（例えばオンラインゲーム）を開発およびテストする際の生産性を向上できる。これにより、分散プログラム内のエラーをより迅速に修正できるようになり、有利である。更に、分散型デプロイメントの場合における本発明の特定の利点は、分散プログラムの実行中にプログラムエラーを経験したエンドユーザが、開発者へのバグレポートの一部として、そのユーザのプログラムの実行履歴、おそらくは履歴の再現を可能にするのに十分なデータを送信することができる点にある。この報告は自動的に行われることが考えられる。その後、開発者が、エラーの発生箇所を調べるために、問題を直接再生し、再現することができる。また、開発者は、実装された変更またはコード変更によりエラーが修正されるかどうかをテストするためにコードのセクションを再生することもできる。
【００７１】
本発明の実施形態によれば、バグを発見および修正し、バグ修正をテストする工程が、有利に合理化される。開発者およびテスト担当者の時間をかなり節約することができ、これにより、開発およびサポートのコストを削減することができる。更に、このような効率的かつ有効なデバッグを提供できることは、ユーザの満足度の向上につながる。
【００７２】
上記の態様のいずれにおいても、各種特徴を、ハードウェアで実装しても、１つ以上のプロセッサで実行されるソフトウェアモジュールとして実装してもよい。ある態様の特徴を、別の態様に適用することができる。
【００７３】
また、本発明は、ここに記載する手法を実装するためのコンピュータプログラムまたはコンピュータプログラム製品と、ここに記載する手法を実装するためのプログラムが記憶されているコンピュータ可読記憶媒体を提供する。本発明を実施するコンピュータプログラムは、コンピュータ可読媒体に記憶することができ、例えば、インターネットのウェブサイトから提供されるダウンロード可能なデータ信号などの信号の形式をとっても、他のどのような形式をとってもよい。
【００７４】
本発明をよりよく理解し、これを実施することができる方法を示すために、例示を目的として添付の図面を参照する。
【図面の簡単な説明】
【００７５】
【図１】分散コンピュータシステムのブロック図である。
【図２】オブジェクトのフロー図を示す。
【図３】プログラムの実行の図である。
【図４】２台のネットワーク接続されたコンピュータの模式図であり、その一方に複数のオブジェクトが記憶されている。
【図５】図４のコンピュータの別の図であり、オブジェクトのサブセット（ａ、ｂ、ｃおよびｄ）が第１のコンピュータから第２のコンピュータにコピーされる。
【図６】図５のコンピュータの図であり、第１のコンピュータにおけるメッセージ（ｚ、ｙおよびｘ）が第２のコンピュータに複製されている。
【図７】図５および図６の第２のコンピュータへの別のオブジェクト（ｅ）の追加を示す。
【図８】図７の第２のコンピュータに複製されているメッセージを示す。
【図９】本発明を実施する分散コンピュータシステムを示す。
【図１０】本発明の一実施形態による、デバッガ２１を有するコンピュータシステムに関連する部分を示す。
【発明を実施するための形態】
【００７６】
図１は、複数のユーザのコンピュータ１〜４を、複数のプロセッサ／サーバに分散されているソフトウェアと対話可能にするコンピュータシステムを示す。このシステムには、実行環境、ネットワーク伝送システム（通常はインターネット）、および外部の言語とシステム（「外部世界」）へのインタフェースが含まれる。実行環境は、ユーザのコンピュータとプロセッサ／サーバとに別々に存在しているように示されているが、いうまでもなく、これは模式図に過ぎず、実際には、実行環境がこれらの全てにわたって存在している。ソフトウェアを開発するために、開発コンピュータにコンパイラ（図示なし）が必要である。システムは、通常のデータアクセスモデルを提供している（つまり、プログラマからみた、システム内の全オブジェクトに対するアクセスが等しい）。システム内の全てのデータは、オブジェクトの形をとっている。オブジェクトへの参照は、分散システムのどの部分にあるオブジェクトをポイントしていてもよい。ポインタが、システム内の複数のマシンに複製されているオブジェクトを参照していてもよい。
【００７７】
コンパイラは、オブジェクトの定義を取得し、実行環境で実行するために、これらを命令にコンパイルする。利用可能な実行環境命令には、整数および浮動小数点の値に対する数値演算（浮動小数点演算は、全てのシステムで矛盾なく定義されている必要がある）、整数および浮動小数点の値または他の形式のデータに対する条件操作、現在のオブジェクトの状態を変更するが、次のフレームの他のオブジェクトからしか見えない操作、特定のタイプの新しいオブジェクトの作成（次のフレームのみで利用可能）、他のオブジェクトへの参照の取得とその状態の読み出し、そのオブジェクトの破壊、別のオブジェクトへのメッセージの送信（次のフレームのみで受信される）、受信したメッセージのチェックとその値の読み出し、外部システムによって定義される関数の呼び出し（この関数は、このフレームのシステム状態を変更してはならない）などが含まれうる。
【００７８】
一実施形態によれば、図１に示すシステムの実行環境は、バーチャルマシンとして実装することができる。このバーチャルマシンは、フレームの組を保持している。各フレームは番号を有する。各フレームにはオブジェクトとメッセージが存在する。メッセージは２つのフレームに添付される。メッセージは、あるフレームから送信されて、次のフレームで受信される。バーチャルマシンは、フレーム、オブジェクト、およびメッセージを記憶するためのシステムを有する必要がある。所定の時間において、記憶されている少なくとも１つフレーム（現在の無矛盾フレーム）が存在する。フレームの実行中は、記憶域には、少なくとも２つのフレーム（現在のフレームと次のフレーム）が存在している。オブジェクトは現在のフレームから読み出され、実行された後、次のフレームに書き込まれる。
【００７９】
本発明の第２の態様の原理によれば、メッセージのキューが保持され、これにより、フレームおよびターゲットオブジェクトが与えられると、そのオブジェクトに送信されたメッセージのリストを返すことができる。このため、実行環境は、このキューを保持するように動作可能である。この実施形態によれば、フレームｎから送信されたメッセージはフレームｎ＋１に到着する。このため、好ましくは、各フレームの各オブジェクトに対して、別個のキューを保持しなければならない。無矛盾実行（consistent
execution）を維持するために、メッセージは、あらかじめ定義されたソート仕様を使用してソートされる。ソート仕様が、ネットワーク全体で一貫しており、プログラムの確定性が損なわれないようにメッセージを配列させる限り、ソートの仕様は重要でない。このため、完全に同一の２つのメッセージＡとＢが存在する場合、ＡとＢの相対順序は重要でない。ＡとＢがどのような形であれ区別できる場には、順序が（場合によっては）重要となりうる。メッセージは、フレーム番号を添付されてシステムに送信される。このため、システムは、このメッセージを正しい場所に記憶する。
【００８０】
本発明を実施するシステムは、オブジェクトを特定するためのシステムを提供し、これにより、オブジェクトおよびフレーム番号が与えられると、実行環境は、その記憶域内、またはネットワークの別の位置でオブジェクトを発見することができる。オブジェクトが記憶域内に存在しないが、ネットワークの他の場所で利用可能である場合、実行環境は、ネットワークを介して、オブジェクト状態を要求する要求を送信するように動作可能である。他システム上の実行環境は、この要求を受信し、ネットワークを介してオブジェクト状態を返送するように動作可能である。
【００８１】
本実施形態のシステムは、今後使用されないフレーム、オブジェクトおよびメッセージを破壊するように適合されうる。一般に、無矛盾実行フレームよりも古いフレーム、オブジェクトおよびメッセージは今後必要とされない。また、システムは、オブジェクトの組を保持し、その組に属するオブジェクトとその組の外部のオブジェクトとを迅速に判定するように適合されている。これは、投機的実行およびネットワーク機能に使用される。この点は、後で更に詳しく説明する。
【００８２】
図１のシステムは、あるフレームについて、全てのオブジェクト状態およびメッセージが利用可能となるタイミングを知るように動作可能である。メッセージがネットワークにある別のコンピュータから送信されている場合、システムは、全メッセージの到着が完了したタイミングを特定する必要がある。全てのメッセージが利用可能となるまで、フレームの無矛盾実行が開始されない。また、システムは、１つ以上の投機的実行フレームを保持できる必要がありうる。これは、無矛盾実行フレームより先の別のフレームである。投機的実行フレームは、無矛盾実行フレームから投機的実行フレームまで実行し、失われたオブジェクトまたは利用可能でないメッセージを一切無視することにより生成される。システムは、この実行によって使用された全てのメッセージを元のフレームに保持しなければならない。オブジェクトが自身を破壊すると、そのオブジェクトへの参照の全てが、無効な参照（dead
reference）を明確に定義している状態に変更されうる。これは、オブジェクトが自身を破壊するとき、または使用時に行われうる。参照されていないオブジェクトを破壊することは許されない。このようなオブジェクトは、システムでまだ使用中の可能性がある。
【００８３】
ネットワーク伝送システムは、オブジェクトおよびメッセージを、サイズに応じて配列させて、１つ以上のネットワークパケットにすると共に、パケットをオブジェクトおよびメッセージに分解する逆の手順を実行するように動作可能である。また、個々のフレームに添付されているオブジェクトおよびメッセージを受け取り、これらをローカル記憶域に記憶することも可能である。また、ネットワーク上の他のマシンに複製すべきオブジェクトの組を指定するシステムも実装している。複製される組およびマシンは、リストなどの適切なデータ構造に記憶されなければならない。組の境界を越える全てのメッセージを発見し、そのメッセージを、それを必要としているマシンに送信することが可能でなければならない。ネットワーク上の別のマシンに複製されているオブジェクトの組に対して、ローカルマシン上のオブジェクトから送信されるメッセージは、関連するマシンにも送信する必要がある。現在のフレームについて、ローカルマシンからの全てのメッセージがオブジェクトに送信されると、このフレームについて、このシステムから全てのメッセージを受信していることを通知するメッセージを、この別のマシンに送信する必要がある。これにより、この別のマシンは、現在のフレームのメッセージの待機をやめることができる。ローカルシステムからネットワークプログラミングシステムへのメッセージは、現在の整合ネットワークフレームではなく、現在の投機的なフレームにおいて送信されるとみなされる。すなわち、ユーザから送信されるメッセージは、投機的な状態に適用させ、無矛盾ネットワーク状態が全メッセージを処理するまで、待ち行列に格納されるだけである。
【００８４】
ネットワーク上のマシンの接続が切断される状況を処理するために、タイムアウトが設定され、これにより、マシンが、完全なフレームで充分なメッセージ（worth of messages）を送信しなかった場合には、他のマシンは、当該フレームについて、このマシンからメッセージが送信されないとみなす。このマシンは、当該フレームについてそのマシンのメッセージの全てが、無矛盾ネットワーク状態に受け容れられていないと仮定しなければならないというメッセージの送信を受ける必要がある。時として、全てのフレームについて、オブジェクトの状態をネットワークに繰り返し送信することが必要となり、これにより、ターゲットコンピュータ上の他のオブジェクトが、そのオブジェクトを実行する必要なく、そのオブジェクトの状態を読み出すことができるようになる。これは、メッセージのみが送信される境界が存在しないためである。隣接するオブジェクトの状態を読み出すオブジェクトの連続するシーケンスが存在しうる。このため、隣接するオブジェクトが、ネットワークに繰り返し送信され、これにより、その状態を、マシンによって読み出されているオブジェクトによって読み出すことができる。
【００８５】
外部の言葉およびシステムへのインタフェースは、外部のネットワークプロトコール、メッセージングシステム、関数呼び出しインタフェースにリンクするためのＡＰＩである。外部システムは、特定のタイプの新しいオブジェクトの作成（次のフレームのみで利用可能）、オブジェクトへのメッセージの送信、次のフレームが実行を開始するタイミングの制御、ネットワークに複製されるオブジェクトの組の作成、現在のフレームまでの投機的実行、前のフレームについて受信されたメッセージのネットワークへの送信、特定のフレーム番号のメッセージが今後受信されないことを通知するメッセージを別のマシンが送信した際の通知、システムから呼び出し可能な関数呼び出しの作成（関数呼び出しが、分散システムの実行に影響するように、システムのグローバル状態を変更してはならない。そうでない場合には、ネットワークの整合性が損なわれる）を行うことができる。しかし、この呼び出しは、ユーザに情報を送信し、オブジェクトの状態を読み出すことができる。外部システムは、オブジェクトの状態を変更することはできない。
【００８６】
各オブジェクトは、オブジェクトの生成後に呼び出されるメインプロシジャを有する。メインプロシジャには、例えば、「次フレーム」ステートメントが含まれうる。オブジェクトは自身の状態を変更することができる。しかし、変更された状態は、次のフレームが開始するまで他のオブジェクトからは見えず、このため、コードがオブジェクトのローカルコピーを保持する。オブジェクトによりローカルコピーのみが変更される。この変更されたローカルコピーは、フレームの終点においてオブジェクトによって戻される。実行システムは、この戻された変更されたオブジェクトを、このフレームに提供されているデータ記憶域に記憶し、元のオブジェクトを、元のフレームのためのデータ記憶域に保持する。このため、フレームｎの実行中に、フレームｎ−１を記憶し、各オブジェクトの実行結果をｎに記憶することが必要となる。フレームｎ＋１が実行を開始するまで、フレームｎは読み出されない。
【００８７】
図２は、各オブジェクトのメインプロシジャのフローチャートを示す。ここで、コードフラグメントとは、（１）オブジェクトの生成時、または１つの「next-frame」ステートメントから開始する、かつ（２）フロー図の全ての出口ポイントは、「next-frame」ステートメントまたはオブジェクトの終了である、かつ（３）どのコードフラグメント内にも「next-frame」ステートメントが存在していない、を満たすコード部分であると定義される。各コードフラグメントは関数であり、入力として、フレームｎ−１における参照された全オブジェクトの状態と、フレームｎ−１からフレームｎまでの全てのメッセージをとり、戻り値が、フレームｎにおけるオブジェクトの状態と、フレームｎからフレームｎ＋１までのオブジェクトからのメッセージである。各コードフラグメントは独立した実行可能形式にコンパイルされてもよいが、他の選択肢も可能である。各コードフラグメントの実行可能形式は、１つのエントリポイントを含み、オブジェクトの変更されたバージョンを返し、次のフレームが開始されたときに続行されるコードフラグメントへの参照を返す。実行可能なコードフラグメントは、次のフレームが開始されるまで、他のオブジェクトから見えるデータの変更を行うことができない。データ（例えばローカル変数の値）をあるフレームから次のフレームに保持するために、ローカル変数の値を記憶するためのスタックフレームがヒープに作成されうる。
【００８８】
実行はフレームに分割される。各フレームについて、システムは、システム内の全オブジェクトを順次、１つずつ実行する。オブジェクトをアウトオブオーダーまたは並列に実行することが完全に可能である。各オブジェクトは、そのオブジェクトのデータ量および実行ポイントを含む状態を有する。オブジェクトの生成時には、実行ポイントはオブジェクトのメインプロシジャの始点にある。オブジェクトのメインプロシジャの実行が「次フレーム」ステートメントに達すると、そのフレームでの当該オブジェクトの実行が停止する。フレームの終点で、新しいオブジェクト状態が記憶される。オブジェクトのコードの実行中に、メッセージが生成されうる。このメッセージは、キューに格納され、ターゲットオブジェクトに添付する必要がある。メッセージを読み出せるのは、次のフレームのターゲットオブジェクトだけである。メッセージは、後述するように、ネットワークに送信する必要がありうる。また、オブジェクトがメッセージを読み出すことがある。メッセージは、確定的な順序で読み出される必要がある。これは、複数のシステムでアウトオブオーダー実行および並行実行を可能にするためである。順序は、システムによって定義することができ、ここには記載しない。フレームの終点では、全ての未使用のメッセージが破棄されうる。全ての変更されたオブジェクトが変更され、フレーム番号が１だけインクリメントされる。実行が次のフレームに続けられうる。
【００８９】
オブジェクトのコードを実行する前に、（このフレームについて）、システム内（すなわちネットワーク全体）のあらゆるオブジェクトからの全てのメッセージ、またはこのオブジェクトが参照する他のオブジェクトの状態が利用可能でなければならない、ということを知っている必要がある。そうでない場合には、投機的実行が望ましいこともある。この場合、オブジェクトおよびそのフレーム番号を記憶する必要があり、必要な情報の全てがなくても、実行を続けることができる。しかし、オブジェクトは「投機的」とマークされる必要があり、必要な情報が全て入手できたときに、このオブジェクトに再び戻って、これを正しく再実行する必要がある。
【００９０】
図３は、ａ〜ｄで示される４つのオブジェクトを含むシステムの実行を示す。フレームｎにおける状態は既知であり、フレームｎの実行によってｂからａへのメッセージが生成されている。フレームｎ＋１では、オブジェクトｃが、オブジェクトｂとｄからデータを読み出す。フレームｎ＋２では、オブジェクトａが、オブジェクトｃからデータを読み出す。図３から、同一フレーム内ではオブジェクト間の依存関係が存在しないことがわかる。メッセージの依存関係は、あるフレームから次のフレームにしか存在せず、読み出しの依存関係は、現在のフレームから前のフレームにしか存在しない。これにより、システムが並列に、ネットワーク全体で実行されることが可能となる。この図には、ａがフレームｎ＋１まで計算され、ｂが無視される部分実行が示されている。これは、現在の無矛盾ネットワーク状態を越えて実行し、投機的な状態（正しい入力データと推測された入力データとの組み合わせに基づく）を計算することが可能であることを示している。しかし、後から、フレームｎ＋１においてｂがａにメッセージを送信することがわかった場合、フレームｎ＋１でのａの実行が誤っている可能性があり、再計算が必要なことがある。
【００９１】
各フレームでの各オブジェクトのコードは、前のフレームにおいて参照された全オブジェクトの値と、オブジェクトによって受信された全メッセージの関数とであると考えることができる。このため、フレームｎにおけるオブジェクトと、フレームｎからフレームｎ＋１までのメッセージがシステム全体で矛盾がなければ、フレームｎ＋１における全オブジェクトの状態と、フレームｎ＋１からフレームｎ＋２までのメッセージは、システム全体で矛盾のないデータの関数となる。このため、初期状態と最初のメッセージが矛盾なく、関数が矛盾のない状態で実行されている限り、オブジェクトは矛盾のない状態に保たれる。確定性を実現するために、オブジェクトの初期状態と最初のメッセージは、システム全体に矛盾なく転送される。また、関数の実行も一貫している。このため、言語によって定義され、ローカルバーチャルマシンによって実行される全てのオペレーションは、一貫して定められた挙動を有する必要がある。浮動小数点演算は矛盾のない結果を与える。全てのデータ値は初期化される。破壊されているオブジェクトを参照することはできない。破壊されたオブジェクトに応答するアクションは一貫している。破壊されたオブジェクトを参照しようと試みることは可能であるが、必ずエラーとならなければならない。言語のエラー処理は一貫した方法で実行され、同じエラーに対して、あるマシン上のプログラムが、別のコンピュータ上のプログラムと異なる応答をしてはならない。
【００９２】
オブジェクトは、ネットワークに複製することができる。すなわち、所定のフレーム番号について、ネットワーク上のあるマシンのオブジェクトが、別のマシン上のオブジェクトと全く同じ状態を有するということである。異なるコンピュータの複数のユーザが同じグローバル状態を参照および変更できるようになるため、これは、システムの好ましい目的である。例えば、これにより、コンピュータゲームの多数のプレーヤが、同じゲーム世界でプレイし、対話できるようになる。各プレーヤは、プレーヤのクライアントマシンに作成されるオブジェクトであり、他のプレーヤのマシンおよび（ほぼ確実に）ゲームサーバに複製される。ゲーム世界は、全プレーヤのマシンに複製される。ゲーム世界が全プレーヤが対話するには大きすぎる場合、ゲーム世界の部分集合がプレーヤマシンに複製されうる。この方法は、フレームｎにおけるオブジェクトの状態が与えられると、ネットワーク全体で矛盾なく、フレームｎ＋１のオブジェクトの状態を計算することが可能であるという点に基づいている。
【００９３】
図４〜６は、複数のコンピュータにオブジェクトを複製するための手法を示す。ここでは、７つのオブジェクトの組（ａ〜ｇ）を有するコンピュータＡにある４つのオブジェクトを、オブジェクトが存在しないコンピュータＢに複製しようとしている。オブジェクト間でメッセージが送信されており、オブジェクト間を結ぶ黒い矢印で示される。オブジェクト複製するために、最初に所望のオブジェクト（通常はオブジェクトのサブセット）が選択される。本例では、オブジェクトａ、ｂ、ｃ、ｄが選択される。次に、開始する特定の複製フレーム番号が選択される。「複製フレーム番号」とは、複製の始点となるフレームの番号である。複製されるオブジェクトの各組について、複製フレーム番号を記憶する必要がある。オブジェクトは、複製フレーム番号から先は、同期した状態で存在するようになる。つまり、（複製フレーム番号後の）任意のフレーム番号において、２台のコンピュータのオブジェクトの状態が等しくなるということである。
【００９４】
図５に示すように、複製フレーム番号において、選択されたオブジェクトの状態がネットワークを介してコンピュータＢに送信される。コンピュータＡとコンピュータＢは、複製フレーム番号から続いており、同期された状態を保つことができる。複製されたオブジェクトの組がコンピュータＢに複製されて存在している限り、コンピュータＡとコンピュータＢは、複製されたオブジェクトの組を覚えていなければならない全ての後続のフレームについて、コンピュータＡとコンピュータＢは、サブセットの境界を越える全てのメッセージを検出しなければならない。このようなメッセージが図７に示されている。サブセットの完全に境界外のメッセージまたは完全に境界内のメッセージは、ネットワークに送信する必要はない。本例では、メッセージｘ、ｙ、ｚをネットワークに送信する必要がある。サブセットの外からサブセット内に送られるメッセージを送信するだけでよい。コンピュータＢでは、サブセットからコンピュータＢには存在しないオブジェクトに送られるメッセージは破棄することができる。
【００９５】
オブジェクトａは、メッセージの送受信を行わなくてもオブジェクトｅの状態を読み出すことが可能であるため、時として、全てのオブジェクトの状態をネットワークに送信することが必要となりうる。これは効率が悪い可能性がある。このため、最適なシステムは、サブセットの境界を越えるオブジェクトのアクセスと、メッセージの交換の量を最小限に抑えるように、ネットワークに複製するオブジェクトのサブセットを選択する。これは、必要に応じて、オブジェクトを追加したり、複製された組から削除することによって、動的に実現することができる。
【００９６】
オブジェクトｅを複製サブセットに追加すべきであるとシステムが判断した場合、サブセットが、図８に示すようにオブジェクトｅを含むように拡張され、オブジェクトｅがネットワークに送信される。オブジェクトｅがサブセットに追加されると、ｅとサブセットの他のメンバ間のメッセージをネットワークに送信する必要がなくなる。しかし、図８に示すように、ｅとサブセットのメンバでないオブジェクト間のメッセージは、ネットワークに送信する必要がある。同じシステムを、コンピュータＢにあるオブジェクトをコンピュータＡに複製するのに使用することができる。
【００９７】
ネットワークでソフトウェアを実行している場合、ネットワーク上のあるマシンで行われた変更と、ネットワーク上の別の全マシンに伝達される変更との間に、遅延（またはレーテンシ）が生ずる。ユーザとの即時の対話機能を維持するために、現在わかっているネットワーク状態を越えて実行することが時として必要となる。しかし、後から、この即時応答を正しいネットワーク状態によって訂正し、ネットワーク内の異なるマシン間にばらつきが生じないようにすることが重要である。本発明によれば、これは、２つの状態を保持することによって実現される。一方の状態は確定的ネットワーク状態であり、もう一方は、投機的な現在の状態である。確定的ネットワーク状態がフレームｎであり、ユーザがフレームｎ＋ｍでデータを入力している場合、投機的な現在の状態の計算は、フレームｎからフレームｎ＋ｍまでシステムに送られた全メッセージをキューに格納し、投機的な現在の状態を一時的記憶域にコピーして、ｍ個のフレームについて、キューに格納したメッセージを使用して、一時的に格納された状態を実行することによって行われる。キューに格納したメッセージは、確定的ネットワーク状態が１フレーム先に移動するまで保持する必要がある。確定的ネットワーク状態によってメッセージが空になると、メッセージを破棄することができる。このシステムは、ネットワークレーテンシを処理するための汎用の投機的実行システムを提供する。ネットワークレーテンシを処理するための既存のシステムは、通常、システム内の各タイプのオブジェクトのために特別に記述した予測ソフトウェアを必要とする。このため、通常、プログラマは、ネットワークシステムに投機的予測を実装する方法を考察しなければならず、そうしなければ、ユーザの対話で多くのレーテンシが発生してしまう。これに対して、本願の発明では、ネットワークレーテンシを処理するためにプログラマが特別なことを行う必要がない。
【００９８】
投機的な予測手法を実装するために、以下のコンポーネントが好ましい。
−確定的ネットワーク状態のためのフレームカウンタ（確定的ネットワーク状態を１フレーム先に移動できる前に、確定的ネットワーク状態フレームのための全メッセージが、システム内の全マシンから受信されていることがわかっていなければならないため）
−確定的ネットワーク状態以降、受信されたメッセージのキュー。これは、ローカルシステムから受信されたメッセージと、ネットワークから受信された任意のメッセージから構成される。
−確定的ネットワーク状態を、一時的記憶域にコピーする機能。これが投機的な現在の状態となる。
−メッセージがなくなるまで、一時的記憶域を実行する機能。
−オブジェクトを投機的に実行する機能。この結果、オブジェクトの値が入手できない場合に、この値が推測される。メッセージが入手できない場合は、メッセージが送信されなかったと仮定される。
−ユーザへの表示のために、投機的な現在の状態を使用する機能。
これには、メモリにいくつかの異なるフレームを保持するための記憶手段が必要となる。確定的ネットワーク状態は、常にメモリに保存しなければならない。
【００９９】
図９は、１つの論理サーバとして機能する第１のサーバマシンＳ１および第２のサーバマシンＳ２と、３台のクライアントマシンＸ、ＹおよびＺとを含む分散コンピュータシステムを示す。サーバは、オブジェクト１〜３２を並列に実行しており、処理がサーバマシンＳ１とサーバマシンＳ２間で共有されている。実行時システムを提供するためのシステムの各実行環境は、本発明を実施する実行環境での実行のために同じ言語で記述されたプログラムコードまたはスクリプトを実行することができる。これにより、ユーザがプログラムに参加できるように、プログラムオブジェクト１〜３２の１つ以上が、各クライアントマシンＸ、ＹおよびＺのそれぞれの実行環境Ｅｘ、ＥｙまたはＥｚによって実行されるために複製されることが保証される。
【０１００】
クライアントマシンＸの場合、実行環境Ｅｘは、クライアントマシンＸがサーバに接続した後に、そこからダウンロードされたブラウザプラグインによってクライアントのウェブブラウザ内に実装されている。クライアントマシンＹは、例えば、必要な実行Ｅｙを実装するマシンのオペレーティングシステムの一部として、ソフトウェアがインストールされている。更に、クライアントマシンＺの場合、実行環境Ｅｚは、ブラウザが対応している言語で記述され、プログラムオブジェクト１〜３２の１つ以上の実行を複製するように動作可能なアプリケーションを有する。
【０１０１】
図１０は、本発明の一実施形態による、デバッガ２１を有し、一般的に符号２０で示すコンピュータシステムに関連する部分を示す。コンピュータシステムは、デバッグされるプログラムのプログラムコードを実行するための実行環境２８、エラーに対してオブジェクトの状態を詳しく検査することができるように、オブジェクトの実行状態をユーザに視覚表示するために、表示手段２３と協調して動作可能な検査手段２２、現在のフレームの状態を保存するための保存手段２４a、その後の実行のために、保存されたフレームを復元するための復元手段２４b、実行状態を特定のフレーム状態に戻すために、ユーザによって指定されたフレームに対してフレームを破棄するように動作可能なアンドゥ手段２５、ならびにユーザがフレーム内のオブジェクトの状態に関する値を変更可能にするように動作可能な変更手段２６を有する。ユーザとデバッガ２１の間のインタフェースとして、入力手段がキーボードの形で設けられている。
【０１０２】
オブジェクトＡ〜Ｅを並列に実行している実行環境２８の構造および規則により、実行環境２８は、プログラム部分の確定的な実行を可能にするように動作可能となる。このため、この実行環境は、特定のプログラム部分またはコード経路の実行を、アンドゥ機能を使用して遡って実行し、再生できるようにするという点で有利である。
【０１０３】
プログラムでエラーが発生した場合、プログラムの本当のエラーの原因は、エラーに気付くかクラッシュが発生する点よりも、プログラムの実行においてかなり前に発生していることが多いという点に留意されたい。本実施形態の利点は、デバッガ実行環境の確定的な性質により、ユーザが、エラーに気付くかクラッシュが発生する前のプログラム状態を再現するために、アンドゥ機能を使用して、プログラムの実行を段階的に戻ることができ、プログラムの状態をより詳細に検査するために、実行を再生することもできることにある。これにより、プログラムのエラーの真の原因を、より容易かつ迅速に特定できるようになる。更に、最初のエラーを出現させるのに必要な、全く同じ再生データを使用して、エラーの可能な修正をテストすることができる。
【０１０４】
図Ｘに示すデバッガの使用中の代表的な手順には、以下のステップが含まれる。
１．ユーザがデバッガ２１を起動し、デバッグするプログラムをロードする。
２．ユーザは、プログラム状態の視覚表示を監視するか、またはプログラムに参加しながら、デバッガ２１を前方に実行させる。
３．ユーザは、デバッグ対象のプログラムがエラー状態になったことを発見する。
４．ユーザは検査手段２２によってプログラムの現在の状態を検査し、エラーの原因を確認する。
５．ユーザは、現在のフレームを破棄し、前のフレームに戻るために、アンドゥ手段２５を操作する。
６．ユーザは、エラーをより詳細に検査するために、以前の実行で記録された入力を使用して、再びそのフレームの実行を再生する。
７．ユーザは、検査手段２２およびディスプレイ２３を使用して、プログラムの状態を検査し、エラーの直前の状態を調べる。
８．エラーを含むフレームが特定されると、ユーザはそのフレームを破棄して、前のフレームに戻る。
９．ユーザは、問題の可能な修正をテストのために、エラーの発生前のフレームに含まれるオブジェクトの状態の１つ以上の値を変更するために、変更手段２６を操作する。
１０．ユーザは、変更したフレームを実行し、アサーションがトリガされるかどうか監視する。トリガされない場合、エラーの位置および原因が特定されている。
【０１０５】
本発明の好ましい実施形態により、ある非常に強力な動作が可能となる。フレームの概念により、同期および依存関係の扱いが容易になり、完全に確定的なシステムを提供することが可能となる。つまり、プログラムが同じ入力により同じようにふるまうようになる。関与しているコンピュータの台数、異なるコンピュータにプログラムの要素を分散させた方法、操作の完了までに要する時間は問わない。プログラムは、常に同じように実行する。より容易に繰り返すことができるように、入力を記憶することができる。また、全てのオブジェクトが常に並列に実行されることも保証される。システムは、通信ボトルネックを最小限に抑えるために、分散システムのコンピュータ内でのオブジェクトの分散を自動でまたは手動で適用してもよい。メモリボトルネックを低減することができるように、メモリが２台のマシン間で複製されてもよい。
【０１０６】
更に、本発明は、ネットワーク上での矛盾のない実行を実現する。これにより、ネットワーク上のオブジェクトの２つのコピーが同じメッセージを受信することを保証するだけで、これらが所定のフレーム番号に関して同期されるようになる。この結果、この２つのオブジェクトが変化したときに、ネットワークを介して常時コピーする必要がなくなる。これにより、必要なネットワーク帯域幅が低減され、性能が向上する。更に、本発明により、オンラインゲームに必要とされる概念である投機的実行が可能となる。投機的実行は、ネットワークの矛盾を引き起こしかねない大きなリスクとなる。ほかのネットワークゲームシステムでは、プログラマが投機的実行を実現する方法を考えるように求められる。これに対し、システムが安全かつ意識せずに投機的な予測を実行することができるという点で、本発明の好ましい実施形態は有利である。
【０１０７】
本発明の実施形態は、どのような高度に並列または分散型のスケーラブルなソフトウェア（例えば膨大な数のプレーヤが参加するオンラインコンピュータゲーム）にも使用することができる。これは、マルチコアプロセッサ、またはグリッド上の高性能コンピューティング、多数のユーザが参加する大規模システムのプログラムにも同様に使用することができ、あるいは、ネットワーク上でスケールアップする必要のある既存のソフトウェアのためのグルーシステムとして機能する。本発明は、矛盾なく確定的な評価順序（order
of evaluation）を提供するため、プログラムを、分散または複製が可能なセクションに安全に分割できるようになる。
【０１０８】
本発明が実施されるシステムを使用することにより、インタラクティブに使用された場合に、即時のフィードバックがユーザに提供されるようになる。システムは、安定したユーザ対話を維持するために、投機的な予測を使用する。また、システムは、ネットワークレーテンシが発生していても、システム全体で一貫した、現実の無矛盾状態を維持する。しかし、システムの各マシンは、システム内の他の全てのコンピュータから必要な全情報を受信した後でなければ、現実の無矛盾状態を計算することはできない。現実の無矛盾状態は、投機的な予測された状態によって生じた誤りを修正するために使用される。
【０１０９】
本発明をいくつかの実施形態および実施例で説明し記載したが、本発明の原理から逸脱することなく、本発明を、さまざまなに変更、実施、補足または適用することができることは明らかであろう。本発明は、携帯可能な記憶媒体に記憶されるか、デジタル通信または他の伝送媒体によって送信されるか、またはコンピュータメモリに記憶されるソフトウェアプログラムおよびデータ構造に実装することができるこのようなプログラムおよびデータ構造は、本発明を実施する方法を実行するため、およびここに記載した機能を有するマシンまたは装置の一部として動作させるために、コンピュータ上で実行することができる。
【図１】
2009541892.tif 000003
【図２】
2009541892.tif 000004
【図３】
2009541892.tif 000005
【図４】
2009541892.tif 000006
【図５】
2009541892.tif 000007
【図６】
2009541892.tif 000008
【図７】
2009541892.tif 000009
【図８】
2009541892.tif 000010
【図９】
2009541892.tif 000011
【図１０】
2009541892.tif 000012
【国際調査報告】
2009541892.tif 000013
2009541892.tif 000014
2009541892.tif 000015
2009541892.tif 000016
2009541892.tif 000017