(57)【要約】【課題】動作が停滞しているコンピュータを検出して待機状態にあるコンピュータにフェイルオーバすることで、リアルタイム性を確保する。【解決手段】ネットワーク接続されたｍ台のコンピュータ１００-iのうち、稼動状態にあるｎ台のコンピュータ１００-iの各々において、整列マルチキャスト部２の合意部２６２は、（ｎ−ｔ）台以上で入力データの合意をとることで当該入力データを整列マルチキャストする。システム構成変更検出部６３は、自身と比較して一定レベル以上停滞しているコンピュータを、合意部２６２による整列マルチキャストの実行状況に基づいて検出し、その検出に関し、自身を含む（ｎ−ｔ）台以上のコンピュータで合意をとる。停滞しているコンピュータの検出に関して合意がとれた場合、システム構成設定部６４は、停滞しているコンピュータを待機状態とし、待機状態にあるコンピュータを稼動状態とする。【選択図】      図２
2010198442.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークで接続されたｍ台（ｍは５以上の整数）のコンピュータのうちｎ台（ｎは４≦ｎ＜ｍを満たす整数）のコンピュータを稼動状態に設定して、ｔ−耐故障アルゴリズムの適用により同期的に動作させる、フェイルオーバ機能を持つ分散システムであって、
前記ｍ台のコンピュータの各々は、
前記ｍ台のコンピュータが、それぞれ同期的に動作させられるべき稼動状態にあるか、或いは待機状態にあるかを示すシステム構成情報を格納するシステム構成記憶手段と、
前記システム構成記憶手段に格納されているシステム構成情報によって稼動状態にあることが示されているｎ台のコンピュータのうちの（ｎ−ｔ）台（ｔは３ｔ＜ｎを満たす０より大きい整数）以上での多重化を保証するために、当該（ｎ−ｔ）台以上のコンピュータで入力データの合意をとることで当該入力データを整列マルチキャストする合意手段と、
前記ｎ台のコンピュータのうち、自身と比較して予め定められたレベル以上停滞しているコンピュータを、前記合意手段による整列マルチキャストの実行状況に基づいて検出し、前記停滞しているコンピュータを検出した場合、前記停滞しているコンピュータの検出に関し、前記ｎ台のコンピュータのうちの自身を含む（ｎ−ｔ）台以上のコンピュータで合意をとることで、前記停滞しているコンピュータの検出を確認する検出手段と、
前記停滞しているコンピュータの検出の確認に応じて、確認された前記停滞しているコンピュータを待機状態とし、待機状態にあるコンピュータを稼動状態とするように、前記システム構成記憶手段に格納されているシステム構成情報情報を更新することによって、前記停滞しているコンピュータから前記待機状態にあるコンピュータへフェイルオーバするシステム構成設定手段と
を具備することを特徴とするフェイルオーバ機能を持つ分散システム。
【請求項２】
前記検出手段は、前記停滞しているコンピュータを確認した場合、確認された前記停滞しているコンピュータを待機状態とし、待機状態にあるコンピュータを稼動状態とするように前記分散システムの構成の変更を要求するためのシステム構成変更要求データを前記入力データとして前記合意手段に与えることにより前記システム構成変更要求データを整列マルチキャストさせ、
前記システム構成設定手段は、前記合意手段により前記システム構成変更要求データが整列マルチキャストさせられたことをもって、前記システム構成変更要求データの示す前記分散システムの構成への変更を行う
ことを特徴とする請求項１記載のフェイルオーバ機能を持つ分散システム。
【請求項３】
前記合意手段は、合意の対象となる入力データを当該入力データにシリアルに付される順序番号により管理し、
前記ｍ台のコンピュータの各々は、前記ｎ台のコンピュータの各々について、他の稼動状態にあるコンピュータとの間で合意された入力データに付された最大の順序番号の履歴を格納する順序番号履歴記憶手段をさらに具備し、
前記検出手段は、前記停滞しているコンピュータを、前記順序番号履歴記憶手段に格納されている前記ｎ台のコンピュータの各々についての最大の順序番号の履歴に基づいて検出する
ことを特徴とする請求項１または２に記載のフェイルオーバ機能を持つ分散システム。
【請求項４】
前記予め定められたレベルを、１よりも大きい前記順序番号の差分としたことを特徴とする請求項３に記載のフェイルオーバ機能を持つ分散システム。
【請求項５】
前記検出手段が前記停滞しているコンピュータを検出した場合、当該検出された停滞しているコンピュータを他の稼動状態にあるすべてのコンピュータに対して報告するための報告種類のプロトコルデータ、他の稼動状態にあるコンピュータから送信された報告種類のプロトコルデータによる報告に同意することを示す同意種類のプロトコルデータ、および当該報告に同意しないことを示す非同意種類のプロトコルデータを送信するシステム構成変更合意プロトコルデータ送受信手段であって、他の稼動状態にあるコンピュータから送信される、前記報告種類のプロトコルデータ、前記同意種類のプロトコルデータおよび前記非同意種類のプロトコルデータを受信するシステム構成変更合意プロトコルデータ送受信手段をさらに具備し、
前記検出手段は、前記停滞しているコンピュータを検出することによって前記システム構成変更合意プロトコルデータ送受信手段により前記報告種類のプロトコルデータが他の稼動状態にあるコンピュータに送信され、当該報告種類のプロトコルデータに対し、（ｎ−ｔ−１）台以上のコンピュータから前記同意種類のプロトコルデータが返されたことをもって、前記停滞しているコンピュータの検出に関し、自身を含む（ｎ−ｔ）台以上のコンピュータで合意がとれたとする請求項１乃至４のいずれかに記載のフェイルオーバ機能を持つ分散システム。
【請求項６】
ネットワークで接続されたｍ台（ｍは５以上の整数）のコンピュータのうちｎ台（ｎは４≦ｎ＜ｍを満たす整数）のコンピュータを稼動状態に設定して、ｔ−耐故障アルゴリズムの適用により同期的に動作させる分散システムにおいて、前記ｎ台のコンピュータのうちのいずれかのコンピュータの動作が停滞している場合に、当該停滞しているコンピュータから待機状態にあるコンピュータにフェイルオーバするためのフェイルオーバ方法であって、
前記ｍ台のコンピュータの各々は、前記ｍ台のコンピュータが、それぞれ同期的に動作させられるべき稼動状態にあるか、或いは待機状態にあるかを示すシステム構成情報を格納するシステム構成記憶手段と、合意手段と、検出手段と、システム構成設定手段とを具備し、
前記フェイルオーバ方法は、
前記ｍ台のコンピュータの各々の前記合意手段が、前記システム構成記憶手段に格納されているシステム構成情報によって稼動状態にあることが示されているｎ台のコンピュータのうちの（ｎ−ｔ）台（ｔは３ｔ＜ｎを満たす０より大きい整数）以上での多重化を保証するために、当該（ｎ−ｔ）台以上のコンピュータで入力データの合意をとることで当該入力データを整列マルチキャストするステップと、
前記検出手段が、前記ｎ台のコンピュータのうち、自身と比較して予め定められたレベル以上停滞しているコンピュータを、前記合意手段による整列マルチキャストの実行状況に基づいて検出するステップと、
前記停滞しているコンピュータを検出した場合、前記検出手段が、前記停滞しているコンピュータの検出に関し、前記ｎ台のコンピュータのうちの自身を含む（ｎ−ｔ）台以上のコンピュータで合意をとることで、前記停滞しているコンピュータの検出を確認するステップと、
前記停滞しているコンピュータの検出の確認に応じて、確認された前記停滞しているコンピュータを待機状態とし、待機状態にあるコンピュータを稼動状態とするように、前記システム構成記憶手段に格納されているシステム構成情報情報を更新することによって、前記停滞しているコンピュータから前記待機状態にあるコンピュータへフェイルオーバするステップと
を具備することを特徴とするフェイルオーバ方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークで接続されたｍ台（ｍは５より大きい整数）のコンピュータのうちｎ台（ｎは４＜ｎ＜ｍを満たす整数）のコンピュータを同期的に動作させ、（ｎ−ｔ）台（ｔは３ｔ＜ｎを満たす整数）以上での多重化を保証する分散システムに係り、特に当該ｎ台のコンピュータのいずれかの動作が停滞している場合に、当該停滞しているコンピュータから残りの（ｍ−ｎ）台のコンピュータのうちの１台にフェイルオーバするフェイルオーバ機能を持つ分散システムおよび同システムにおけるフェイルオーバ方法に関する。
【背景技術】
【０００２】
近年、コンピュータ技術やネットワーク技術の向上は目覚ましく、これに伴って、業務のコンピュータ化が広く行われている。また、その業務の内容によっては、故障などによる中断が許されないものも多く、最近では、複数のコンピュータをネットワークで結合した分散システムを構築することが一般的になりつつある。そして、この分散システムの運用手法の１つに、整列マルチキャストを用いた決定性のプログラムの実行の多重化が存在する。
【０００３】
整列マルチキャストは、分散システムへの入力をすべてのコンピュータに配送する仕組みであり、データの到着順序がすべてのコンピュータで同じであることを保証するものである。
【０００４】
分散システムにおける多重化の手法として、例えば特許文献１は、ｎ台（ｎは４以上の整数）のコンピュータ（つまり４台以上のコンピュータ）がネットワークで接続された分散システムにおいて、スプリットブレインを原理的に発生させず、タイムアウトによる故障発生時の処理の中断も発生させることがない手法を開示している。
【０００５】
この特許文献１が開示する従来の多重化手法（先行技術）においては、ｎ台（ｎは４以上の整数）のコンピュータから構成される分散システムを例にとると、当該ｎ台のコンピュータを同期的に動作させ、当該ｎ台のコンピュータのうちの（ｎ−ｆ）台（ｆは、最大許容障害数と呼ばれる、３ｆ＜ｎを満たす最大の整数）以上での多重化を保証するために、当該ｎ台のコンピュータの各々は、入力候補収集手段と入力候補選定制御手段（第１の入力候補選定制御手段）とを具備する。入力候補収集手段は、ｎ台のコンピュータそれぞれが次に処理する候補として選択した入力データをネットワークを介して収集する。入力候補選定制御手段は、入力候補収集手段により収集された入力データが（ｎ−ｆ）個以上存在する場合に、その中に同一内容の入力データが（ｎ−ｆ）個以上あるか否かを判定し、（ｎ−ｆ）個以上あったときに、その入力データを次に処理する対象として確定する。これにより入力データが整列マルチキャストされる。このように、収集された（ｎ−ｆ）個以上の入力データの中に同一内容の入力データが（ｎ−ｆ）個以上あることを入力候補選定制御手段が判定することは、（ｎ−ｆ）台以上のコンピュータで入力データの合意をとることに他ならない。つまり入力候補選定制御手段は合意手段として機能することを意味する。
【０００６】
例えば、特許文献２では、最大許容障害数ｆに相当する変数としてｔが用いられる。この場合、（ｎ−ｔ）台以上のコンピュータで入力データの合意をとることにより、ｎ台のコンピュータのうちの最大ｔ台の故障（いわゆるビザンチン型の故障）が許容される。このようなアルゴリズムは、ｔ−耐故障ビザンチン合意アルゴリズム、ｔ−耐故障ビザンチン将軍アルゴリズム、或いは単にｔ−耐故障アルゴリズムと呼ばれる。以下の説明では、上述のアルゴリズムをｔ−耐故障アルゴリズムと称し、特許文献１が開示する先行技術に関しても、煩雑さを防ぐために最大許容障害数として「ｔ」を用いることにする。また以下の説明では、上述のｎ台のコンピュータを、多重化を構成するコンピュータまたは同期的に動作させられるべきコンピュータと称することもある。
【０００７】
ｔ−耐故障アルゴリズムでは、ｔは、３ｔ＜ｎを満たす０より大きい整数であればよく、必ずしも特許文献１に記載されているように、３ｔ＜ｎを満たす最大の整数である必要はない。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特許第３６５５２６３号公報
【特許文献２】特開平６-８３６１１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
特許文献１に記載の先行技術によれば、ｎ台（ｎは４以上の整数）のコンピュータから構成される分散システム、つまり多重化を構成するコンピュータがｎ台の分散システムでは、ｔ台までのコンピュータの故障が許容される。
【００１０】
ここで、ｎ台のコンピュータの中に定常的に遅延している（つまり動作が停滞している）コンピュータが存在する場合を想定する。この場合、遅延しているコンピュータの台数がｔ台までであれば、残りの（ｎ−ｔ）台のコンピュータで合意をとることができるため、リアルタイム性を確保できる。
【００１１】
次に、ｔ台のコンピュータが故障して、動作しているコンピュータが（ｎ−ｔ）台となった状態を想定する。このような状態では、動作している（ｎ−ｔ）台のコンピュータの中に遅延しているコンピュータがあると、その遅延しているコンピュータを含めて合意をとる必要がある。このような場合、分散システムにおける処理速度が、遅延しているコンピュータの処理速度になってしまう。
【００１２】
つまり先行技術においては、ｔ台までのコンピュータの故障が許容されるものの、ｔ台のコンピュータが故障して、（ｎ−ｔ）台のコンピュータの中に遅延しているコンピュータがあると、分散システム全体の処理速度の低下を招く。
【００１３】
本発明は上記事情を考慮してなされたものでその目的は、多重化を構成するコンピュータのうちで動作が停滞しているコンピュータを検出して待機状態にあるコンピュータにフェイルオーバすることで、リアルタイム性を確保できるフェイルオーバ機能を持つ分散システムおよび同システムにおけるフェイルオーバ方法を提供することにある。
【課題を解決するための手段】
【００１４】
本発明の１つの観点によれば、ネットワークで接続されたｍ台（ｍは５以上の整数）のコンピュータのうちｎ台（ｎは４≦ｎ＜ｍを満たす整数）のコンピュータを稼動状態に設定して、ｔ−耐故障アルゴリズムの適用により同期的に動作させる、フェイルオーバ機能を持つ分散システムが提供される。この分散システムを構成する前記ｍ台のコンピュータの各々は、前記ｍ台のコンピュータが、それぞれ同期的に動作させられるべき稼動状態にあるか、或いは待機状態にあるかを示すシステム構成情報を格納するシステム構成記憶手段と、前記システム構成記憶手段に格納されているシステム構成情報によって稼動状態にあることが示されているｎ台のコンピュータのうちの（ｎ−ｔ）台（ｔは３ｔ＜ｎを満たす０より大きい整数）以上での多重化を保証するために、当該（ｎ−ｔ）台以上のコンピュータで入力データの合意をとることで当該入力データを整列マルチキャストする合意手段と、前記ｎ台のコンピュータのうち、自身と比較して予め定められたレベル以上停滞しているコンピュータを、前記合意手段による整列マルチキャストの実行状況に基づいて検出し、前記停滞しているコンピュータを検出した場合、前記停滞しているコンピュータの検出に関し、前記ｎ台のコンピュータのうちの自身を含む（ｎ−ｔ）台以上のコンピュータで合意をとることで、前記停滞しているコンピュータの検出を確認する検出手段と、前記停滞しているコンピュータの検出の確認に応じて、確認された前記停滞しているコンピュータを待機状態とし、待機状態にあるコンピュータを稼動状態とするように、前記システム構成記憶手段に格納されているシステム構成情報情報を更新することによって、前記停滞しているコンピュータから前記待機状態にあるコンピュータへフェイルオーバするシステム構成設定手段とを具備する。
【発明の効果】
【００１５】
本発明によれば、停滞しているコンピュータを検出した場合、この停滞しているコンピュータの検出に関し、停滞しているコンピュータを検出したコンピュータを含む（ｎ−ｔ）台以上のコンピュータで合意をとることで、停滞しているコンピュータを正しく検出できたことを確認することができる。また本発明によれば、この確認に応じて、確認された停滞しているコンピュータを待機状態とし、待機状態にあるコンピュータを稼動状態とするシステム変更を行うことで、つまり停滞しているコンピュータから待機状態にあるコンピュータにフェイルオーバすることで、アルタイム性を確保することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態に係る分散システムの構成を示すブロック図。
【図２】同実施形態の分散システムを構成するコンピュータの機能構成を示すブロック図。
【図３】同実施形態の入力受付キュー部に積まれる入力パケットデータのデータ構造例を示す図。
【図４】同実施形態の分散システムを構成するコンピュータの整列マルチキャストプロトコルデータ送受信部間で送受信される整列マルチキャストプロトコルデータのレイアウトを示す図。
【図５】同実施形態におけるシステム構成記憶部のデータ構造例を示す図。
【図６】同実施形態における最大確定入力順序番号履歴記憶部のデータ構造例を示す図。
【図７】同実施形態の分散システムを構成するコンピュータのシステム構成変更合意プロトコルデータ送受信部間で送受信されるシステム構成変更合意プロトコルデータのレイアウトを示す図。
【図８】同実施形態において各コンピュータが実行する整列マルチキャストの１回の配送を行う基本的な部分の動作手順を示す第１のフローチャート。
【図９】同実施形態において各コンピュータが実行する整列マルチキャストの１回の配送を行う基本的な部分の動作手順を示す第２のフローチャート。
【図１０】同実施形態において各コンピュータが実行する、多重化実行の遅延を解消するための動作手順を示す第１のフローチャート。
【図１１】同実施形態において各コンピュータが実行する、多重化実行の遅延を解消するための動作手順を示す第２のフローチャート。
【図１２】同実施形態において各コンピュータが実行する、多重化実行の遅延を解消するための動作手順を示す第３のフローチャート。
【図１３】同実施形態において各コンピュータが実行する、多重化実行の遅延を解消するための動作手順を示す第４のフローチャート。
【図１４】同実施形態において各コンピュータが実行する、停滞しているコンピュータを探すための処理の手順を示すフローチャート。
【図１５】同実施形態において各コンピュータが実行する、報告種類のシステム構成変更合意プロトコルデータを受け取った場合の処理の手順を示すフローチャート。
【図１６】同実施形態において各コンピュータが実行する、同意種類または非同意種類のシステム構成変更合意プロトコルデータを受け取った場合の処理の手順を示すフローチャート。
【図１７】同実施形態において各コンピュータが実行する、確定されたシステム構成変更要求パケットを受け取った場合の処理の手順を示すフローチャート。
【図１８】同実施形態において各コンピュータが実行する、システム構成通知プロトコルデータを受け取った場合の処理の手順を示すフローチャート。
【発明を実施するための形態】
【００１７】
以下、本発明の実施の形態につき図面を参照して説明する。  
図１は本発明の一実施形態に係る分散システムの構成を示すブロック図である。図１において、分散システム１０は、例えば５台のコンピュータ１００-1（＃１）〜１００-5（＃５）から構成されている。コンピュータ１００-1〜１００-5のうち、ｔ−耐故障アルゴリズムによる多重化を保証するのに必要な台数以上のコンピュータ、例えば４台のコンピュータ１００-1〜１００-4は稼動状態にあるものとする。この稼動状態にあるコンピュータ１００-1〜１００-4は多重化を構成する。コンピュータ１００-1〜１００-5のうち、残りのコンピュータ１００-5は待機状態にある。
【００１８】
ここで、分散システム１０を構成するコンピュータの数をｍで表し、分散システム１０において現在多重化されている（稼動状態にある）コンピュータの数をｎで表すものとする。ｎは上記特許文献１と同様に４以上の整数であり、ｍはｎより大きい整数である。つまり、ｎは、４≦ｎ＜ｍを満たす整数である。この場合、ｔを３ｔ＜ｎを満たす０より大きい整数とすると、ｔ−耐故障アルゴリズムにより、ｎ台のコンピュータのうちの最大ｔ台の故障が許容される。図１の分散システムの例では、ｎは４であり、ｍは５である。ｎが４の場合、ｔは１となり、１台のコンピュータの故障が許容される。ｔが１の場合、ｔ台のコンピュータの故障を許容するのに必要なｎ、つまりｔ−耐故障アルゴリズムによる多重化を保証するのに必要なコンピュータの台数の最小値は４である。図１の分散システムの例は、この場合に相当する。
【００１９】
コンピュータ１００-1〜１００-5は、ネットワークＡを介してクライアント装置２００と接続されている。コンピュータ１００-1〜１００-5は、クライアント装置２００以外のクライアント装置（図示せず）ともネットワークＡを介して接続されているものとする。本実施形態においてネットワークＡはパブリックネットワーク（外部ネットワーク）である。コンピュータ１００-1〜１００-5間は、ネットワークＢを介して接続されている。本実施形態においてネットワークＢはプライベートネットワーク（内部ネットワーク）である。
【００２０】
稼動状態にあるコンピュータ１００-1〜１００-4、つまり分散システム１０において多重化を構成しているコンピュータ１００-1〜１００-4は、前記特許文献１に記載された分散システムにおけるコンピュータと同様に、ネットワークＡを介してクライアント装置２００から受け取った入力パケット（入力）を他のコンピュータと同じ順序で処理していく。なお、クライアント装置２００からの入力パケットは、コンピュータ１００-1〜１００-4のうちのいずれかのコンピュータに入力される。
【００２１】
コンピュータ１００-1〜１００-5は、それぞれ同一のアプリケーションプログラム３（図２参照）を有している。コンピュータ１００-1〜１００-5のうち、多重化を構成するコンピュータ１００-1〜１００-4は、同一の初期状態から始まる。その後、クライアント装置２００から分散システムに入力されるデータは、必ず整列マルチキャストを通して、コンピュータ１００-1〜１００-4に同一順序で配送される。これにより、コンピュータ１００-1〜１００-4においてそれぞれのアプリケーションプログラム３が実行される。
【００２２】
コンピュータ１００-1〜１００-4がそれぞれ有するアプリケーションプログラム３への入力データ列は、整列マルチキャストにより同一順序となっている。このため、前記特許文献１に記載されているような決定性のプログラムの特徴により、コンピュータ１００-1〜１００-4の状態が同一に保たれ、出力データ列もすべて同じとなる。つまり、プログラムの実行が多重化される。
【００２３】
図２は、図１に示されるコンピュータ１００-i（ｉ＝１，２，…-5）の構成を示すブロック図である。図２において、クライアント装置２００からネットワークＡを介してコンピュータ１００-iに送信されて、当該コンピュータ１００-iの入力受付キュー部（以下、受付キューと称する）１で受け付けられた入力パケットは、当該受付キュー１に受付順に積まれる。受付キュー１に積まれた入力パケットは、整列マルチキャスト部２（内の入力パケット確定判定部２６に含まれている合意部２６２）によってアプリケーションプログラム３または後述するシステム構成管理部６に配送される。なお、受付キュー１に積まれる入力パケットには、クライアント装置２００からの入力パケットの他に、システム構成管理部６のシステム構成変更検出部６３から送られるシステム構成変更を要求する特定の入力パケット（システム構成変更要求パケット）がある。
【００２４】
アプリケーションプログラム３は、配送された入力パケットを受けて、プログラム状態管理部４に保存されている状態に従って当該入力パケットを処理し、出力パケットを生成する。生成された出力パケットは、出力フィルタ部５で選別されてから、ネットワークＡを介してクライアント装置２００に返却される（出力）。
【００２５】
次に、コンピュータ１００-iの整列マルチキャスト部２の構成について説明する。整列マルチキャスト部２は、前記特許文献１に記載された整列マルチキャスト部と同様に、入力順序番号記憶部２１、入力パケットジャーナル記憶部２２、整列マルチキャストプロトコルデータ送受信部２３、ステップ番号記憶部２４、候補パケット記憶部２５、入力パケット確定判定部２６、最大確定入力順序番号記憶部２７、遅延記憶部２８およびスキップ判定部２９の周知の構成を含んでいる。
【００２６】
入力順序番号記憶部２１は、整列マルチキャストによってコンピュータ１００-iへ次に配送される入力パケットの順序番号（つまり整列マルチキャストにシリアルに付される最新の順序番号）を格納する。入力パケットジャーナル記憶部２２は、整列マルチキャストによってコンピュータ１００-iへの配送が確定した入力パケットの列を最近のものから一定の量だけ格納する。
【００２７】
整列マルチキャストプロトコルデータ送受信部２３は、システム構成管理部６の後述するシステム構成記憶部６１を参照して、他の稼動状態にあるコンピュータの整列マルチキャストプロトコルデータ送受信部２３とネットワークＢを介してプロトコルデータ（整列マルチキャストプロトコルデータ）を授受する。
【００２８】
本実施形態では、クライアント装置２００とコンピュータ１００-iとの間のデータの授受と、コンピュータ１００-i相互間のデータの授受とで、使用するネットワークが切り替えられる。これによりネットワーク負荷が軽減される。しかし、クライアント装置２００とコンピュータ１００-iとの間のデータの授受と、コンピュータ１００-i相互間のデータの授受とが、例えばネットワークＡを介して行われる構成であっても構わない。またネットワークＡが必ずしもパブリックネットワークである必要はない。
【００２９】
ステップ番号記憶部２４、候補パケット記憶部２５および入力パケット確定判定部２６は、整列マルチキャストによってコンピュータ１００-iへ次に配送される入力パケットを決定し、またシステム構成を変更するアルゴリズムで用いられる。
【００３０】
ステップ番号記憶部２４は、プロトコルのステップを示すステップ番号を格納する。候補パケット記憶部２５は、そのステップにおける各コンピュータの「入力候補」となる入力パケットを計ｎ個格納する。
【００３１】
入力パケット確定判定部２６は、候補パケット記憶部２５の情報から入力パケットの確定の判定および次ステップの「入力候補」の決定を行う。入力パケット確定判定部２６はさらに、前記特許文献１に記載された入力パケット確定判定部と異なり、入力パケットをアプリケーションプログラム３およびシステム構成管理部６（内のシステム構成設定部６４）のいずれに渡すかを決定する。この決定のために、受付キュー１に積まれる入力パケットには、処理種別を示す情報（処理種別情報）が付加される。入力パケット確定判定部２６は、入力候補収集部２６１および合意部２６２を含む。
【００３２】
図３は受付キュー１に積まれるデータ（入力パケットデータ）のデータ構造例を示す。図３に示されるように、入力パケットデータは、処理種別および入力パケットの各フィールドを含む。入力パケットフィールドには入力パケットが格納（設定）され、処理種別フィールドには処理種別情報が格納（設定）される。
【００３３】
本実施形態において処理種別情報は、入力パケットフィールドに格納されている入力パケットをアプリケーションプログラム３またはシステム構成管理部６（内のシステム構成設定部６４）のいずれに渡すかを入力パケット確定判定部２６（内の合意部２６２）が決定するための処理種別を示す。そのため、処理種別情報の示す処理種別は、（１）アプリケーションと（２）構成とに分けられる。処理種別が「アプリケーション」の場合、入力パケットが外部のクライアント装置２０００から入力されたものであることをも示し、処理種別が「構成」の場合、入力パケットが分散システム１０を構成するいずれかのコンピュータのシステム構成管理部６（内のシステム構成変更検出部６３）から当該いずれかのコンピュータの受付キュー１に入力されたものであることをも示す。
【００３４】
再び図２を参照すると、最大確定入力順序番号記憶部２７は、多重化を構成している（稼動状態にある）他のコンピュータも含め、配送が確定したことがわかっている最大の入力順序番号を格納する。遅延記憶部２８は、多重化を構成している他の（ｎ−１）台（ｎ＝４）のコンピュータよりも遅延しているかどうかを示す（ｎ−１）個の遅延フラグ（ｎ＝４の本実施形態では、３個のフラグ）を格納する。スキップ判定部２９は、遅延記憶部２８の情報からスキップ動作の必要性を判定およびスキップ動作を実行する。
【００３５】
以降の説明では、入力順序番号記憶部２１に格納された入力順序番号を該当入力順序番号と呼び、ステップ番号記憶部２４に格納されたステップ番号を該当ステップ番号と呼ぶ。コンピュータ１００-iの整列マルチキャスト部２に含まれている候補パケット記憶部２５に格納されているｎ個の「入力候補」のうち、当該コンピュータ１００-i自身（自コンピュータ）に対応する「入力候補」を自候補と呼び、当該自候補以外の「入力候補」を他候補と呼ぶ。
【００３６】
次に、整列マルチキャストプロトコルデータ送受信部２３によって送受信される整列マルチキャストプロトコルデータについて説明する。  
図４は、整列マルチキャストプロトコルデータのレイアウトを示す図である。図４に示されるように、整列マルチキャストプロトコルデータ送受信部２３によって送受信される整列マルチキャストプロトコルデータは、種類、送信者、入力順序番号、ステップ番号（整列マルチキャストステップ番号）、最大確定入力順序番号、処理種別および入力パケットの各フィールドを含む。図４に示される整列マルチキャストプロトコルデータが前記特許文献１に記載されているプロトコルデータと相違するのは、前述の処理種別フィールドが追加されている点にある。
【００３７】
整列マルチキャストプロトコルデータは先頭の種類フィールドによって、次の３つに使い分けられる。  
（１）候補種類
入力順序番号フィールド、ステップ番号フィールド、入力パケットフィールドには、それぞれ、送信者（送信側コンピュータ）の送信時における該当入力順序番号、該当ステップ番号、自候補が格納される。
【００３８】
（２）確定種類
その入力順序番号（入力順序番号フィールドに格納されている入力順序番号）に対応する入力パケットが、送信者の送信時における入力パケットジャーナル記憶部２２にあることを示し、入力パケットフィールドには、その入力パケットが格納される。この場合、ステップ番号フィールドは使用されない。
【００３９】
（３）遅延種類
その入力順序番号に対応する入力パケットが、送信者の送信時における入力パケットジャーナル記憶部２２にないことを示す。この場合、ステップ番号フィールドおよび入力パケットフィールドは使用されない。
【００４０】
いずれの種類の整列マルチキャストプロトコルデータにおいても、最大確定入力順序番号フィールドには、送信者（送信側コンピュータ）からの整列マルチキャストプロトコルデータ送信時における該当最大確定入力順序番号が格納される。また、整列マルチキャストプロトコルデータの受信側コンピュータにおける該当最大確定入力順序番号は、当該受信側コンピュータで確定された入力パケットの順序番号と、当該受信側コンピュータで受信された整列マルチキャストプロトコルデータ中の最大確定入力順序番号とのうち、最も大きいものに更新される。
【００４１】
本実施形態では、分散システム１０内のコンピュータ１００-iは、前記特許文献１に記載されたコンピュータと異なり、多重化を構成するコンピュータを、当該システム１０の状況に応じて動的に変更するための新規の構成を含む。即ちコンピュータ１００-iは、図２に示されるように、システム構成管理部６をさらに有する。システム構成管理部６は、分散システム１０の構成を管理・決定する。この分散システム１０の構成の決定は、多重化を構成するコンピュータ間の合意に基づいて行われる。
【００４２】
システム構成管理部６は、システム構成記憶部６１、最大確定入力順序番号履歴記憶部６２、システム構成変更検出部６３、システム構成設定部６４、システム構成変更合意プロトコルデータ送受信部６５、およびシステム構成通知プロトコルデータ送受信部６６から構成される。
【００４３】
システム構成記憶部６１は、分散システム１０の構成に関するシステム構成情報を格納する。システム構成情報は、分散システム１０を構成するコンピュータと当該コンピュータの状態とを示す情報を含む。コンピュータの状態は、当該コンピュータが稼動している稼動状態（つまり多重化を構成している状態）、或いは待機している待機状態（つまり多重化を構成していない状態）のいずれかである。システム構成情報はさらに、分散システム１０を構成するコンピュータの優先度を示す情報（優先度情報）を含む。この優先度は、稼動状態にあったコンピュータの停滞の検出に応じてフェイルオーバを実施する際に優先的に使用するコンピュータを決定するのに用いられる。
【００４４】
図５は、システム構成記憶部６１のデータ構造例を示す。図５の例では、分散システム１０を構成するコンピュータを示す情報として、コンピュータ名が用いられている。本実施形態において、コンピュータ１００-1〜１００-5のコンピュータ名がコンピュータ＃１〜＃５であるものとすると、図５に示すシステム構成記憶部６１は、分散システム１０がコンピュータ１００-1〜１００-5から構成されていることを示す。
【００４５】
また図５に示すシステム構成記憶部６１は、コンピュータ１００-1〜１００-4が稼動状態にあり、コンピュータ１００-5が待機状態にあることを示す。つまり図５に示すシステム構成記憶部６１は、図１の状態の分散システム１０の構成を示している。
【００４６】
図５に示すシステム構成記憶部６１はさらに、コンピュータ１００-1，１００-2，１００-3，１００-4，１００-5の優先度が、それぞれ１，２，３，４，５であることを示す。本実施形態では、優先度の値が小さいほど高優先度となる。したがって図５の例では、コンピュータの優先度は、コンピュータ１００-1が最も高く、以下コンピュータ１００-2，１００-3，１００-4，１００-5の順となる。但し、ｎが４、ｍが５である本実施形態では、待機状態にあるコンピュータはコンピュータ１００-5のみであることから、フェイルオーバを実施する際には、当該コンピュータ１００-5が優先度に無関係に使用される。もし、ｍが５よりも大きく、したがって待機状態にあるコンピュータがコンピュータ１００-5を含めて複数存在するならば、フェイルオーバを実施する際には、この複数の待機状態にあるコンピュータのうち最も優先度が高いコンピュータが使用される。
【００４７】
最大確定入力順序番号履歴記憶部６２は、多重化を構成している（稼動状態にある）各コンピュータの、配送が確定したことが分かっている最大の入力順序番号（最大確定入力順序番号）の履歴を格納する。より詳細には、最大確定入力順序番号履歴記憶部６２は、自コンピュータの最大確定入力順序番号記憶部２７に格納されている最大確定入力順序番号が変更される毎に、その時刻を示すタイムスタンプに加えて、多重化を構成している各コンピュータ（図１の例ではコンピュータ１００-1〜１００-4）の、配送が確定したことがわかっている最大の入力順序番号を、時系列順に格納するのに用いられる。
【００４８】
図６は最大確定入力順序番号履歴記憶部６２のデータ構造例を示す。図６の例では、ある時点以降のコンピュータ１００-4（＃４）における最大確定入力順序番号が、他のコンピュータ１００-1（＃１）〜１００-3（＃３）よりも小さく、遅延していることが示されている。
【００４９】
システム構成変更検出部６３は、最大確定入力順序番号履歴記憶部６２に格納されている最大確定入力順序番号履歴に基づいて停滞しているコンピュータを検出することにより、システム構成を変更すべきことを検出（決定）する。システム構成変更検出部６３はまた、停滞しているコンピュータを検出した場合、当該検出された停滞しているコンピュータを、他の稼動状態にあるすべてのコンピュータに対してシステム構成変更合意プロトコルデータ送受信部６５を介して報告する。この報告には、報告種類のシステム構成変更合意プロトコルデータが用いられる。
【００５０】
システム構成変更検出部６３はまた、上述の報告に対して、他の稼動状態にあるコンピュータのうちの（ｎ−ｔ−１）台以上（ｎ＝４、ｔ＝１の本実施形態では２台以上）から、同意する旨がシステム構成変更合意プロトコルデータ送受信部６５を介して返された場合、停滞しているコンピュータの検出に関し、自コンピュータを含めて（ｎ−ｔ）台以上で合意がとれたと判断する。
【００５１】
システム構成変更検出部６３はまた、他のコンピュータから停滞しているコンピュータが報告された場合、最大確定入力順序番号履歴記憶部６２に格納されている最大確定入力順序番号履歴に基づいて、その報告に同意するかを判定する。システム構成変更検出部６３は、この判定結果（つまり、同意するか或いは非同意とするか）を、停滞しているコンピュータを報告したコンピュータに通知する。この通知には、同意種類または非同意種類のシステム構成変更合意プロトコルデータが用いられる。
【００５２】
システム構成変更検出部６３はまた、停滞しているコンピュータの検出に関し、自コンピュータを含めて（ｎ−ｔ）台以上で合意がとれたことにより、停滞しているコンピュータの検出を確認する。システム構成変更検出部６３はさらに、停滞しているコンピュータの検出の確認に応じて、確認された停滞しているコンピュータを待機状態とし、待機状態にあるコンピュータを稼動状態とするように分散システムの構成の変更を要求するためのシステム構成変更要求パケットを、入力パケットとして受付キュー１に渡す。
【００５３】
システム構成設定部６４は、システム構成変更要求パケットについて合意部２６２によって合意された結果、つまりシステム構成変更要求パケットが合意部２６２によって確定された結果、当該システム構成変更要求パケットが合意部２６２から渡された場合、当該システム構成変更要求パケットで要求された分散システムの構成の変更を行う。
【００５４】
システム構成変更合意プロトコルデータ送受信部６５は、停滞しているコンピュータがシステム構成変更検出部６３によって検出された際に、他のコンピュータと合意を形成するためのシステム構成変更合意プロトコルデータの通信を行う。
【００５５】
図７は、システム構成変更合意プロトコルデータ送受信部６５によって送受信されるシステム構成変更合意プロトコルデータのレイアウトを示す図である。図７に示されるように、システム構成変更合意プロトコルデータは、種類、送信者、提案者、提案時タイムスタンプ、および停滞確認対象コンピュータ名（停滞している疑いをかけられているコンピュータ名）の各フィールドを含んでいる。停滞確認対象コンピュータ名フィールドは、整列マルチキャストプロトコルデータの入力パケットフィールドに相当する。つまり本実施形態では、停滞確認対象コンピュータ名フィールドの内容は、入力パケットとして扱われる。
【００５６】
システム構成変更合意プロトコルデータは、先頭の種類フィールドによって次の３つに使い分けられる。  
（１）報告種類
提案者フィールドで示される提案者（コンピュータ）が、定常的に停滞している他のコンピュータを検出したことを示す。送信者フィールド、および提案時タイムスタンプフィールドには、それぞれ、報告種類を示す種類フィールドを含むシステム構成変更合意プロトコルデータ（つまり報告種類のシステム構成変更合意プロトコルデータ）の送信者（送信側コンピュータ）を示すコンピュータ名、および停滞しているコンピュータを検出した際のタイムスタンプ（提案時のタイムスタンプ）が格納される。停滞確認対象コンピュータ名フィールドには、停滞の検出に関して確認が必要なコンピュータ（つまり停滞確認の対象となるコンピュータ）のコンピュータ名が格納される。送信者フィールドの示す送信者は、提案者フィールドの示す提案者に一致する。
【００５７】
（２）同意種類
報告種類のシステム構成変更合意プロトコルデータを受信したコンピュータが、同等な停滞を検出したことを示す。送信者フィールドには、同意種類を示す種類フィールドを含むシステム構成変更合意プロトコルデータ（つまり同意種類のシステム構成変更合意プロトコルデータ）の送信者を示すコンピュータ名が格納される。提案者フィールド、提案時タイムスタンプフィールド、および停滞確認対象コンピュータ名フィールドには、それぞれ報告種類のシステム構成変更合意プロトコルデータの対応するフィールドの内容のコピーが用いられる。
【００５８】
（３）非同意種類
報告種類のシステム構成変更合意プロトコルデータを受信したコンピュータが、同等な停滞を検出していないことを示す。送信者フィールドには、非同意種類を示す種類フィールドを含むシステム構成変更合意プロトコルデータ（つまり非同意種類のシステム構成変更合意プロトコルデータ）の送信者を示すコンピュータ名が格納される。提案者フィールド、提案時タイムスタンプフィールド、および停滞確認対象コンピュータ名フィールドには、それぞれ報告種類のシステム構成変更合意プロトコルデータの対応するフィールドの内容のコピーが用いられる。
【００５９】
システム構成通知プロトコルデータ送受信部６６は、システム構成を変更すべきことがシステム構成変更検出部６３によって検出されたタイミングで、待機状態にあったコンピュータを稼動状態にするためのシステム構成通知プロトコルデータを送受信する。システム構成通知プロトコルデータは、システム構成記憶部６１に格納されているデータ（システム構成情報）それ自体（つまりシステム構成記憶部６１のダンプ情報）を含む。
【００６０】
次に、分散システム１０内で稼動状態にあるコンピュータの動作原理について具体的に説明する。  
（初期化処理）
まず、コンピュータ１００-1〜１００-5のシステム構成記憶部６１は、分散システム１０の初期状態を示す情報を格納する。図５は、このときのシステム構成記憶部６１のデータ構造例を示しているものとする。ここでは、コンピュータ１００-1〜１００-4が稼動状態にあり、コンピュータ１００-5が待機状態にある。
【００６１】
稼動状態にあるコンピュータ１００-j（ｊ＝１〜４）の入力順序番号記憶部２１は、初期状態の入力順序番号、つまり初期入力順序番号（例えば１）を格納する。コンピュータ１００-jの入力パケットジャーナル記憶部２２および候補パケット記憶部２５は空の状態にある。
【００６２】
コンピュータ１００-jのステップ番号記憶部２４は初期ステップ番号（例えば１）を記憶し、最大確定入力順序番号記憶部２７は初期入力順序番号を格納する。コンピュータ１００-jの遅延記憶部２８の（ｎ−１）個のフラグ（ここでは３個のフラグ）はすべてリセットされており、最大確定入力順序番号履歴記憶部６２は現在のタイムスタンプとコンピュータ１００-1〜１００-4の各々の初期入力順序番号を記憶する。
【００６３】
コンピュータ１００-jの整列マルチキャスト部２が実行する整列マルチキャストによって各コンピュータへ配送される入力パケットを決定する処理は、アルゴリズム１〜９により実現される。
【００６４】
まず、アルゴリズム１〜４について、図８および図９を参照して説明する。図８および図９は、整列マルチキャストの１回の配送を行う基本的な部分の動作手順を示すフローチャートである。図８のフローチャート（第１のフローチャート）のステップＡ１はアルゴリズム１〜３全体を表し、残りのステップＡ２〜Ａ１３はアルゴリズム４を表す。図９のフローチャート（第２のフローチャート）のステップＢ１〜Ｂ４はアルゴリズム１を、ステップＢ５〜Ｂ８はアルゴリズム２を、そしてステップＢ９，Ｂ１０はアルゴリズム３を、それぞれ示す。
【００６５】
（アルゴリズム１）
整列マルチキャスト部２内の入力パケット確定判定部２６に含まれる入力候補収集部２６１は、コンピュータ１００-1〜１００-4（ｎ＝４）がそれぞれ次に処理する候補（入力候補）として選択した入力パケット（入力データ）を収集するための候補一覧作成処理（図８のステップＡ１）の一部（図９のステップＢ１〜Ｂ４）を次のように実行する。
【００６６】
入力候補収集部２６１は、ステップ番号記憶部２４に格納されている該当ステップ番号が初期値であるときは（図９のステップＢ１のＹＥＳ）、受付キュー１に入力パケットが存在するかを判定する（図９のステップＢ２）。
【００６７】
もし、入力パケットが存在するならば（図９のステップＢ２のＹＥＳ）、入力候補収集部２６１はステップ番号記憶部２４に格納されている該当ステップ番号を次に進める（図９のステップＢ３）。そして入力候補収集部２６１は、入力パケットを自候補として候補パケット記憶部２５に格納し、かつ、この自候補が入力パケットフィールドに設定された候補種類のプロトコルデータ（整列マルチキャストプロトコルデータ）を整列マルチキャストプロトコルデータ送受信部２３によりネットワークＢを介して他のすべてのコンピュータ（つまりコンピュータ１００-1〜１００-4のうち、コンピュータ１００-jを除くすべてのコンピュータ）に送信させる（図９のステップＢ４）。このステップＢ４において、入力候補収集部２６１は、候補パケット記憶部２５内のすべての他候補を空にする。
【００６８】
（アルゴリズム２）
一方、該当ステップ番号が初期値でないか（図９のステップＢ１のＮＯ）、または受付キュー１に入力パケットがないとき（図９のステップＢ２のＮＯ）、入力候補収集部２６１は、入力順序番号記憶部２１に格納されている該当入力順序番号に一致する入力順序番号（が設定された入力順序番号フィールド）を持つ候補種類の整列マルチキャストプロトコルデータが整列マルチキャストプロトコルデータ送受信部２３によって受信されているかを判定する（図９のステップＢ５）。もし、受信されているならば（図９のステップＢ５のＹＥＳ）、入力候補収集部２６１は、受信されている整列マルチキャストプロトコルデータ（受信整列マルチキャストプロトコルデータ）内の（ステップ番号フィールドに設定されている）ステップ番号は該当ステップ番号よりも大きいかを判定する（図９のステップＢ６）。
【００６９】
もし、受信整列マルチキャストプロトコルデータ内のステップ番号が該当ステップ番号よりも大きいならば（図９のステップＢ６のＹＥＳ）、入力候補収集部２６１は、ステップ番号記憶部２４に格納されている該当ステップ番号を受信整列マルチキャストプロトコルデータ内のステップ番号に更新する（図９のステップＢ７）。
【００７０】
次に入力候補収集部２６１は、受信整列マルチキャストプロトコルデータ内の（入力パケットフィールドに設定されている）入力パケットを自候補として候補パケット記憶部２５に格納し、かつ、この自候補が入力パケットフィールドに設定された（つまり受信整列マルチキャストプロトコルデータ内の入力パケットフィールドのコピーを含む）候補種類の整列マルチキャストプロトコルデータを整列マルチキャストプロトコルデータ送受信部２３によりネットワークＢを介して他のすべてのコンピュータに送信させる（図９のステップＢ８）。このステップＢ８において入力候補収集部２６１は、受信整列マルチキャストプロトコルデータ内の入力パケット（ここでは自候補とされた入力パケット）を、当該受信整列マルチキャストプロトコルデータの（送信者フィールドの示す）送信者に対応する他候補として、候補パケット記憶部２５に格納する。つまりステップＢ８では、受信整列マルチキャストプロトコルデータ中の入力パケットが、自候補として設定されるとともに、当該受信整列マルチキャストプロトコルデータの送信者に対応する他候補としても設定される。このとき入力候補収集部２６１は、候補パケット記憶部２５内の、受信整列マルチキャストプロトコルデータの送信者に対応する他候補以外の他候補をすべて破棄する（空にする）。
【００７１】
（アルゴリズム３）
これに対し、受信整列マルチキャストプロトコルデータ内のステップ番号と該当ステップ番号とが等しいならば（図９のステップＢ６のＮＯ，ステップＢ９のＹＥＳ）、入力候補収集部２６１は、受信整列マルチキャストプロトコルデータ内の入力パケットを、当該受信整列マルチキャストプロトコルデータの送信者に対応する他候補として候補パケット記憶部２５に格納する（図９のステップＢ１０）。
【００７２】
入力候補収集部２６１は、ステップＢ６またはステップＢ１０を実行すると、候補パケット記憶部２５に格納された候補数が（ｎ−ｔ）個以上（ｎ＝４、ｔ＝１の例では３個以上）になったかを判定する（図９のステップＢ１１）。
【００７３】
入力候補収集部２６１は、候補数が（ｎ−ｔ）個以上になっていないならば（図９のステップＢ１１のＮＯ）、ステップＢ１からの処理を再び実行する。これに対し、候補数が（ｎ−ｔ）個以上になっているならば（図９のステップＢ１１のＹＥＳ）、入力候補収集部２６１は候補一覧作成処理を終了する。なお、ステップＢ５またはステップＢ９の判定がＮＯの場合にも、ステップＢ１からの処理が再び実行される。
【００７４】
（アルゴリズム４）
候補一覧作成処理（図８のステップＡ１）が終了すると、即ち候補パケット記憶部２５に格納された候補（入力候補）数（空でない候補数）が（ｎ−ｔ）個以上になると、入力パケット確定判定部２６内の合意部２６２は第１の入力候補選定制御手段として機能して、当該候補パケット記憶部２５に（ｎ−ｔ）個以上の同一の候補が存在するか、つまり（ｎ−ｔ）台以上のコンピュータで合意がとられた（合意が形成された）候補が存在するかを判定する（図８のステップＡ２）。
【００７５】
もし、（ｎ−ｔ）個以上の同一（同一内容）の候補が存在するならば（図８のステップＡ２のＹＥＳ）、合意部２６２は、その候補を該当入力順序番号における入力パケットとして確定する（図８のステップＡ３）。このステップＡ３において合意部２６２は、最大確定入力順序番号記憶部２７に格納されている該当最大確定入力順序番号を該当入力順序番号に更新する。また、ステップＡ３において合意部２６２は、確定された入力パケットが受付キュー１に存在するならば、当該入力パケットを受付キュー１から削除する。
【００７６】
このように、該当入力順序番号における入力パケットが確定すると、つまり該当入力順序番号における入力パケットに関して合意がとられて、整列マルチキャストが確定すると、合意部２６２は図８のステップＡ４に進む。このステップＡ４において合意部２６２は、候補出力先切り替え手段として機能して、確定された入力パケットに付されている処理種別情報の示す処理種別が「構成」であるか否（「アプリケーション」である）か、つまり確定された入力パケットがシステム構成変更を要求するシステム構成変更要求パケットであるかを判定する。システム構成変更要求パケットの詳細については、後述するアルゴリズム１２の処理の中で説明する。
【００７７】
もし、処理種別が「構成」であるならば、つまり確定された入力パケットがシステム構成変更要求パケットであるならば（図８のステップＡ４のＹＥＳ）、合意部２６２は、確定された入力パケットをシステム構成管理部６内のシステム構成設定部６４に渡すとともに、当該入力パケットを入力パケットジャーナル記憶部２２に格納する（図８のステップＡ５）。
【００７８】
システム構成設定部６４は、合意部２６２から確定された入力パケットを受け取ると、当該パケットがコンピュータ１００-j自身（自コンピュータ）を待機状態に変更することを要求するシステム構成変更要求パケットであるかを判定する（図８のステップＡ６）。もし、自コンピュータを待機状態に変更することを要求するシステム構成変更要求パケットである場合（図８のステップＡ６のＹＥＳ）、システム構成設定部６４は上述の初期化処理を実施して自コンピュータを待機状態にする（図８のステップＡ７）。待機状態となったコンピュータのシステム構成管理部６は、稼動状態にあるコンピュータから、待機状態から稼動状態への変更を通知するシステム構成通知プロトコルデータが送られるのを待つ。一方、待機状態となったコンピュータの整列マルチキャスト部２は、例えば省電力化のために動作を停止する。
【００７９】
これに対し、確定された入力パケットが、他のコンピュータを待機状態に変更することを要求するシステム構成変更要求パケットである場合（図８のステップＡ６のＮＯ）、システム構成設定部６４は、システム構成記憶部６１に格納されているシステム構成情報を、変更後のシステム構成を示すように更新するとともに、その更新後のシステム構成情報を含むシステム構成通知プロトコルデータ（つまり変更後のシステム構成を通知するためのシステム構成通知プロトコルデータ）をシステム構成通知プロトコルデータ送受信部６６により、分散システムを構成する他のすべてのコンピュータに送信させる（図８のステップＡ８）。この場合、合意部２６２は、次工程へ移行すべく、入力順序番号記憶部２１に格納されている該当入力順序番号を次に進め（１インクリメントし）、ステップ番号記憶部２４に格納されている該当ステップ番号を初期化する（図８のステップＡ９）。このステップＡ９において合意部２６２は、候補パケット記憶部２５に格納されているすべての候補を破棄し（空にし）、遅延記憶部２８に格納されている（ｎ−１）個の遅延フラグをすべてリセットする。
【００８０】
一方、処理種別が「構成」でないならば、つまり確定された入力パケットがシステム構成変更要求パケットでない場合（図８のステップＡ４のＮＯ）、合意部２６２は、当該入力パケットをアプリケーションプログラム３に配送するとともに、当該入力パケットを入力パケットジャーナル記憶部２２に格納する（図８のステップＡ１０）。ここでは、確定された入力パケットは、現在入力パケットジャーナル記憶部２２に格納されている入力パケットの列の後ろに位置するように格納される。なお、入力パケットジャーナル記憶部２２に格納されている入力パケットの列が一定の量に達しているならば、先頭の入力パケット（つまり最も古い入力パケット）が破棄される。その後、合意部２６２は、次工程へ移行すべく、上記ステップＡ９を実行する。
【００８１】
一方、（ｎ−ｔ）個以上の同一の候補が存在しなかった場合（図８のステップＡ２のＮＯ）、合意部２６２は第２の入力候補選定制御手段として機能して、今度は、候補パケット記憶部２５に過半数以上の同一の候補が存在するかを判定する（図８のステップＡ１１）。もし、過半数以上の同一の候補が存在するならば（図８のステップＡ１１のＹＥＳ）、合意部２６２は、その候補を選択して自候補として候補パケット記憶部２５に格納し（つまり、その候補を候補パケット記憶部２５内の自候補とし）、かつ、この自候補が入力パケットフィールドに設定された候補種類のプロトコルデータ（整列マルチキャストプロトコルデータ）を整列マルチキャストプロトコルデータ送受信部２３によりネットワークＢを介して他のすべてのコンピュータに送信させる（図８のステップＡ１２）。このステップＡ１２において合意部２６２は、候補パケット記憶部２５に格納されているすべての他候補を破棄する。
【００８２】
これに対し、過半数以上の同一の候補が存在しないならば（図８のステップＡ１１のＮＯ）、合意部２６２は第３の入力候補選定制御手段として機能して、候補パケット記憶部２５に格納されている入力候補の中からランダムに候補（入力パケット）を自候補として選択し、かつ、この自候補が入力パケットフィールドに設定された候補種類のプロトコルデータ（整列マルチキャストプロトコルデータ）を整列マルチキャストプロトコルデータ送受信部２３によりネットワークＢを介して他のすべてのコンピュータに送信させる（図８のステップＡ１３）。このステップＡ１３において合意部２６２は、候補パケット記憶部２５に格納されているすべての他候補を破棄する。
【００８３】
ステップＡ１２（第２の入力候補選定制御手段としての動作）またはステップＡ１３（第３の入力候補選定制御手段としての動作）が終了すると、ステップＡ１からの処理が再び実行される。一方、ステップＡ７またはステップＡ９が終了すると、整列マルチキャストの１回の配送処理が終了する。
【００８４】
以上の手順で、多重化を構成する各コンピュータ１００-j、つまりコンピュータ１００-1〜１００-4は、（ｎ−ｔ）台（ここでは３台）以上のコンピュータでの入力パケットの一致を確認しながら処理を進めていく。
【００８５】
次に、アルゴリズム５〜９について、図１０乃至図１３を参照して説明する。図１０乃至図１３は、多重化実行の遅延を解消するための処理の手順を示すフローチャートである。図１０のフローチャート（第１のフローチャート）のステップＣ１，Ｃ２はアルゴリズム５を表し、ステップＣ３はアルゴリズム７を表す。図１１のフローチャート（第２のフローチャート）はアルゴリズム６を、図１２のフローチャート（第３のフローチャート）はアルゴリズム８を、そして図１３のフローチャート（第１のフローチャート）はアルゴリズム９を、それぞれ示す。
【００８６】
（アルゴリズム５）
整列マルチキャスト部２内の合意部２６２は、該当入力順序番号より小さい入力順序番号を持つ候補種類の整列マルチキャストプロトコルデータが整列マルチキャストプロトコルデータ送受信部２３によって受信された場合に、その入力順序番号に対応する入力パケットが入力パケットジャーナル記憶部２２に存在するかを判定する（図１０のステップＣ１）。
【００８７】
もし、該当入力順序番号より小さい入力順序番号に対応する入力パケットが入力パケットジャーナル記憶部２２に存在するならば（図１０のステップＣ１のＹＥＳ）、つまり短い多重化実行の遅延のために、該当入力順序番号より小さい入力順序番号に対応する入力パケットが入力パケットジャーナル記憶部２２に残されているならば、合意部２６２は、その入力パケットが入力パケットフィールドに設定された確定種類の整列マルチキャストプロトコルデータを整列マルチキャストプロトコルデータ送受信部２３によりネットワークＢを介して受信整列マルチキャストプロトコルデータの送信者に返送させる（図１０のステップＣ２）。
【００８８】
（アルゴリズム６）
また、合意部２６２は、該当入力順序番号に一致する入力順序番号を持つ確定種類の整列マルチキャストプロトコルデータが整列マルチキャストプロトコルデータ送受信部２３によって受信された場合には、その受信整列マルチキャストプロトコルデータ内の入力パケットを入力パケットとして確定する（図１１のステップＤ１）。このステップＤ１において合意部２６２は、確定された入力パケットが受付キュー１に存在するならば、当該入力パケットを受付キュー１から削除する。またステップＤ１では、受信整列マルチキャストプロトコルデータ内の最大確定入力順序番号が、最大確定入力順序番号記憶部２７に格納されている該当最大確定入力順序番号よりも大きいならば、該当最大確定入力順序番号が受信整列マルチキャストプロトコルデータ内の最大確定入力順序番号に更新される。
【００８９】
ステップＤ１の後、前述のアルゴリズム４におけるステップＡ４乃至Ａ９に相当する処理Ｄ２乃至Ｄ７が次のように実行される。まず合意部２６２は、確定された入力パケットに付されている処理種別情報の示す処理種別が「構成」であるか否（「アプリケーション」である）か、つまり確定された入力パケットがシステム構成変更を要求するシステム構成変更要求パケットであるかを判定する（図１１のステップＤ２）。
【００９０】
もし、処理種別が「構成」であり、したがって確定された入力パケットがシステム構成変更要求パケットであるならば（図１１のステップＤ２のＹＥＳ）、合意部２６２は、確定された入力パケットをシステム構成管理部６内のシステム構成設定部６４に渡すとともに、当該入力パケットを入力パケットジャーナル記憶部２２に格納する（図１１のステップＤ３）。
【００９１】
システム構成設定部６４は、合意部２６２から確定された入力パケットを受け取ると、当該パケットが自コンピュータを待機状態に変更することを要求するシステム構成変更要求パケットであるかを判定する（図１１のステップＤ４）。もし、自コンピュータを待機状態に変更することを要求するシステム構成変更要求パケットである場合（図１１のステップＤ４のＹＥＳ）、システム構成設定部６４は初期化処理を実施して自コンピュータを待機状態にする（図１１のステップＤ５）。
【００９２】
これに対し、確定された入力パケットが、他のコンピュータを待機状態に変更することを要求するシステム構成変更要求パケットである場合（図１１のステップＤ４のＮＯ）、システム構成設定部６４は、システム構成記憶部６１に格納されているシステム構成情報を、変更後のシステム構成を示すように更新するとともに、その更新後のシステム構成情報を含むシステム構成通知プロトコルデータ（つまり変更後のシステム構成を通知するためのシステム構成通知プロトコルデータ）をシステム構成通知プロトコルデータ送受信部６６により、分散システム１０を構成する他のすべてのコンピュータに送信させる（図１１のステップＤ６）。この場合、合意部２６２は、次工程へ移行すべく、入力順序番号記憶部２１に格納されている該当入力順序番号を次に進め（１インクリメントし）、ステップ番号記憶部２４に格納されている該当ステップ番号を初期化する（図１１のステップＤ７）。このステップＤ７において合意部２６２は、候補パケット記憶部２５に格納されているすべての候補を破棄し、遅延記憶部２８に格納されている（ｎ−１）個の遅延フラグをすべてリセットする。
【００９３】
一方、処理種別が「構成」でないならば、つまり確定された入力パケットがシステム構成変更を要求する入力パケットでない場合（図１１のステップＤ２のＮＯ）、合意部２６２は、当該入力パケットをアプリケーションプログラム３に配送するとともに、当該入力パケットを入力パケットジャーナル記憶部２２に格納する（図１１のステップＤ８）。その後、合意部２６２は、次工程へ移行すべく、上記ステップＤ７を実行する。
【００９４】
（アルゴリズム７）
一方、該当入力順序番号より小さい入力順序番号を持つ候補種類の整列マルチキャストプロトコルデータが受信された場合で、該当入力順序番号より小さい入力順序番号に対応する入力パケットが入力パケットジャーナル記憶部２２に存在しないならば（図１０のステップＣ１のＮＯ）、合意部２６２はステップＣ３に進む。つまり長い多重化実行の遅延のために、該当入力順序番号より小さい入力順序番号に対応する入力パケットが入力パケットジャーナル記憶部２２から既に捨てられている場合には（図１０のステップＣ１のＮＯ）、合意部２６２は、遅延種類の整列マルチキャストプロトコルデータを整列マルチキャストプロトコルデータ送受信部２３によりネットワークＢを介して受信整列マルチキャストプロトコルデータの送信者に返送させる（図１０のステップＣ３）。
【００９５】
（アルゴリズム８）
一方、整列マルチキャスト部２内のスキップ判定部２９は、該当入力順序番号に一致する入力順序番号を持つ遅延種類の整列マルチキャストプロトコルデータが整列マルチキャストプロトコルデータ送受信部２３によって受信された場合に、遅延記憶部２８に格納されている（ｎ−１）個の遅延フラグのうち、当該プロトコルデータの送信者に対応する遅延フラグをセットする（図１２のステップＥ１）。
【００９６】
（アルゴリズム９）
スキップ判定部２９は、遅延記憶部２８に格納されている（ｎ−１）個の遅延フラグのうちのセットされた遅延フラグの数と、候補パケット記憶部２５に格納されている入力候補の数との和が、（ｎ−ｔ）個以上に達したかどうかを監視する（図１３のステップＦ１）。もし、（ｎ−ｔ）個以上に達しているならば（図１３のステップＦ１のＹＥＳ）、スキップ判定部２９は、候補パケット記憶部２５に格納されている入力候補の数が（ｎ−ｔ）個未満かを判定する（図１３のステップＦ２）。もし、（ｎ−ｔ）個未満であるならば（図１３のステップＦ２のＹＥＳ）、スキップ判定部２９はスキップ動作を行う（図１３のステップＦ３）。即ちスキップ判定部２９は、入力順序番号記憶部２１に格納されている該当入力順序番号を最大確定入力順序番号記憶部２７に格納されている該当最大確定入力順序番号に更新し、ステップ番号記憶部２４に格納されている該当ステップ番号を初期ステップ番号にする。またスキップ判定部２９は、候補パケット記憶部２５を空にし、遅延記憶部２８のすべての遅延フラグをリセットした上で、システム構成管理部６およびプログラム状態管理部４にスキップを通知する。
【００９７】
システム構成管理部６のシステム構成設定部６４は、スキップ判定部２９からスキップが通知されると、他のコンピュータのシステム構成記憶部６１に格納されているシステム構成情報を自コンピュータのシステム構成記憶部６１にコピーする（図１３のステップＦ４）。システム構成設定部６４は、コピーされたシステム構成情報に基づき、自コンピュータを待機状態に変更する必要があるかを判定する（図１３のステップＦ５）。
【００９８】
もし、自コンピュータを待機状態に変更する必要があるならば（図１３のステップＦ５のＹＥＳ）、システム構成設定部６４は上述の初期化処理を実施して自コンピュータを待機状態にする（図１３のステップＦ６）。これに対し、自コンピュータを待機状態に変更する必要がないならば（図１３のステップＦ５のＮＯ）、システム構成設定部６４は何もせずに、処理を終了する。
【００９９】
一方、プログラム状態管理部４は、スキップ判定部２９からスキップが通知されると、該当入力順序番号の直前の状態を他のコンピュータのプログラム状態管理部４からコピーする（図１３のステップＦ７）。このために、プログラム状態管理部４は、各入力順序番号の直前の状態を最近のものから一定の量だけ保持している。
【０１００】
なお、図１３のフローチャートでは、システム構成設定部６４による処理の後にプログラム状態管理部４による処理（ステップＦ７）が実行されている。しかし、この処理の順序が逆であっても、或いは両方の処理が並行して実行されても構わない。
【０１０１】
次に、システム構成管理部６が実行するシステム構成変更のための処理について説明する。この処理は、アルゴリズム１０〜１４により実現される。  
（アルゴリズム１０）
まず、アルゴリズム１０について、図１４を参照して説明する。図１４は、システム構成管理部６のシステム構成変更検出部６３によって実行される、停滞しているコンピュータを探すための処理の手順を示すフローチャートである。
【０１０２】
システム構成変更検出部６３は、一定時間間隔Δｔ１毎に以下の処理を実行する（図１４のステップＧ１）。  
まずシステム構成変更検出部６３は、最大確定入力順序番号履歴記憶部６２を参照し、当該記憶部６２に格納されている最大確定入力順序番号履歴のうち、直近の時間Δｔ２（Δｔ２＞Δｔ１）の間に追加された最大確定入力順序番号の情報を取得する（図１４のステップＧ２）。この直近の時間Δｔ２の間に追加された最大確定入力順序番号の情報は、タイムスタンプに基づいて特定される。
【０１０３】
次にシステム構成変更検出部６３は、稼動状態にある他のコンピュータについて、自コンピュータの最大確定入力順序番号と比べてΔｉ（Δｉは１より大きい整数）以上最大確定入力順序番号が下回る（つまり自コンピュータよりもΔｉに相当する時間以上遅延している）という条件を満たす回数が一定回数以上発生しているかを、取得された最大確定入力順序番号の情報に基づいて判定する（図１４のステップＧ３）。システム構成変更検出部６３は、このステップＧ３の判定を、稼動状態にある他のすべてのコンピュータについて繰り返す（図１４のステップＧ４）。これによりシステム構成変更検出部６３は、上記条件を満たす回数が一定回数以上の稼動状態にあるコンピュータを探す。
【０１０４】
もし、このようなコンピュータを探したならば（図１４のステップＧ３のＹＥＳ）、システム構成変更検出部６３は、当該コンピュータは停滞（定常的に停滞）していると認定する。そこでシステム構成変更検出部６３は、例えば、停滞していると認定されたコンピュータを除く、他の稼動状態にあるコンピュータに対して、当該認定されたコンピュータを停滞確認の対象とする報告種類のシステム構成変更合意プロトコルデータを、システム構成変更合意プロトコルデータ送受信部６５により送信させる（図１４のステップＧ５）。
【０１０５】
（アルゴリズム１１）
次に、アルゴリズム１１について、図１５を参照して説明する。図１５は、システム構成変更検出部６３によって実行される、他のコンピュータから報告種類のシステム構成変更合意プロトコルデータを受け取った場合の処理の手順を示すフローチャートである。
【０１０６】
今、システム構成変更検出部６３が、他のコンピュータのシステム構成変更合意プロトコルデータ送受信部６５から送信された報告種類のシステム構成変更合意プロトコルデータを、自コンピュータのシステム構成変更合意プロトコルデータ送受信部６５を介して受け取ったものとする。するとシステム構成変更検出部６３は、最大確定入力順序番号履歴記憶部６２を参照し、当該記憶部６２に格納されている最大確定入力順序番号履歴のうち、直近の時間Δｔ２の間に追加された最大確定入力順序番号の情報を取得する（図１５のステップＨ１）。
【０１０７】
次にシステム構成変更検出部６３は、受け取ったシステム構成変更合意プロトコルデータで報告された停滞確認の対象となるコンピュータについて、自コンピュータの最大確定入力順序番号と比べてΔｉ以上下回るという条件を満たす回数が一定回数以上発生しているかを、取得された最大確定入力順序番号の情報に基づいて判定する（図１５のステップＨ２）。つまりシステム構成変更検出部６３は、報告された停滞確認の対象となるコンピュータが停滞しているかを検出する。
【０１０８】
もし、ステップＨ２の判定がＹＥＳであるならば、つまり報告された停滞確認の対象となるコンピュータの停滞が検出されたならば、システム構成変更検出部６３は、報告種類のシステム構成変更合意プロトコルデータの送信元のコンピュータに対して、同意種類のシステム構成変更合意プロトコルデータを、システム構成変更合意プロトコルデータ送受信部６５により返送させる（図１５のステップＨ３）。これに対し、ステップＨ２の判定がＮＯであるならば、つまり報告された停滞確認の対象となるコンピュータの停滞が検出されなかったならば、システム構成変更検出部６３は、報告種類のシステム構成変更合意プロトコルデータの送信元のコンピュータに対して、非同意種類のシステム構成変更合意プロトコルデータを、システム構成変更合意プロトコルデータ送受信部６５により返送させる（図１５のステップＨ４）。
【０１０９】
（アルゴリズム１２）
次に、アルゴリズム１２について、図１６を参照して説明する。図１６は、システム構成変更検出部６３によって実行される、報告種類のシステム構成変更合意プロトコルデータに対する応答として、他のコンピュータから同意種類または非同意種類のシステム構成変更合意プロトコルデータを受け取った場合の処理の手順を示すフローチャートである。
【０１１０】
今、システム構成変更検出部６３が、他のコンピュータのシステム構成変更合意プロトコルデータ送受信部６５から返された同意種類または非同意種類のシステム構成変更合意プロトコルデータを、自コンピュータのシステム構成変更合意プロトコルデータ送受信部６５を介して受け取ったものとする。するとシステム構成変更検出部６３は、受け取った同意種類または非同意種類のシステム構成変更合意プロトコルデータの提案者フィールドおよび提案時タイムスタンプフィールドを参照する（図１６のステップＩ１）。
【０１１１】
次にシステム構成変更検出部６３は、今回受け取ったシステム構成変更プロトコルデータを含めて、提案者および提案時タイムスタンプがいずれも報告種類のシステム構成変更合意プロトコルデータと同一の同意種類または非同意種類のシステム構成変更合意プロトコルデータを（ｎ−ｔ−１）個以上受け取ったかを判定する（図１６のステップＩ２）。
【０１１２】
もし、このようなシステム構成変更合意プロトコルデータを（ｎ−ｔ−１）個以上受け取ったならば（図１６のステップＩ２のＹＥＳ）、システム構成変更検出部６３は、そのうちの（ｎ−ｔ−１）個以上が同意種類のシステム構成変更合意プロトコルデータであるかを判定する（図１６のステップＩ３）。つまり、ステップＩ３においてシステム構成変更検出部６３は、提案者および提案時タイムスタンプがいずれも報告種類のシステム構成変更合意プロトコルデータと同一の同意種類のシステム構成変更合意プロトコルデータを（ｎ−ｔ−１）個以上受け取ったかを判定する。この判定は、（ｎ−ｔ）台以上の稼動状態にあるコンピュータの間で、停滞が検出されたコンピュータについて合意がとられているかを判定することと等価である。
【０１１３】
ステップＩ３の判定がＹＥＳの場合、つまり停滞が検出されたコンピュータについて（ｎ−ｔ）台以上の稼動状態にあるコンピュータの間で合意がとられていると判定された場合、システム構成変更検出部６３は、ステップＩ４に進む。このステップＩ４において、システム構成変更検出部６３はシステム構成記憶部６１を参照して、待機状態にあるコンピュータが存在するかを判定する。即ちシステム構成変更検出部６３は、停滞が検出されたコンピュータからフェイルオーバ可能なコンピュータが存在するかを判定する（図１６のステップＩ４）。
【０１１４】
ステップＩ４の判定がＹＥＳの場合、システム構成変更検出部６３は、システム構成変更要求パケットを生成し、当該システム構成変更要求パケットを入力パケットとして受付キュー１に積む（図１６のステップＩ５）。このシステム構成変更要求パケット（入力パケット）には、「構成」を示す処理種別情報が付されている。受付キュー１に積まれたシステム構成変更要求パケットは、入力パケットとして前述のアルゴリズム４で処理される。
【０１１５】
システム構成変更要求パケットは、システム構成情報を含む。システム構成変更検出部６３は、このシステム構成情報を、現在自コンピュータのシステム構成記憶部６１に格納されているシステム構成情報のコピーを利用して生成する。即ちシステム構成変更検出部６３は、システム構成情報のコピーのうち、停滞が検出されたことの合意がとられたコンピュータの状態を示す情報を待機状態を示すように更新するとともに、当該コンピュータの優先度を他の待機状態にあるコンピュータよりも低くなるように更新し、さらに、最も優先度の高い待機状態にあるコンピュータの状態を示す情報を稼動状態を示すように更新する。この更新されたシステム構成情報のコピーが、システム構成変更要求パケットに用いられる。したがってシステム構成変更要求パケットは、停滞が検出されたことの合意がとられたコンピュータを待機状態とすることを要求するとともに、当該コンピュータの優先度を他の待機状態にあるコンピュータよりも低く設定し、かつ最も優先度の高い待機状態にあるコンピュータを稼動状態とすることを要求する。つまりシステム構成変更要求パケットは、停滞が検出されたことの合意がとられたコンピュータから最も優先度の高い待機状態にあるコンピュータにフェイルオーバすることを要求するパケットである。  
一方、ステップＩ２，Ｉ３またはＩ４の判定がＮＯの場合、システム構成変更検出部６３は処理を終了する。
【０１１６】
（アルゴリズム１３）
次に、アルゴリズム１３について、図１７を参照して説明する。図１７は、システム構成設定部６４によって実行される、整列マルチキャスト部２の合意部２６２から確定されたシステム構成変更要求パケットを受け取った場合の処理の手順を示すフローチャートである。
【０１１７】
システム構成設定部６４は、合意部２６２から確定されたシステム構成変更要求パケットを受け取ると、以下の処理を分散システム１０を構成するすべてのコンピュータについて実行する（図１７のステップＪ１）。
【０１１８】
まずシステム構成設定部６４は、合意部２６２から渡されたシステム構成変更要求パケットに含まれているシステム構成情報（以下、新たなシステム構成情報と称する）を現在システム構成記憶部６１に格納されているシステム構成情報（以下、現システム構成情報と称する）と比較する（図１７のステップＪ２）。この比較の結果に基づき、システム構成設定部６４は、現在対象としているコンピュータについて、待機状態から稼動状態への変更が要求されているかを判定する（図１７のステップＪ３）。なお、稼動状態から待機状態への変更が要求されている場合、アルゴリズム４（具体的にはステップＡ４以降）で処理される。
【０１１９】
もし、現在対象としているコンピュータについて、待機状態から稼動状態への変更が要求されているならば（図１７のステップＪ３のＹＥＳ）、システム構成設定部６４は、自コンピュータのシステム構成通知プロトコルデータ送受信部６６から現在対象としているコンピュータ（つまり待機状態から稼動状態への変更が要求されたコンピュータ）のシステム構成通知プロトコルデータ送受信部６６に対して、システム構成通知プロトコルデータにより新たなシステム構成情報を送信させる（図１７のステップＪ４）。このシステム構成通知プロトコルデータ（新たなシステム構成情報）の送信により、送信先のコンピュータに対して、待機状態から稼動状態への変更が通知される。
【０１２０】
またシステム構成設定部６４は、自コンピュータ内の各記憶部に格納されている、稼動状態への変更が要求されたコンピュータに関する情報を初期化する（図１７のステップＪ５）。ここでは、遅延記憶部２８内の（ｎ−１）個の遅延フラグうちの、稼動状態への変更が要求されたコンピュータに新たに対応付けられる遅延フラグ、および、最大確定入力順序番号履歴記憶部６２内の最大確定入力順序番号履歴のうちの、稼動状態への変更が要求されたコンピュータに新たに対応付けられる最大確定入力順序番号履歴が初期化される。また、ステップＪ５では、システム構成記憶部６１に格納されている現システム構成情報が新たなシステム構成情報に更新される。
【０１２１】
（アルゴリズム１４）
次に、アルゴリズム１４について、図１８を参照して説明する。図１８は、システム構成設定部６４によって実行される、システム構成通知プロトコルデータ送受信部６６からシステム構成通知プロトコルデータを受け取った場合の処理の手順を示すフローチャートである。
【０１２２】
今、自コンピュータのシステム構成通知プロトコルデータ送受信部６６が他のコンピュータのシステム構成通知プロトコルデータ送受信部６６から送信されたシステム構成通知プロトコルデータを受信したものとする。システム構成通知プロトコルデータ送受信部６６は、自身が受信したシステム構成通知プロトコルデータを自コンピュータ内のシステム構成設定部６４に渡す。
【０１２３】
システム構成設定部６４は、システム構成通知プロトコルデータ送受信部６６からシステム構成通知プロトコルデータを受け取ると、自コンピュータが待機状態にあるかを判定する（図１８のステップＫ１）。もし、自コンピュータが待機状態にあるならば（図１８のステップＫ１のＹＥＳ）、システム構成設定部６４は受け取ったシステム構成通知プロトコルデータが、自コンピュータを稼動状態に変更することを示すシステム構成情報を含んでいるかを判定する（図１８のステップＫ２）
もし、システム構成通知プロトコルデータが自コンピュータを稼動状態に変更することを示しているならば（図１８のステップＫ２のＹＥＳ）、システム構成設定部６４は、システム構成記憶部６１に格納されているシステム構成情報を、当該プロトコルデータに含まれているシステム構成情報に更新する（図１８のステップＫ３）。そしてシステム構成設定部６４は、初期化処理を行い、整列マルチキャスト部２を動作可能状態にする（図１８のステップＫ４）。
【０１２４】
一方、ステップＫ１またはＫ２の判定がＮＯの場合、システム構成設定部６４は処理を終了する。例えば、システム構成変更要求パケットによって稼動状態から待機状態に変更することが要求されているコンピュータのシステム構成変更検出部６３では、ステップＫ１の判定がＮＯとなる。この場合、システム構成変更検出部６３は、システム構成記憶部６１に格納されているシステム構成情報を新たなシステム構成情報に更新することなく処理を終了する。このようにしても、待機状態に変更することが要求されているコンピュータは、他の稼動状態にあるコンピュータから無視されるため何ら問題とならない。なお、稼動状態から待機状態に変更することが要求されているコンピュータにおいてシステム構成情報の更新が行われても構わない。
【０１２５】
なお、以上に述べたアルゴリズム１〜１４の順序は、必ずしもこの順序で実行されるというものではない。つまり、これらは、その動作条件が成立すれば独立して実行されるものである。
【０１２６】
本実施形態において、システム構成管理部６内のシステム構成変更検出部６３は、最大確定入力順序番号履歴記憶部６２に格納されている情報のうち、直近の一定時間（Δｔ２）における各コンピュータの整列マルチキャスト部２の処理状況を反映した情報に基づき、自コンピュータよりも最大確定入力順序番号がΔｉ（Δｉは１より大きい整数）以上下回ったコンピュータ（さらに詳細には、Δｉ以上下回った回数が一定回数以上となるコンピュータ）を、停滞しているコンピュータとして検出している（アルゴリズム１０）。Δｉを１より大きい整数としている理由は、ｔ−耐故障アルゴリズムを適用した分散システムでは、当該アルゴリズムが（ｎ−ｔ）台のコンピュータの合意があれば次の処理を実行できることによる。つまり、ｔ−耐故障アルゴリズムを適用すると、原理的に、分散システム内のあるコンピュータにとって、ｔ台のコンピュータは入力順序番号が１遅れている状態に見えてしまうためである。よって、Δｉを１より大きい整数とすることにより、停滞しているコンピュータの誤検出を防ぐことができる。
【０１２７】
また本実施形態では、停滞しているコンピュータを検出するための時間範囲Δｔ２を設定することで、一時的に停滞しているコンピュータが停滞しているコンピュータとして検出される不具合を防止できる。
【０１２８】
また本実施形態では、停滞しているコンピュータの検出について、（ｎ−ｔ）台以上のコンピュータで合意がとれたことを、フェイルオーバのきっかけとしている（アルゴリズム１２）。これにより、コンピュータ間で通信ができないという理由だけで、各々のコンピュータが通信相手のコンピュータを停滞していると判定して、スプリットブレインが発生するのを防ぐことができる。
【０１２９】
また本実施形態では、システム構成変更要求パケットを整列マルチキャストの入力パケットとしている（アルゴリズム１２）。これにより、停滞が確認されたために待機状態に変更されたコンピュータが復帰してきた際に、変更される前の処理は実行し、変更された後の処理は実行しないようにできる。
【０１３０】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。例えば、上記実施形態では、稼動状態に設定されるコンピュータ（多重化を構成するコンピュータ）の数ｎが４で、ｔが１である。しかし、ｎは４以上の整数であればよく、つまり稼動状態に設定されるコンピュータは４台以上であればよく、ｔは３ｔ＜ｎを満たす０より大きい整数であればよい。この場合、ｔ−耐故障アルゴリズムにより、ｎ台のコンピュータのうちの最大ｔ台の故障を許容することができる。
【０１３１】
特に、｛ｎ，ｔ｝を、上記条件を満たし、かつ（ｎ−ｔ）の値が最小値となるように設定するならば、ｎ台のコンピュータのうちの最大ｔ台の故障を許容するのに、最も少ない台数のコンピュータで合意をとることができる。ここで、ｔの条件３ｔ＜ｎを変形すると、ｔはｔ＜ｎ／３を満たす０より大きい整数であるといえる。このことから、（ｎ−ｔ）の値は、ｎに対して（ｎ−ｔ）＞２ｎ／３のような関係がある。したがって、｛ｎ，ｔ｝を、上記条件を満たし、かつ（ｎ−ｔ）の値が２ｎ／３を超える最小値となるように設定するならば、つまり｛ｎ，ｔ｝を、いわゆる過２／３の合意をとるように設定するならば、最も少ない台数のコンピュータで合意をとることができる。（ｎ−ｔ）の値が２ｎ／３を超える最小値となる｛ｎ，ｔ｝は、｛４，１｝，｛７，２｝，｛１０，３｝，｛１３，４｝…である。
【０１３２】
また上記実施形態では、システム構成変更検出部６３が停滞しているコンピュータを検出するのに、最大確定入力順序番号履歴記憶部６２に直近の時間Δｔ２の間に追加された最大確定入力順序番号の情報の数（つまり標本数）を特に考慮していない。しかし、この標本数が一定数以下、つまり時間Δｔ２における最大確定入力順序番号の変更が一定回数以下である場合、停滞しているコンピュータの検出を抑止するようにしても良い。このように、停滞しているコンピュータの検出に標本数が少ない場合を排除することで、誤検出を防止することができる。
【０１３３】
また、Δｔ２の間に最大確定入力順序番号履歴記憶部６２に追加された最大確定入力順序番号の情報を用いる代わりに、一定数の最大確定入力順序番号の情報を用いようにしてもよい。具体的には、自コンピュータについての変更された最大確定入力順序番号の情報の数（つまり自コンピュータについての標本数）を一定数として、これらの最大確定入力順序番号と対応する他のコンピュータについての最大確定入力順序番号とを比較して、最大確定入力順序番号が自コンピュータよりもΔｉ以上下回る数（つまり割合）が一定数以上となるコンピュータを、停滞しているコンピュータとして検出するようにしてもよい。このように、標本数を一定数とすることで、誤検出を防止することができる。
【０１３４】
また、時間Δｔ２の間に最大確定入力順序番号履歴記憶部６２に追加された各コンピュータの最大確定入力順序番号の情報に基づき、自コンピュータと比べてΔｉ以上最大確定入力順序番号が下回り、その番号の差分が時間の経過に応じて拡大しているコンピュータを、停滞しているコンピュータとして検出するようにしてもよい。このようにすると、停滞しているコンピュータを高精度で検出できる。
【０１３５】
また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。
【符号の説明】
【０１３６】
１…入力受付キュー部（受付キュー）、２…整列マルチキャスト部、３…アプリケーションプログラム、４…プログラム状態管理部、５…出力フィルタ部、６…システム構成管理部、１０…分散システム、２１…入力順序番号記憶部、２２…入力パケットジャーナル記憶部、２３…整列マルチキャストプロトコルデータ送受信部、２４…ステップ番号記憶部、２５…候補パケット記憶部、２６…入力パケット確定判定部、２７…最大確定入力順序番号記憶部、２８…遅延記憶部、２９…スキップ判定部、６１…システム構成記憶部、６２…最大確定入力順序番号履歴記憶部、６３…システム構成変更検出部、６４…システム構成設定部、６５…システム構成変更合意プロトコルデータ送受信部、６６…システム構成通知プロトコルデータ送受信部、１００-1〜１００-5，１００-i…コンピュータ、２００…クライアント装置、２６１…入力候補収集部、２６２…合意部。
【図１】
2010198442.tif 000003
【図２】
2010198442.tif 000004
【図３】
2010198442.tif 000005
【図４】
2010198442.tif 000006
【図５】
2010198442.tif 000007
【図６】
2010198442.tif 000008
【図７】
2010198442.tif 000009
【図８】
2010198442.tif 000010
【図９】
2010198442.tif 000011
【図１０】
2010198442.tif 000012
【図１１】
2010198442.tif 000013
【図１２】
2010198442.tif 000014
【図１３】
2010198442.tif 000015
【図１４】
2010198442.tif 000016
【図１５】
2010198442.tif 000017
【図１６】
2010198442.tif 000018
【図１７】
2010198442.tif 000019
【図１８】
2010198442.tif 000020