(57)【要約】【課題】通信遅延が起こりうるプロセスの間のデータ通信を可能にし、データ通信の順次整合性を達成する方法を提供すること。【解決手段】「コミット−同期」実行モデルを使用してデータ通信の順次整合性を達成する方法であって、この方法が、− コミットコマンドによって、第一プロセスから中間オブジェクトまたはその一部にデータを伝送するステップと、− 中間オブジェクトまたはその一部のインジケータを、データが第二プロセスによって受信されるかまたはアクセスされるという指示に設定するステップと、− 同期コマンドによって、中間オブジェクトからのデータを第二プロセスによって受信するかまたはアクセスするステップと、− 中間オブジェクトまたはその一部のインジケータを、データが第二プロセスによって受信されないかまたはアクセスされないという指示に設定するステップ、を有し、− コミットコマンド、および／または、同期コマンドに、それぞれ、データが中間オブジェクトに伝送されるときの方法、および／または、中間オブジェクトから受信されるかまたはアクセスされるときの方法を示すための１つの以上のパラメータが設けられている、方法。【選択図】図１
2005507522.tif 000002
【特許請求の範囲】
【請求項１】
「コミット−同期」実行モデルを使用してデータ通信の順次整合性を達成する方法であって、以下のステップ、すなわち、
− コミットコマンドによって、第一プロセスから中間オブジェクトまたはその一部にデータを伝送するステップと、
− 前記中間オブジェクトまたはその一部のインジケータを、データが第二プロセスによって受信されるかまたはアクセスされるという指示に設定するステップと、
− 同期コマンドによって、前記中間オブジェクトからの前記データを前記第二プロセスによって受信するかまたはアクセスするステップと、
− 前記中間オブジェクトまたはその一部の前記インジケータを、データが前記第二プロセスによって受信されないかまたはアクセスされないという指示に設定するステップと、
を有し、
− 前記コミットコマンド、および／または、前記同期コマンドに、それぞれ、前記データが前記中間オブジェクトに伝送されるときの方法、および／または、前記中間オブジェクトから受信されるかまたはアクセスされるときの方法を示すための１つの以上のパラメータが設けられている、
方法。
【請求項２】
データを伝達するための前記中間オブジェクトが、1つの送信側プロセスと1つの受信側プロセスとに関連付けられている、請求項1による方法。
【請求項３】
前記中間オブジェクトまたはその一部において実行される操作が、自動的である、請求項1による方法。
【請求項４】
前記パラメータが、どのデータがどの中間オブジェクトまたはその一部によって扱われるかを指定する、請求項1による方法。
【請求項５】
受信側操作が、任意の中間オブジェクトまたはその一部にアクセスすることができる、請求項1による方法。
【請求項６】
受信側操作が、伝送側操作がデータを送信した先の中間オブジェクトまたはその一部にアクセスすることができる、請求項1による方法。
【請求項７】
受信側操作が、伝送側操作によってデータが送信されていない中間オブジェクトまたはその一部にアクセスすることができる、請求項1による方法。
【請求項８】
受信側操作が、伝送側操作がデータを送信した先のすべての中間オブジェクトまたはその一部に最終的にアクセスする、請求項1による方法。
【請求項９】
受信側操作が、データを送信した伝送側プロセスに、前記データの受信を報告する、請求項1による方法。
【請求項１０】
プロセスが、伝送中に処理を続行する、請求項1による方法。
【請求項１１】
プロセスが、伝送操作と受信操作とを管理するインタラクションマネージャを使用する、請求項1による方法。
【請求項１２】
複数の伝送操作が、1つのプロセスによって実行される、請求項1による方法。
【請求項１３】
インジケータが、伝送が開始されたときに別の伝送が進行中でなかった場合に、前記伝送の後ただちに設定される、請求項1による方法。
【請求項１４】
それぞれがプロセッサと少なくともいくらかのメモリとを含んでいる1つ以上のコンピューティングデバイス上で実行されている2つ以上のプログラムスレッドの間でデータを交換する方法であって、当該方法が、以下のステップ、すなわち、
− 当該プログラムスレッドのうちの第一スレッドが、当該スレッドの間の関係を定義するために契約ソフトウェアコンポーネントを実行するステップと、
− 当該第一プログラムスレッドと1つ以上の第二プログラムスレッドそれぞれが、当該契約ソフトウェアコンポーネントの前記定義された関係に基づいて、それぞれの契約ソフトウェアオブジェクトを作成するステップと、
を有する、方法。
【請求項１５】
当該スレッドの間の前記定義された関係が、前記契約ソフトウェアコンポーネントのインスタンス化である、請求項14による方法。
【請求項１６】
プログラムスレッドごとに契約ソフトウェアオブジェクトが作成される、請求項14による方法。
【請求項１７】
当該契約ソフトウェアオブジェクトを作成しかつ動作させるための必要な手段を割り当てることによって、データを交換するための前記方法を使用する各スレッドに対して契約ソフトウェアオブジェクトが作成される、請求項14による方法。
【請求項１８】
前記契約ソフトウェアオブジェクトと、当該スレッドの間の前記関係が、1つの論理オブジェクトである、請求項14による方法。
【請求項１９】
プログラムスレッドが、第二スレッドの第二契約ソフトウェアオブジェクトによって前記第二スレッドにデータを伝えるために、第一契約ソフトウェアオブジェクト上でローカルに動作する、請求項14による方法。
【請求項２０】
当該1つの論理オブジェクトの当該第一契約ソフトウェアオブジェクト上のローカル操作が、当該第一契約ソフトウェアオブジェクトのコミット操作の後にグローバルになる、請求項14による方法。
【請求項２１】
当該1つの論理オブジェクトの当該第一契約ソフトウェアオブジェクトのグローバル操作が、第二契約ソフトウェアオブジェクトによる同期操作の呼び出しによって、当該第二契約ソフトウェアオブジェクトに対して効力を発する、請求項14による方法。
【請求項２２】
請求項14による方法を使用する、請求項1による方法。
【請求項２３】
中間オブジェクトまたはその一部がコネクタである、請求項1〜22の1つまたは複数による方法。
【請求項２４】
請求項1〜23の1つまたは複数による方法を実行するコンピュータシステムであって、少なくとも1つのプロセッサと1つのメモリとを有する、情報を交換する必要のある少なくとも2つの平行するプログラムスレッドを実行している少なくとも1つのコンピューティングデバイスを有する、コンピュータシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、順次整合性を保証する方法に関する。本出願と同じ出願人による米国特許第6,182,152号（社内整理番号PHN015645）は、プロセス内更新操作とプロセス間適合化操作によって、同時に起こる順次プロセスを同期する方法およびシステムを開示しており、これは、いくつかのプロセッサが単一のコンピュータまたは類似する機器上で動作しているときの、プロセス内データ通信の場合には、良好に機能する。
【０００２】
さらに、本発明は、「二段階ロック」を使用する通信プロトコルに関する。しかしながら、二段階ロックプロトコルは、最終的にデッドロックになることが知られており、相対的に効率が低い。
【特許文献１】
米国特許第6,182,152号
【特許文献２】
ヨーロッパ特許出願第01204139.8号
【発明の開示】
【課題を解決するための手段】
【０００３】
本発明は、「コミット−同期（commit−sync）」実行モデルを使用してデータ通信の順次整合性を達成する方法であって、当該方法が、
− コミットコマンドによって第一プロセスから中間オブジェクトまたはその一部にデータを伝送するステップと、
− 前記中間オブジェクトまたはその一部のインジケータを、データが第二プロセスによって受信されるかまたはアクセスされるという指示に設定するステップと、
− 同期コマンドによって、前記中間オブジェクトまたはその一部からの前記データを前記第二プロセスによって受信するかまたはアクセスするステップと、
− 前記中間オブジェクトまたはその一部の前記インジケータを、データが前記第二プロセスによって受信されないかまたはアクセスされないという指示に設定するステップ、
を有し、
− 前記コミットコマンド、および／または、前記同期コマンドに、それぞれ、前記データが前記中間オブジェクトに伝送されるときの方法、および／または、前記中間オブジェクトから受信されるかまたはアクセスされるときの方法を示すための１つの以上のパラメータが設けられている、
方法、を提供する。
【０００４】
本発明による実施例は、通信遅延が起こりうるプロセスの間のデータ通信を可能にする。この通信遅延は、1つ以上のコンピュータネットワークによって相互接続されているいくつかのコンピューティングデバイス上でプロセスが動作する場合にしばしば起こる。
【０００５】
データが中間オブジェクトによってどのように扱われるかを示すパラメータを使用することは、データの受信またはアクセスを選択的な方法において行うことができるという利点を持つ。このようなパラメータ化された受信操作（SYNC）では、プロセスは、以前に伝送されたデータのうち中間オブジェクトによって示された、選択されたデータのみを、インジケータを用いて「同期」することが可能になる。この方法によるデータ通信は、接続しているデータ通信ネットワークによって少なくとも公平さ(fairness)の要件が満たされていれば、順次的に整合的である。公平さの要件は、すべての中間ネットワークノードが信頼できる、すなわち伝送のプロセスにおいてデータまたはデータ通信が失われないこととして定義される。この方法が機能するための唯一の要件が公平さであることは、非常に有利である。なぜなら、任意の相互接続ネットワークを、通信またはメッセージが失われない限りは、サービスの速度または品質などのネットワークパラメータを無視して使用することができるためである。
【０００６】
別の好ましい実施例においては、同期操作は、中間オブジェクトまたはその一部にアクセスするためのパラメータを含むことができる。これらのパラメータのうちのインジケータは、データが受信されないかまたはアクセスされないことを示す。
【０００７】
本発明によるさらなる実施例の場合、第二プロセスまたは受信側プロセスは、データを送信した伝送側プロセスに、データの受信を報告する。この利点は、送信側プロセスが、メッセージが到着したことを認識することであり、もう1つの利点は、送信者が、通信に使用される中間オブジェクトまたはその一部が再び「空き」であることを認識する。このことは、中間オブジェクトまたはその一部のインジケータが、データが第二プロセスによって受信されないかまたはアクセスされないという指示に設定されることを意味する。もう1つの効果は、その中間オブジェクトまたはその一部が、新しい「COMMIT（コミット）」用に「空き」であることである。
【０００８】
別の実施例においては、プロセスは、伝送している間、動作を続行する。コミット操作は、中間オブジェクトまたはその一部に含まれているグローバル変数に影響するが、コミット操作を実行しているプロセスに直接的には影響しない。例えば、コミット演算子は、プロセスの実行に影響しうる値を戻さず、同期を目的としてプロセスを遅延させる必要もない。このことは、プロセスがコミットアクションを実行する場合、そのプロセスはコミットアクションを一種の「バックグラウンドタスク」として扱うことができ、単純に通常の実行を続行する。このアクションがローカルアクションである限りは、次のアクションを実行する前にコミット操作が完了するまでブロックする必要はない。
【０００９】
別の実施例においては、プロセスは、伝送操作と受信操作を管理するインタラクションマネージャを使用する。COMMITがバックグラウンドで実行されており、このプロセスが別のCOMMITを実行してかつ自身の実行を続行する必要がある場合、システムは、現在実行されているCOMMITの後に別のCOMMITを実行する必要があることを、何らかの方法で記録する必要がある。これは、以降に実行されるCOMMITを追跡する「インタラクションマネージャ」を導入することによって対処することができる。このインタラクションマネージャは、SYNCの実行を管理するために使用することもでき、従ってインタラクションの実行に関する責任が1つの権限に移される。プロセスごとに個別のインタラクションマネージャを使用することは、プロセス自体がそのインタラクションを最適化するためにネットワークのトポロジとパフォーマンスに関する知識を持つ必要がないという利点を有する。この責任は、インタラクションマネージャに局在化される。プロセスは、COMMITコマンドとSYNCコマンドをインタラクションマネージャに与えるのみであり、インタラクションマネージャは、COMMITとSYNCの実行において許可される特権を使用して、これらのコマンドを最適な方法において扱う。インタラクションマネージャは、同じネットワークノードに属すプロセス間の通信を最適化するために使用することもできる（分散されていない場合）。
【００１０】
別の実施例においては、複数の伝送操作が、1つのプロセスによって同時に実行される。このための前提条件は、同時のCOMMIT操作によって使用される一連の中間オブジェクトまたはその一部が、互いに分離している(disjoint)ことである。論理的には、COMMITは次のCOMMITが実行される前に完了している必要があるが、インタラクションマネージャは、必要なデータを中間オブジェクトまたはその一部のそれぞれの受信者に送信することによって、完了前に次のCOMMITの実行を開始させることができる。当然ながら、最後のCOMMITを完了させる前には、論理的に先行しているCOMMITすべてが完了している必要がある。中間オブジェクトまたはその一部においてCOMMITが進行中であり、同じ中間オブジェクトまたはその一部が関連している別のCOMMITが開始を許可されるならば、中間オブジェクトまたはその一部の受信側において、場合によっては無制限の量のデータをバッファリングする必要があるが、これは望ましくない。従来、このプロトコルでは、バッファリングがまったく必要とされない。従って、本発明では、COMMITの重複実行は、それらのCOMMITに関連している一連の中間オブジェクトまたはその一部が互いに分離している場合にのみ許可される。このことは、個々の中間オブジェクトまたはその一部それぞれにおいて最大で1つのCOMMITを進行させることができることを意味する。
【００１１】
さらなる実施例においては、前記インジケータは、伝送が開始されたときに別の伝送が進行中でなかった場合に、前記伝送の後ただちに設定される。
【００１２】
本発明のさらなる観点は、同時出願中のヨーロッパ特許出願第01204139.8号（社内整理番号PHNL010785）による分散ソフトウェアコンポーネントと組み合わせて、本発明による方法を使用することに関する。両方のコンセプトの方策を組み合わせることは、分散されているコンポーネントの挙動を、その分散の程度と無関係にすることができるという利点を持つ。言い換えれば、組み合わされた方策によって、メッセージの遅延を考慮することなくシステムを設計することができる。このことは、システムが分散状況においても機能上は「瞬間的なメッセージング」が適用されているかのように動作することを保証する。
【００１３】
本発明のさらなる利点、特徴、および詳細は、添付されている図面を参照しながら、本発明の好ましい実施例の以下の記述に照らして説明されるであろう。
【発明を実施するための最良の形態】
【００１４】
実施例（図1）においては、2つのプロセス2、4は、動作している間、データを交換する必要がある。この目的のため、これらのプロセスは、コネクタ6、8を論理的に利用する。2つのコネクタが図示されているが、両方の方向にコネクタの配列を利用することができる。このような配列は、コネクタ6についてはXiとして、コネクタ8についてはYiとして記述することができる。コネクタには、インジケータ（フラグ）16、18が設けられている。コネクタ6、8は、プロセスが通信する論理モデルを表しているが、物理的なデータ通信は、インタラクションマネージャ12、14と1つ以上のデータ通信ネットワークNとを使用して実行される。図6の実施例においては、インタラクションマネージャ12、14は、共通クライアント111、112、113、114の一部であり、これらのクライアントについては、図6に関連して後述されている。
【００１５】
プロセスは、COMMITまたはSYNCコマンドをそれぞれのインタラクションマネージャに発行することによって、コネクタを使用する。ポーリングの使用を回避するために、インタラクションマネージャは、特定の入力コネクタY1,……,Ymがイネーブルされたことをプロセスに知らせることができる。これは、演算子SIGNAL (Y1,……,Ym)が行う。これは、例えば、上記の特許文献に記載されているWAIT演算子を実装するのに使用することができる。インタラクションマネージャは、ネットワークを通じて他のインタラクションマネージャと通信することができる。このことに対して2つの操作が定義されている。送信者プロセスsのインタラクションマネージャは、受信者に到達するメッセージmを操作SEND (m,r)を使用して送信することができ、ネットワークは、受信者のインタラクションマネージャのメソッドDELIVER (m,s)（sは送信者プロセス）を呼び出す。
【００１６】
メソッドを指定するのに使用されるオブジェクト型は、プロセスに対してプロセス、コネクタに対してコネクタ、値に対して値、出力コネクタ状態に対してコネクタ状態、シーケンス番号に対してSYNC n,r、メッセージに対してメッセージである。プロセス（Process）型は、プロセスのクラスに対応する。コネクタ型は、コネクタのクラスを表す。この型のインスタンスは、（例えば、メッセージ内の）「アイデンティティ」と、状態変数を持つオブジェクトとして使用される（「コネクタ変数」のスライドを参照）。データ型値（Value）は、コネクタに格納することのできる値を表す。コネクタ状態（ConnectorState）は、出力コネクタの制御状態、すなわち、コネクタの送信者によって認識されるコネクタの状態を定義する列挙型である。これらについては、後にさらに説明される。シーケンス番号（SeqNr）型の値は、COMMITのシーケンス番号として使用される整数である。メッセージ（Message）型の値は、インタラクションマネージャによって送信および受信することのできるメッセージを表す。使用されるさまざまな種類のメッセージについては、後に定義されている。
【００１７】
本発明による実施例（図2）は、以下の4つの状態で構成されている。
【００１８】
− コミット済（committed）42:     x上で進行中のCOMMITなし
− コミット中（committing）41:    x上でCOMMIT (x ← v)型のCOMMITが進行中であり、このCOMMITの前に開始されたすべてのCOMMITは完了している。
【００１９】
− ロック中（locking）43:     x上でCOMMIT (x1 ← V1,…,xm ← Vm)型のCOMMITが進行中であり、COMMITは段階1である。
【００２０】
− ロック済（locked）44:      x上でCOMMIT (x1 ← V1,…,xm ← Vm)型のCOMMITが進行中であり、COMMITは段階2である。
【００２１】
プロセスのインタラクションマネージャは、そのプロセスの出力コネクタのそれぞれの「状態」を維持する。この状態は、4つの異なる値を持つことができ、それぞれの解釈について以下に説明する。出力コネクタが「コミット済」状態である場合は、そのコネクタ上で進行中のCOMMITはない。コネクタはロックされていない。出力コネクタxが「コミット中」状態である場合は、COMMIT (x ← v)型46のCOMMITの実行がこのコネクタ上で進行中であり、その一方で、すべての先行するCOMMITは完了済みである。コネクタはロックされておらず、送信者プロセスは、そのCOMMITを完了させるために、受信者プロセスからの「コミット済（committed）」メッセージを待っている。出力コネクタが「ロック中」状態である場合は、2段階ロック方式の段階1にあるCOMMITと進行において同期されていない、COMMIT (x1 ← V1,…,xm ← Vm)型49のCOMMITが存在する。コネクタはすでに「ロック」されているか、またはまだロックされておらず、送信者プロセスは、2段階ロック方式の段階2に進むために、受信者プロセスからの「ロック済（locked）」メッセージを待っている。出力コネクタが「ロック済」状態である場合は、2段階ロック方式の段階2にあるCOMMITと進行において同期されている、COMMIT (x1 ← V1,…,xm ← Vm)型47のコミットが存在する。コネクタはすでに「ロック」されており、送信者プロセスは、そのCOMMITを完了させるために、すべての出力コネクタx1,…,xmがロックされて、かつすべての先行するCOMMITが完了した状態を待っている。
【００２２】
この実施例においては、いくつかの型のメッセージがメソッドによって使用されている。これらの型は次のとおりである。
【００２３】
送信者から受信者へ：
・ < commit, Connector, Value >
・ < lock1, Connector, Value >
・ < lock 2, Connector, Value >
・ < unlock, Connector >
受信者から送信者へ:
・ < committed, Connector >
・ < locked, Connector >
・ < synced, Connector >
メッセージは複数の値であり、複数の値の最初の要素はメッセージの型を示す。
【００２４】
メッセージ<commit,x,v> 51は、コネクタxの受信者に、xにvを書き込み、xをイネーブルし、かつメッセージ<committed, x> 52を送信者プロセスに送り返すようにさせる命令である。
【００２５】
メッセージ<lock1,x,v> 54は、コネクタxの受信者に、xにvを書き込み、xをイネーブルしかつロックし、メッセージを送信者プロセスに送り返さないようにさせる命令である。
【００２６】
メッセージ<lock2,x,v> 56は、コネクタxの受信者に、xにvを書き込み、xをイネーブルしかつロックし、かつメッセージ<locked,x> 57を送信者プロセスに送り返すようにさせる命令である。
【００２７】
メッセージ<unlock,x> 55、58は、コネクタxの受信者に、コネクタxをアンロックさせる命令である。このメッセージは、COMMITを完了させるときに使用される。メッセージ<committed,x> 52と<locked,x>57は、上述されているようにxの受信者のACKメッセージである。メッセージ<synced,x> 53は、x上で正常な「同期」が実行されたとき、すなわちxの値が読み取られてxがディセーブルされたときに、xの受信者からxの送信者に送信される。
【００２８】
COMMITとSYNCの実行を制御するため、レコードがインタラクションマネージャによって維持され、このレコードは、以下のインタラクションマネージャ変数のセットを有する。
【００２９】
・ inputs: Set (Connector)      入力コネクタのセット（定数）
・ outputs: Set (Connector)      出力コネクタのセット（定数）
・ current: SeqNr       最後に初期化されたCOMMITのシーケンス番号
・ complete: SeqNr      最後に完了したCOMMITのシーケンス番号
conset [SeqNr]:
Set(Connector)      conset [s]は、シーケンス番号sを持つCOMMITに関連しているコネクタのセット。
【００３０】
初期値：
・ current = 0
・ complete = 0
・ conset = 該当しない
これらのレコードは、2つの部分から構成される。第一に、インタラクションマネージャは、プロセスに接続されている各入力コネクタと出力コネクタの状態に関する情報を維持する。この情報は、コネクタを表すオブジェクトに格納されることが好ましく、これらのオブジェクトに含まれる変数については後に説明される。第二に、上記に示されているようにインタラクションマネージャ自体の中に多数のグローバル変数がある。入力および出力としてプロセスに接続されているコネクタに関する情報は、オブジェクトの一定の集合（セット）inputsとoutputsに含まれている。進行中のCOMMITを追跡するために、COMMITのシーケンス番号が使用される。変数currentは、最も最近に開始されたCOMMITのシーケンス番号である。変数completeは、最も最近に完了したCOMMITのシーケンス番号である（従って
2005507522.tif 000003
。進行中の各COMMIT、すなわちシーケンス番号sを持つ各COMMITについて
2005507522.tif 000004
となるように、インタラクションマネージャは、どのコネクタがCOMMITに関連しているかを認識している必要がある。この情報は、（潜在的に無限の）配列consetに格納される。別の実施例においては、current、complete、およびconsetから成るデータ構造は、コネクタオブジェクトを通じて非常に効率的にリンクされているリスト構造に置き換えることができる（シーケンス番号の必要がなくなる）。
【００３１】
インタラクションマネージャは、各入力および出力コネクタに関する情報を記録し、この情報は、これらのコネクタを表している個別のオブジェクトに格納される。変数は次のとおりである。
【００３２】
・ sender : Process    コネクタに接続されている送信者プロセス（定数）
・ value : Value      コネクタに格納されている現在値
・ enabled: Boolean      コネクタがイネーブルされているか否かを示す。
【００３３】
・ locked: Boolean      コネクタがロックされているか否かを示す。
【００３４】
初期値：
・ value = 該当しない
・ enabled = false
・ locked = false
定数senderは、コネクタの送信者プロセス（コネクタの他端におけるプロセス）を指す。変数valueには、コネクタに格納されている値が含まれており、この値は、前述されているように、コネクタの受信者側に格納されている。「フラグ」enabledとlockedは、それぞれ、コネクタがイネーブルされているか否か、ロックされているか否かを示す。
【００３５】
さらに、インタラクションマネージャは、各入力および出力コネクタに関する情報を記録し、この情報は、これらのコネクタを表している個別のオブジェクトに格納される。変数は次のとおりである。
【００３６】
・ receiver: Process      コネクタに接続されている受信者プロセス（定数）
・ state: ConnectorState      コネクタの現在の出力制御状態
・ synced: Boolean      コネクタがディセーブルされていると認識されているか否かを示す。
【００３７】
初期値：
・ state = コミット済み
・ synced = true
定数receiverは、コネクタの受信者プロセス（コネクタの他端におけるプロセス）を指す。変数stateは、出力コネクタの「制御状態」を維持するために使用される。この変数の値は、出力コネクタの状態を定義し、そのコネクタ上でどのアクションがインタラクションマネージャによって行われるかを、かなりの程度決定する。コネクタがとりうるさまざまな状態とそれらの解釈については、後の説明を参照のこと。「フラグ」syncedは、（「同期済（synced）」メッセージを使用して受信者によって報告されるように）コネクタがディセーブルされていると認識されているか否かを示す。インタラクションマネージャに適用することのできるCOMMIT、SYNC、およびDELIVER操作の詳細な定義は、以下に説明される。
【００３８】
有効なCOMMITのSYNCの例は、次のとおりである。
2005507522.tif 000005
【００３９】
COMMITの前提条件(2)は、x1,…,xmが現在のプロセスの出力である必要があることと、COMMITが少なくとも1つの出力に関連している必要があることとを述べている。「コミット済」以外のコネクタの状態によって示されるように、出力コネクタx1,…,xmのいずれかにおいてCOMMITが進行中である場合、プロセスは、x1,…,xm上のすべてのCOMMITが完了する、すなわち、x1,…,xmすべてが「コミット済」状態になる(4)まで待つ必要がある。このことは、入ってくるDELIVERコマンドの効果によって起こる。COMMITがCOMMIT (x1 ← V1)型46であり、かつすべての先行するCOMMITが完了している（(5)行における条件「current = complete」）場合、メッセージ< commit, x1, V1 >が受信者x1に送信され、それによって、受信者に、値V1をx1に格納し、x1をイネーブルし、かつACK< committed, x1 >を送信者に送信する(6)ように命令する。このACKが受信されるまで、コネクタの状態は「コミット中」41に設定される(7)。それ以外のすべての状況においては、2段階ロック方式が使用される。
【００４０】
COMMITに関連しているすべての出力コネクタx1,…,xm (9)が順に検討され、各xiがコネクタの受信者側にてロックされる。これは、各xiに「ロック」メッセージを送信することによって行われ、このメッセージには「lock1」と「lock2」の2種類がある(11,14)。パフォーマンス上の理由から、たとえ受信者がViをまだ読み取ることができなくても値Viを受信者に移送するために、両方の型のメッセージが使用される。（「ロック（lock）」メッセージにおいてViを受信者に移しておくことによって、メッセージをバッファリングする必要がなく、COMMITの完了時にデータなしで「アンロック（unlock）」メッセージのみを受信者に送信するのみでよい） xiのフラグsyncedが設定されている場合(10)、そのコネクタはディセーブルされており、受信側にて読み取ることもイネーブルすることもできず、従って、このコネクタの状態をただちに「ロック済」に設定することができる(12)。メッセージ「ロック1」は、コネクタがロックされたことのACKを送信する必要がないことを受信者に示す。xiのフラグsyncedが設定されていない場合には(13)、通常の二段階ロック方式に従う。受信者に送信されるメッセージ「ロック2」(14)は、コネクタがロックされたときにACK（メッセージ「ロック済」）を送信するように受信者に命令する。このメッセージが受信されるまでは、コネクタの状態は「ロック中」に設定される。COMMITは、現在アクティブなCOMMITのシーケンス番号をインクリメントし(16)、現在のCOMMITに関連しているコネクタをあとから参照できるように記録する(17)ことによって終了する。
【００４１】
有効なSYNCの構文例は、次のとおりである。
2005507522.tif 000006
【００４２】
SYNCの前提条件(2)は、x1,…,xmが現在のプロセスの入力である必要があることを述べている。イネーブルされているコネクタのいずれかからSYNCを読み取らせる前に、すべてのCOMMITが終了している必要があり、終了していない場合、シーケンス上の矛盾が生じることがある。しかしながら、すべてのCOMMITが終了していない場合、すなわちcurrent ≠ completeである場合、選択肢として、終了するのを待つ(4,5)か、またはディセーブルされているコネクタから読み取らずにSYNCを終了する(6)。後者は、SYNCの本発明の定義によって可能となり、SYNCをブロックすることが望ましくないときに有用となることがある。これに対して、場合によっては、公平さの要件によって、COMMITが完了するのを待つことが必要となる。すべてのCOMMITが完了したとき、セット{x1,…,xn}内のイネーブルされている出力コネクタが順に検討される(7)。コネクタがロックされていない場合、またはコネクタがロックされており、かつアンロックされるのを待つことが決定されている場合(8,9)、コネクタの値が読み取られる(10)。留意すべき点として、アンロックを待つか否かの選択は、緩和されたSYNCの定義によって可能となり、待つことは、公平さの関連において必要とされることがある。コネクタの値が読み取られたときに、コネクタはディセーブルされる必要があり(11)、同期されたメッセージを送信することによって(12)、コネクタの送信者にこのことを通知する必要がある。
【００４３】
SYNCのこの定義の別の実施例は、たとえすべてのCOMMITが完了していなくても、SYNCにおいてネットワークトポロジの知識を使用して、x1,…,xnの1つ以上から読み取ることである（トポロジは順次整合性が保証されるものと想定する）。
【００４４】
有効なDELIVERのいくつかの構文例を、以下に紹介する。
2005507522.tif 000007
【００４５】
このネットワーク操作は、「コミット（commit）」メッセージを現在のプロセスのインタラクションマネージャに配信する。プロトコルは、メッセージ内のコネクタxが現在のプロセスの入力であり、かつ、このメッセージはxがロックされていないときに配信される(2)というものである。このメッセージは、メッセージに含まれている値vをコネクタxに格納し(4)、コネクタのイネーブル化フラグを設定し(5)、ACKをメッセージの送信者に送信する(6)ように、インタラクションマネージャに命令する。SIGNALコマンドは、コネクタxがイネーブルされたことを現在のプロセスに警告する。
【００４６】
DELIVERの別の構文例は、次のとおりである。
2005507522.tif 000008
【００４７】
このネットワーク操作は、タイプ1の「ロック」メッセージを現在のプロセスのインタラクションマネージャに配信する。プロトコルは、メッセージ内のコネクタxが現在のプロセスの入力であり、かつ、このメッセージはxがロックされていないときに配信される(2)というものである。このメッセージは、メッセージに含まれている値vをコネクタxに格納し(4)、コネクタのイネーブル化フラグを設定し(5)、コネクタをロックする(6)ように、インタラクションマネージャに命令する。タイプ2の「ロック」メッセージとの違いは、メッセージの送信者にACKが送信されないことである。
【００４８】
有効なDELIVERの別の構文例は、次のとおりである。
2005507522.tif 000009
【００４９】
このネットワーク操作は、タイプ2の「ロック」メッセージを現在のプロセスのインタラクションマネージャに配信する。プロトコルは、メッセージ内のコネクタxが現在のプロセスの入力であり、かつ、このメッセージはxがロックされていないときに配信される(2)というものである。このメッセージは、メッセージに含まれている値vをコネクタxに格納し(4)、コネクタのイネーブル化フラグを設定し(5)、コネクタをロックし(6)、ACKをメッセージの送信者に送信する(7)ように、インタラクションマネージャに命令する。タイプ1の「ロック」メッセージとの違いは、ACKがメッセージの送信者に送信されることである。
【００５０】
有効なDELIVERの別の構文例は、次のとおりである。
2005507522.tif 000010
【００５１】
このネットワーク操作は、「アンロック」メッセージを現在のプロセスのインタラクションマネージャに配信する。プロトコルは、メッセージ内のコネクタxが現在のプロセスの入力であり、かつ、このメッセージはxがイネーブルされておりかつロックされているときに配信される(2)というものである。このメッセージは、コネクタxをアンロックするようにインタラクションマネージャに命令する。SIGNALコマンドは、コネクタxがアンロックされ、かつ（イネーブルされているため）読み取ることができることを現在のプロセスに警告する。
【００５２】
有効なDELIVERの別のSYNC例は、次のとおりである。
2005507522.tif 000011
【００５３】
このネットワーク操作は、「コミット済」メッセージを現在のプロセスのインタラクションマネージャに配信する。プロトコルは、メッセージ内のコネクタxが現在のプロセスの出力であり、かつ、このメッセージはxがロックされておらずかつxの状態が「コミット中」であるときに配信される(2)というものである。このメッセージは、コネクタxの状態を「コミット済」に変更し(4)、syncedフラグをfalseに設定するように、インタラクションマネージャに命令する。「コミット済」メッセージは、COMMIT (x → v)型のCOMMITの完了を報告し、このコミットのシーケンス番号は(complete + 1)に等しい（これはこのプロトコルによって暗黙的に生じる特性である）する。completeの値は、これに一致して調整される(6)。COMMITが完了すると、そのCOMMITの後に開始された別のCOMMITの完了が可能になることがあり、可能か否かは、後述されている補助操作COMPLETE()によってチェックされる(7)。
【００５４】
有効なDELIVERの別のSYNC例は、次のとおりである。
2005507522.tif 000012
【００５５】
このネットワーク操作は、「ロック済」メッセージを現在のプロセスのインタラクションマネージャに配信する。プロトコルは、メッセージ内のコネクタxが現在のプロセスの出力であり、かつ、このメッセージはxがロックされておりかつxの状態が「ロック中」であるときに配信される(2)というものである。このメッセージは、コネクタxの状態を「ロック済」に変更するようにインタラクションマネージャに命令し、このことにより、進行中の1つ以上のCOMMITの完了が可能になることがある。このことは、後述されている補助操作COMPLETE()によってチェックされる(5)。
【００５６】
有効なDELIVERの別のSYNC例は、次のとおりである。
2005507522.tif 000013
【００５７】
このネットワーク操作は、「同期済」メッセージを現在のプロセスのインタラクションマネージャに配信する。プロトコルは、メッセージ内のコネクタxが現在のプロセスの出力であることである。このメッセージは、xが「コミット済」状態にあるときに(4)、xのsyncedフラグの値を「true」に変更する(5)ように、インタラクションマネージャに命令する。xが「コミット済」状態でない場合、このメッセージは無視される。なぜなら、xが「コミット済」状態にある場合のみ、xは確実に「同期済」である、すなわちxのenableフラグがクリアされているためである。
【００５８】
1つの実施例において、有効なCOMPLETE()は次のように使用される。
2005507522.tif 000014
2005507522.tif 000015
【００５９】
COMPLETEは、進行中のCOMMITの1つ以上が完了させられる状態にあるか否かを調べて、完了させられる状態にある場合、これらのCOMMITを完了させる。COMPLETEは、最初に、進行中のCOMMITがあるか否か(4)と、完了させる必要のある最初のCOMMIT（シーケンス番号complete + 1を持つCOMMIT）を完了させることができるか、すなわちそのCOMMITに関連しているすべてのコネクタが「ロック済」状態にあるか否か(5)を調べる。条件が満たされている場合、これらのコネクタが順に検討され(6)、各コネクタの受信者に「アンロック」メッセージが送信される(7)。COMMITの完了は、状態を「コミット済」に変更し(8)、かつsyncedフラグの値をfalseにリセットする(9)することによって、コネクタに記録される。最後に、最も最近に完了されたCOMMITのシーケンス番号を示す変数completeが、インクリメントされる(10)。COMMITの完了によって、進行中の次のCOMMITの完了が可能になることがあるため、このプロセス全体が繰り返される(4)。留意すべき点として、COMMIT (x → v)型のCOMMITの完了は、COMPLETEによって扱われず、DELIVER ( < committed, x >)操作によって直接扱われる。
【図面の簡単な説明】
【００６０】
【図１】本発明による好ましい実施例の線図を示す。
【図２】別の好ましい実施例の線図である。
【図３】本発明による別の実施例の線図である。
【図４】本発明による別の実施例の線図である。
【図５】本発明による別の実施例の線図である。
【図６】本発明による別の好ましい実施例の線図である。
【符号の説明】
【００６１】
2、4  プロセス
6、8  コネクタ
12、14  インタラクションマネージャ
16、18  インジケータ（フラグ）
111、112、113、114  共通クライアント
41  「コミット中」
42  「コミット済」
43  「ロック中」
44  「ロック済」
46  COMMIT (x ← v)型
47  COMMIT (x1 ← V1,…,xm ← Vm)型
49  COMMIT (x1 ← V1,…,xm ← Vm)型
51  メッセージ<commit,x,v>
52  メッセージ<committed, x>
53  メッセージ<synced,x>
54  メッセージ<lock1,x,v>
55、58  メッセージ<unlock,x>
56  メッセージ<lock2,x,v>
57  メッセージ<locked,x>
【図１】
2005507522.tif 000016
【図２】
2005507522.tif 000017
【図３】
2005507522.tif 000018
【図４】
2005507522.tif 000019
【図５】
2005507522.tif 000020
【図６】
2005507522.tif 000021
【国際公開パンフレット】
2005507522.tif 000022
2005507522.tif 000023
2005507522.tif 000024
2005507522.tif 000025
2005507522.tif 000026
2005507522.tif 000027
2005507522.tif 000028
2005507522.tif 000029
2005507522.tif 000030
2005507522.tif 000031
2005507522.tif 000032
2005507522.tif 000033
2005507522.tif 000034
2005507522.tif 000035
2005507522.tif 000036
2005507522.tif 000037
2005507522.tif 000038
2005507522.tif 000039
2005507522.tif 000040
2005507522.tif 000041
2005507522.tif 000042
2005507522.tif 000043
2005507522.tif 000044
【国際公開パンフレット（コレクトバージョン）】
2005507522.tif 000045
【国際調査報告】
2005507522.tif 000046
2005507522.tif 000047
2005507522.tif 000048
2005507522.tif 000049
2005507522.tif 000050
2005507522.tif 000051