(57)【要約】【課題】障害発生コンピュータが運用開始時のｆで表される（ｆ＋１）台以上となっても、正常に動作するコンピュータが３台以上あれば、多重化を継続できるようにする。【解決手段】ネットワークで接続されたｍ台のコンピュータ１００-iの各々において、整列マルチキャスト部２の合意部２６２は、構成記憶部２１１に格納されている情報によって示される分散システムを構成するｎ台のコンピュータのうちの（ｎ−ｆ）台（ｆは３ｆ＜ｎを満たす最大の整数）以上のコンピュータで入力データの合意をとることで当該入力データを整列マルチキャストする。構成決定部２１０は、現在の分散システムを構成する各コンピュータの状態から、当該分散システムの構成を変更すべき事項が発生したかを判定し、当該変更すべき事項が発生したと判定したコンピュータが（ｎ−ｆ）台以上存在するかによって、構成記憶部２１１に格納されている情報を変更する。【選択図】      図２
2010152559.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークで接続されたｍ台（ｍは４より大きい整数）のコンピュータのうちｎ台（ｎは４＜ｎ≦ｍを満たす整数）のコンピュータを同期的に動作させる分散システムであって、
前記ｍ台のコンピュータの各々は、
同期的に動作させられるべきｎ台のコンピュータを識別する情報を、前記分散システムを構成するコンピュータを識別する情報として格納する構成記憶手段と、
前記構成記憶手段に格納されている情報によって識別される前記分散システムを構成するｎ台のコンピュータを同期的に動作させ、当該ｎ台のコンピュータのうちの（ｎ−ｆ）台（ｆは３ｆ＜ｎを満たす最大の整数）以上での多重化を保証するために、当該（ｎ−ｆ）台以上のコンピュータで入力データの合意をとることで当該入力データを整列マルチキャストする合意手段と、
前記構成記憶手段に格納されている情報によって識別される前記分散システムを構成するｎ台のコンピュータの状態から障害が発生したコンピュータを検出する障害検出手段と、
前記障害検出手段によって障害が発生したコンピュータが検出された場合、前記分散システムの構成を変更すべき事項が発生したと判定し、前記分散システムの構成を変更すべき事項が発生したと判定したコンピュータが（ｎ−ｆ）台以上存在するかによって、前記分散システムの構成を変更するかを決定し、前記分散システムの構成を変更すると決定した場合、前記構成記憶手段に格納されている情報を変更後の前記分散システムの構成を示すように更新する構成決定手段と
を具備することを特徴とする分散システム。
【請求項２】
前記構成決定手段は、前記障害発生が検出されたコンピュータが前記分散システムから切り離されるように、前記構成記憶手段に格納されている情報を更新する
ことを特徴とする請求項１記載の分散システム。
【請求項３】
前記構成決定手段は、前記分散システムの構成を変更すべき事項が発生したと判定した場合、その旨を示す特定の入力データを前記合意手段に与えて当該特定の入力データを整列マルチキャストさせることで、前記分散システムの構成を変更すべき事項が発生したと判定したコンピュータが（ｎ−ｆ）台以上存在することを確認することを特徴とする請求項２記載の分散システム。
【請求項４】
前記合意手段は、合意の対象となる整列マルチキャストを当該整列マルチキャストにシリアルに付される順序番号により管理し、
前記ｍ台のコンピュータの各々は、他のコンピュータ毎に、合意がとられた整列マルチキャストの最大の順序番号を格納する他コンピュータ最大順序番号記憶手段をさらに具備し、
前記障害検出手段は、前記合意手段によって管理される最新の前記整列マルチキャストの順序番号と前記他コンピュータ最大順序番号記憶手段に格納されている他のコンピュータ毎の整列マルチキャストの最大の順序番号との差が閾値を超えるかによって、当該他のコンピュータの障害発生を検出する
ことを特徴とする請求項１記載の分散システム。
【請求項５】
ｍ台（ｍは４より大きい整数）のコンピュータがネットワークで接続された分散システムにおいて、前記ｍ台のコンピュータのうちｎ台（ｎは４＜ｎ≦ｍを満たす整数）のコンピュータを同期的に動作させて、（ｎ−ｆ）台（ｆは３ｆ＜ｎを満たす最大の整数）以上での多重化を保証する多重化制御方法であって、
前記ｍ台のコンピュータの各々は、同期的に動作させられるべきｎ台のコンピュータを識別する情報を、前記分散システムを構成するコンピュータを識別する情報として格納する構成記憶手段と、合意手段と、障害検出手段と、構成決定手段とを具備し、
前記多重化制御方法は、
前記ｍ台のコンピュータの各々の前記合意手段が、前記構成記憶手段に格納されている情報によって識別される前記分散システムを構成するｎ台のコンピュータを同期的に動作させ、当該ｎ台のコンピュータのうちの（ｎ−ｆ）台（ｆは３ｆ＜ｎを満たす最大の整数）以上での多重化を保証するために、当該（ｎ−ｆ）台以上のコンピュータで入力データの合意をとることで当該入力データを整列マルチキャストするステップと、
前記障害検出手段が、前記構成記憶手段に格納されている情報によって識別される前記分散システムを構成するｎ台のコンピュータの状態から障害が発生したコンピュータを検出するステップと、
障害が発生したコンピュータが検出された場合、前記分散システムの構成を変更すべき事項が発生したと判定し、前記分散システムの構成を変更すべき事項が発生したと判定したコンピュータが（ｎ−ｆ）台以上存在するかによって、前記分散システムの構成を変更するかを前記構成決定手段が決定するステップと、
前記分散システムの構成を変更すると決定された場合、前記構成記憶手段に格納されている情報を変更後の前記分散システムの構成を示すように前記構成決定手段が更新するステップと
を具備することを特徴とする多重化制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークで接続されたｍ台（ｍは４より大きい整数）のコンピュータのうちｎ台（ｎは４＜ｎ≦ｍを満たす整数）のコンピュータを同期的に動作させ、（ｎ−ｆ）台（ｆは３ｆ＜ｎを満たす最大の整数）以上での多重化を保証する分散システムに係り、特に当該ｎ台のコンピュータのいずれかで障害が発生した場合に好適な分散システムおよび同システムの多重化制御方法に関する。
【背景技術】
【０００２】
近年、コンピュータ技術やネットワーク技術の向上は目覚ましく、これに伴って、業務のコンピュータ化が広く行われている。また、その業務の内容によっては、故障などによる中断が許されないものも多く、最近では、複数のコンピュータをネットワークで結合した分散システムを構築することが一般的になりつつある。そして、この分散システムの運用手法の１つに、整列マルチキャストを用いた決定性のプログラムの実行の多重化が存在する。
【０００３】
整列マルチキャストは、分散システムへの入力をすべてのコンピュータに配送する仕組みであり、データの到着順序がすべてのコンピュータで同じであることを保証するものである。
【０００４】
分散システムにおける多重化の手法として、例えば特許文献１は、ｎ台（ｎは４以上の整数）のコンピュータ（つまり４台以上のコンピュータ）がネットワークで接続された分散システムにおいて、スプリットブレインを原理的に発生させず、タイムアウトによる故障発生時の処理の中断も発生させることがない手法を開示している。
【０００５】
この特許文献１が開示する従来の多重化手法（先行技術）においては、多重化を構成するコンピュータがｎ台（ｎは４以上の整数）の分散システムを例にとると、当該ｎ台のコンピュータを同期的に動作させ、当該ｎ台のコンピュータのうちの（ｎ−ｆ）台（ｆは、最大許容障害数と呼ばれる、３ｆ＜ｎを満たす最大の整数）以上での多重化を保証するために、当該ｎ台のコンピュータの各々は、入力候補収集手段と入力候補選定制御手段（第１の入力候補選定制御手段）とを具備する。入力候補収集手段は、ｎ台のコンピュータそれぞれが次に処理する候補として選択した入力データをネットワークを介して収集する。入力候補選定制御手段は、入力候補収集手段により収集された入力データが（ｎ−ｆ）個以上存在する場合に、その中に同一内容の入力データが（ｎ−ｆ）個以上あるか否かを判定し、（ｎ−ｆ）個以上あったときに、その入力データを次に処理する対象として確定する。これにより入力データが整列マルチキャストされる。このように、収集された（ｎ−ｆ）個以上の入力データの中に同一内容の入力データが（ｎ−ｆ）個以上あることを入力候補選定制御手段が判定することは、（ｎ−ｆ）台以上のコンピュータで入力データの合意をとることに他ならない。つまり入力候補選定制御手段は合意手段として機能することを意味する。
【特許文献１】特許第３６５５２６３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上記先行技術によれば、多重化を構成するコンピュータがｎ台（ｎは４以上の整数）の分散システムでは、ｆ台（ｆは３ｆ＜ｎを満たす最大の整数）までのコンピュータの故障（故障停止）が許容される。つまり、（ｎ−ｆ）台以上での多重化が保証（継続）される。このことは、上記先行技術では、故障停止（障害が発生）したコンピュータの数が（ｆ＋１）以上になると、多重化は継続できず、分散システムはフェイルストップすることを意味する。例えば、多重化を構成するコンピュータが７台（ｎ＝７）の分散システムでは、ｆは２となることから、２台までのコンピュータの故障停止は許容されるものの、さらに１台のコンピュータが故障停止すると、つまり３台のコンピュータが故障停止すると多重化を継続できない。
【０００７】
本発明は上記事情を考慮してなされたものでその目的は、障害が発生したコンピュータの数が運用開始時のｆで表される（ｆ＋１）以上となっても、正常に動作するコンピュータが３台以上あれば、多重化を継続できる分散システムおよび同システムの多重化制御方法を提供することにある。
【課題を解決するための手段】
【０００８】
本発明の１つの観点によれば、ネットワークで接続されたｍ台（ｍは４より大きい整数）のコンピュータのうちｎ台（ｎは４＜ｎ≦ｍを満たす整数）のコンピュータを同期的に動作させる分散システムが提供される。この分散システムにおいて、前記ｍ台のコンピュータの各々は、構成記憶手段と、合意手段と、障害検出手段と、構成決定手段とを具備する。前記構成記憶手段は、同期的に動作させられるべきｎ台のコンピュータを識別する情報を、前記分散システムを構成するコンピュータを識別する情報として格納する。前記合意手段は、前記構成記憶手段に格納されている情報によって識別される前記分散システムを構成するｎ台のコンピュータを同期的に動作させ、当該ｎ台のコンピュータのうちの（ｎ−ｆ）台（ｆは３ｆ＜ｎを満たす最大の整数）以上での多重化を保証するために、当該（ｎ−ｆ）台以上のコンピュータで入力データの合意をとることで当該入力データを整列マルチキャストする。前記障害検出手段は、前記構成記憶手段に格納されている情報によって識別される前記分散システムを構成するｎ台のコンピュータの状態から障害が発生したコンピュータを検出する。前記構成決定手段は、前記障害検出手段によって障害が発生したコンピュータが検出された場合、前記分散システムの構成を変更すべき事項が発生したと判定し、前記分散システムの構成を変更すべき事項が発生したと判定したコンピュータが（ｎ−ｆ）台以上存在するかによって、前記分散システムの構成を変更するかを決定し、前記分散システムの構成を変更すると決定した場合、前記構成記憶手段に格納されている情報を変更後の前記分散システムの構成を示すように更新する。
【発明の効果】
【０００９】
本発明によれば、現在分散システムを構成するｎ台のコンピュータのいずれかのコンピュータで障害が発生したために分散システムの構成を変更すべき事項が発生したと判定し、この分散システムの構成を変更すべき事項が発生したと判定したコンピュータが（ｎ−ｆ）台以上存在することの合意がとれたことをもって、分散システムの構成を変更することにより、障害が発生したコンピュータの数が運用開始時のｆで表される（ｆ＋１台）以上となっても、正常に動作するコンピュータが３台以上あれば、多重化を継続できる
【発明を実施するための最良の形態】
【００１０】
以下、本発明の実施の形態につき図面を参照して説明する。  
図１は本発明の一実施形態に係る分散システムの構成を示すブロック図である。図１において、分散システム１０００は、例えば７台のコンピュータ１００-1（＃１）〜１００-7（＃７）により多重化されているものとする。但し本実施形態では、分散システム１０００を構成するコンピュータの数は、当該システムの状況に応じて動的に変更される。
【００１１】
そこで、分散システム１０００の運用開始時の当該分散システム１０００を構成するコンピュータの数をｍで表し、現在の分散システム１０００を構成するコンピュータの数をｎで表すこともある。ｎは上記特許文献１と異なり４より大きい整数）である。なお、上記特許文献１では、分散システムを構成するコンピュータの数は変更されない。つまり上記特許文献１では、分散システムの構成が当該システムの状況に応じて変更されることはない。
【００１２】
ｍは４より大きい整数（つまり５以上の整数）である。つまり分散システム１０００の運用開始時の当該分散システム１０００を構成するコンピュータの数ｍは７に限るものではなく、４より大きければよい。明らかなように、ｎは、４＜ｎ≦ｍを満たす整数である。図１の例では、ｍ＝ｎ＝７であるが、本実施形態では、ｎは７から６に、６から５に変更される可能性がある。
【００１３】
コンピュータ１００-1〜１００-7は、ネットワークＡを介してクライアント装置２０００と接続されている。コンピュータ１００-1〜１００-7は、クライアント装置２０００以外のクライアント装置（図示せず）ともネットワークＡを介して接続されているものとする。本実施形態においてネットワークＡはパブリックネットワークである。コンピュータ１００-1〜１００-7間は、ネットワークＢを介して接続されている。本実施形態においてネットワークＢはプライベートネットワークである。
【００１４】
コンピュータ１００-1〜１００-7が分散システム１０００を構成している場合、コンピュータ１００-1〜１００-7は、前記特許文献１に記載された分散システムにおけるコンピュータと同様に、ネットワークＡを介してクライアント装置２０００から受け取った入力パケット（入力）を他のコンピュータと同じ順序で処理していく。なお、クライアント装置２０００からの入力パケットは、コンピュータ１００-1〜１００-7のうちのいずれかのコンピュータに入力される。
【００１５】
コンピュータ１００-1〜１００-7は、それぞれ同一のアプリケーションプログラム３（図２参照）を有している。コンピュータ１００-1〜１００-7は、同一の初期状態から始まる。その後、クライアント装置２０００から分散システムに入力されるデータは、必ず整列マルチキャストを通して、コンピュータ１００-1〜１００-7に同一順序で配送される。これにより、コンピュータ１００-1〜１００-7においてそれぞれのアプリケーションプログラム３が実行される。
【００１６】
コンピュータ１００-1〜１００-7がそれぞれ有するアプリケーションプログラム３への入力データ列は、整列マルチキャストにより同一順序となっている。このため、前記特許文献１に記載されているような決定性のプログラムの特徴により、コンピュータ１００-1〜１００-7の状態が同一に保たれ、出力データ列もすべて同じとなる。つまり、プログラムの実行が多重化される。
【００１７】
特許文献１に記載されている分散システムにおいて多重化を構成するコンピュータの数がｎ（ｎは４以上の整数）の場合、当該分散システムでは、ｆを３ｆ＜ｎを満足する最大の整数（最大許容障害数）とすると、ｆ台までの故障停止が許容される。つまり、ｎ台のコンピュータから構成される分散システムでは、（ｎ−ｆ）台以上のコンピュータの多重化が保証され、多重化されるプログラムは、少なくとも（ｎ−ｆ）台のコンピュータ上で実行される。したがって、ｎが４より大きい整数である本実施形態においても、（ｎ−ｆ）台以上のコンピュータの多重化が保証される。
【００１８】
図２は、コンピュータ１００-i（ｉ＝１，２，…，７）の構成を示すブロック図である。図２において、クライアント装置２０００からネットワークＡを介してコンピュータ１００-iに送信されて、当該コンピュータ１００-iの入力受付キュー部１で受け付けられた入力パケットは、当該入力受付キュー部１にキューイングされる。入力受付キュー部１にキューイングされた入力パケットは、整列マルチキャスト部２（内の後述する入力パケット確定判定部２６に含まれている合意部２６２）によってアプリケーションプログラム３または整列マルチキャスト部２内の後述する構成決定部２１０に配送される。なお、入力受付キュー部１にキューイングされる入力パケットには、クライアント装置２０００からの入力パケットの他に、構成決定部２１０から送られる入力パケット（特定入力パケット）がある。
【００１９】
アプリケーションプログラム３は、配送された入力パケットを受けて、プログラム状態管理部４に保存されている状態に従って当該入力パケットを処理し、出力パケットを生成する。生成された出力パケットは、出力フィルタ部５で選別されてから、ネットワークＡを介してクライアント装置２０００に返却される（出力）。
【００２０】
次に、コンピュータ１００-iの整列マルチキャスト部２の構成について説明する。整列マルチキャスト部２は、前記特許文献１に記載された整列マルチキャスト部と同様に、入力順序番号記憶部２１、入力パケットジャーナル記憶部２２、プロトコルデータ送受信部２３、ステップ番号記憶部２４、候補パケット記憶部２５、入力パケット確定判定部２６、最大確定入力順序番号記憶部２７、遅延記憶部２８およびスキップ判定部２９の周知の構成を有している。
【００２１】
入力順序番号記憶部２１は、整列マルチキャストによってコンピュータ１００-iへ次に配送される入力パケットの順序番号（つまり整列マルチキャストにシリアルに付される最新の順序番号）を格納する。入力パケットジャーナル記憶部２２は、整列マルチキャストによってコンピュータ１００-iへの配送が確定した入力パケットの列を最近のものから一定の量だけ格納する。プロトコルデータ送受信部２３は、他のコンピュータのプロトコルデータ送受信部２３とネットワークＢを介してプロトコルデータを授受する。
【００２２】
本実施形態では、クライアント装置２０００とコンピュータ１００-iとの間のデータの授受と、コンピュータ１００-i相互間のデータの授受とで、使用するネットワークが切り替えられる。これによりネットワーク負荷が軽減される。しかし、クライアント装置２０００とコンピュータ１００-iとの間のデータの授受と、コンピュータ１００-i相互間のデータの授受とが、例えばネットワークＡを介して行われる構成であっても構わない。またネットワークＡが必ずしもパブリックネットワークである必要はない。
【００２３】
ステップ番号記憶部２４、候補パケット記憶部２５および入力パケット確定判定部２６は、整列マルチキャストによってコンピュータ１００-iへ次に配送される入力パケットを決定するアルゴリズムで用いられる。ステップ番号記憶部２４は、プロトコルのステップを示すステップ番号を格納する。候補パケット記憶部２５は、そのステップにおける各コンピュータの「入力候補」となる入力パケットを計ｎ個格納する。
【００２４】
入力パケット確定判定部２６は、候補パケット記憶部２５の情報から入力パケットの確定の判定および次ステップの「入力候補」の決定を行う。入力パケット確定判定部２６はさらに、前記特許文献１に記載された入力パケット確定判定部と異なり、入力パケットをアプリケーションプログラム３および構成決定部２１０のいずれに渡すかを決定する。この決定のために、入力受付キュー部１にキューイングされる入力パケットには、処理種別を示す情報（処理種別情報）が付加される。入力パケット確定判定部２６は、入力候補収集部２６１及び合意部２６２を含む。
【００２５】
図３は入力受付キュー部１にキューイングされるデータ（入力パケットデータ）のデータ構造例を示す。図３に示されるように、入力パケットデータは、処理種別および入力パケットの各フィールドを含む。入力パケットフィールドには入力パケットが格納（設定）され、処理種別フィールドには処理種別情報が格納（設定）される。
【００２６】
本実施形態において処理種別情報は、入力パケットフィールドに格納されている入力パケットをアプリケーションプログラム３または構成決定部２１０のいずれに渡すかを入力パケット確定判定部２６（内の合意部２６２）が決定するための処理種別を示す。そのため、処理種別情報の示す処理種別は、（１）アプリケーションと（２）構成とに分けられる。処理種別が「アプリケーション」の場合、入力パケットが外部のクライアント装置２０００から入力されたものであることをも示し、処理種別が「構成」の場合、入力パケットが分散システム１０００を構成するいずれかのコンピュータの構成決定部２１０から当該いずれかのコンピュータの入力受付キュー部１に入力されたものであることをも示す。
【００２７】
再び図２を参照すると、最大確定入力順序番号記憶部２７は、他のコンピュータも含め、配送が確定したことがわかっている最大の入力順序番号を格納する。遅延記憶部２８は、他の（ｎ−１）台（ｎ＝７）のコンピュータよりも遅延しているかどうかを示す（ｎ−１）個の遅延フラグ（ｎ＝７の本実施形態では、６個のフラグ）を格納する。スキップ判定部２９は、遅延記憶部２８の情報からスキップ動作の必要性を判定およびスキップ動作を実行する。
【００２８】
図４は、最大確定入力順序番号記憶部２７のデータ構造例を示す。図４に示されるデータ構造例では、最大確定入力順序番号として「５００００」が格納されている。この場合、最大確定入力順序番号記憶部２７は、他のコンピュータも含め、配送が確定したことがわかっている最大の入力順序番号が「５００００」であることを示す。
【００２９】
以降の説明では、入力順序番号記憶部２１に格納された入力順序番号を該当入力順序番号と呼び、ステップ番号記憶部２４に格納されたステップ番号を該当ステップ番号と呼ぶ。コンピュータ１００-iの整列マルチキャスト部２に含まれている候補パケット記憶部２５に格納されているｎ個の「入力候補」のうち、当該コンピュータ１００-i自身（自コンピュータ）に対応する「入力候補」を自候補と呼び、当該自候補以外の「入力候補」を他候補と呼ぶ。
【００３０】
本実施形態では、整列マルチキャスト部２は、前記特許文献１に記載された整列マルチキャスト部と異なり、分散システム１０００を構成するコンピュータを、当該システム１０００の状況に応じて動的に変更するための新規の構成を含む。即ち整列マルチキャスト部２は、図２に示されるように、構成決定部２１０、構成記憶部２１１、最大順序番号遅延許容値記憶部２１２および他コンピュータ最大確定入力順序番号記憶部２１３をさらに含む。
【００３１】
構成決定部２１０は、分散システム１０００を構成するコンピュータを、当該システム１０００の状況（さらに詳細に述べるならば、現在当該システム１０００を構成しているコンピュータ１００-1〜１００-7の状況）に応じて決定する。構成記憶部２１１は、構成決定部２１０によって決定された分散システム１０００を構成するコンピュータを示す情報を格納する。本実施形態では、分散システム１０００を構成するコンピュータを示す情報として、当該コンピュータを一意に識別するための識別子(ＩＤ)が用いられる。構成決定部２１０は、構成記憶部２１１に格納されている情報（分散システム１０００を構成するコンピュータを示す情報）により、分散システム１０００において多重化を構成するコンピュータの数ｎと、当該ｎによって導かれる最大許容障害数ｆとを決定する。構成決定部２１０は、他のコンピュータの障害を検出する障害検出部２１０ａを含む。
【００３２】
図５は、構成記憶部２１１のデータ構造例を示す。図５に示されるデータ構造例では、コンピュータ＃１乃至＃７のＩＤ（ＩＤ＝１乃至ＩＤ＝７）が構成記憶部２１１に格納されている。この場合、構成記憶部２１１は、分散システム１０００がコンピュータ＃１乃至＃７から構成されており、ｎが７（ｎ＝７）で、ｆが２（ｆ＝２）であることを示す。
【００３３】
最大順序番号遅延許容値記憶部２１２は、後述する他コンピュータ最大確定入力順序番号記憶部２１３に格納されている、コンピュータ１００-i以外のコンピュータ（他コンピュータ）の最大確定入力順序番号の入力順序番号記憶部２１に格納されている該当入力順序番号（つまりコンピュータ１００-iにおいて管理されている最新の入力順序番号）に対するずれ（遅延）を許容する値（最大順序番号遅延許容値）Ｌを格納する。この値Ｌは例えばユーザによって任意に設定される。但し、Ｌは１より大きい整数である。
【００３４】
図６は、最大順序番号遅延許容値記憶部２１２のデータ構造例を示す。図６に示されるデータ構造例では、最大順序番号遅延許容値Ｌとして「３０００」が最大順序番号遅延許容値記憶部２１２に格納されている。この場合、他コンピュータの最大確定入力順序番号の該当入力順序番号に対する遅延は、順序番号の差に換算して「３０００」まで許容される。つまり、他コンピュータの最大確定入力順序番号の該当入力順序番号に対するずれが「３０００」を超えない範囲では、当該他コンピュータは正常であると構成決定部２１０によって判定される。換言するならば、他コンピュータの最大確定入力順序番号の該当入力順序番号に対するずれが「３０００」を超えると、当該他コンピュータは異常であると構成決定部２１０によって判定（検出）される。
【００３５】
本実施形態では、上述の最大確定入力順序番号（他コンピュータ最大確定入力順序番号記憶部２１３に格納されている最大確定入力順序番号）を利用したコンピュータ１００-iの異常検出（つまり分散システム１０００の状況の変化）に応じて、分散システム１０００が再構成される。
【００３６】
他コンピュータ最大確定入力順序番号記憶部２１３は、分散システム１０００を構成するコンピュータの集合のうち、コンピュータ１００-i自身（自コンピュータ）を除くコンピュータ（他コンピュータ）に対応する最大確定入力順序番号を格納する。
【００３７】
図７は、コンピュータ１００-iがコンピュータ１００-1（＃１）である場合における、当該コンピュータ１００-1（＃１）の他コンピュータ最大確定入力順序番号記憶部２１３のデータ構造例を示す。図７に示されるデータ構造例では、コンピュータ１００-1（＃１）以外のコンピュータ１００-2（＃２）〜１００-7（＃７）の最大確定入力順序番号（５００００）が、当該コンピュータ１００-2（＃２）〜１００-7（＃７）の例えばＩＤに対応付けて他コンピュータ最大確定入力順序番号記憶部２１３に格納されている。
【００３８】
次に、プロトコルデータ送受信部２３によって送受信されるプロトコルデータについて説明する。  
図８は、プロトコルデータのレイアウトを示す図である。図８に示されるように、プロトコルデータ送受信部２３によって送受信されるプロトコルデータは、種類、送信者、入力順序番号、ステップ番号、最大確定入力順序番号、処理種別および入力パケットの各フィールドを含む。図８に示されるプロトコルデータが前記特許文献１に記載されているプロトコルデータと相違するのは、前述の処理種別フィールドが追加されている点にある。
【００３９】
周知のように、プロトコルデータは先頭の種類フィールドによって、次の３つに使い分けられる。
【００４０】
（１）候補種類：入力順序番号フィールド、ステップ番号フィールド、入力パケットフィールド、処理種別フィールドには、それぞれ、送信者（送信側コンピュータ）の送信時における該当入力順序番号、該当ステップ番号、自候補、自候補に付されていた処理種別（処理種別情報）が格納される。
【００４１】
（２）確定種類：その入力順序番号（入力順序番号フィールドに格納されている入力順序番号）に対応する入力パケットが、送信者の送信時における入力パケットジャーナル記憶部２２にあることを示し、入力パケットフィールド、処理種別フィールドには、それぞれ、その入力パケット、その入力パケットに付されていた処理種別（処理種別情報）が格納される。この場合、ステップ番号フィールドは使用されない。
【００４２】
（３）遅延種類：その入力順序番号に対応する入力パケットが、送信者の送信時における入力パケットジャーナル記憶部２２にないことを示す。この場合、ステップ番号フィールド、入力パケットフィールドおよび処理種別フィールドは使用されない。
【００４３】
いずれの種類のプロトコルデータにおいても、最大確定入力順序番号フィールドには、送信者（送信側コンピュータ）からのプロトコルデータ送信時における該当最大確定入力順序番号が格納される。また、プロトコルデータの受信側コンピュータにおける該当最大確定入力順序番号は、当該受信側コンピュータで確定された入力パケットの順序番号と、当該受信側コンピュータで受信されたプロトコルデータ中の最大確定入力順序番号とのうち、最も大きいものに更新される。
【００４４】
次に、図９乃至図１４のフローチャートを参照して、コンピュータ１００-iの整列マルチキャスト部２の動作手順について説明する。  
まず初期状態では、入力順序番号記憶部２１は初期入力順序番号（例えば１）を格納する。入力パケットジャーナル記憶部２２は空の状態であり、ステップ番号記憶部２４は初期ステップ番号（例えば１）を格納する。また、候補パケット記憶部２５は空の状態であり、最大確定入力順序番号記憶部２７は初期入力順序番号を格納し、さらに、遅延記憶部２８のすべてのフラグはリセットされている。
【００４５】
図９および図１０は、整列マルチキャストの１回の配送を行う基本的な部分の動作手順を示すフローチャートである。  
整列マルチキャスト部２内の入力パケット確定判定部２６に含まれる入力候補収集部２６１は、コンピュータ１００-1〜１００-7（ｎ＝７）がそれぞれ次に処理する候補（入力候補）として選択した入力パケット（入力データ）を収集するための候補一覧作成処理を実行する（図８のステップＡ１）。
【００４６】
候補一覧作成処理において入力候補収集部２６１は、ステップ番号記憶部２４に格納されている該当ステップ番号が初期値であるときは（図１０のステップＢ１のＹＥＳ）、入力受付キュー部１に入力パケット（より具体的には、入力パケットおよび処理種別情報から構成される入力パケットデータ）が存在するかを判定する（図１０のステップＢ２）。
【００４７】
もし、入力パケットが存在するならば（図１０のステップＢ２のＹＥＳ）、入力候補収集部２６１はステップ番号記憶部２４に格納されている該当ステップ番号を次に進める（図１０のステップＢ３）。そして入力候補収集部２６１は、入力パケットを自候補として候補パケット記憶部２５に格納し、かつ、この自候補が入力パケットフィールドに設定され、この自候補に付されている処理種別情報が処理種別フィールドに設定された候補種類のプロトコルデータをプロトコルデータ送受信部２３によりネットワークＢを介して他のすべてのコンピュータに送信させる（図１０のステップＢ４）。このステップＢ４において、入力候補収集部２６１は、候補パケット記憶部２５内の全ての他候補を空にする。
【００４８】
一方、該当ステップ番号が初期値でないか（図１０のステップＢ１のＮＯ）、または入力受付キュー部１に入力パケットがないとき（図１０のステップＢ２のＮＯ）、入力候補収集部２６１は、入力順序番号記憶部２１に格納されている該当入力順序番号に一致する入力順序番号（が設定された入力順序番号フィールド）を持つ候補種類のプロトコルデータがプロトコルデータ送受信部２３によって受信されているかを判定する（図１０のステップＢ５）。もし、受信されているならば（図１０のステップＢ５のＹＥＳ）、入力候補収集部２６１は、受信されているプロトコルデータ（受信プロトコルデータ）内の（ステップ番号フィールドに設定されている）ステップ番号は該当ステップ番号よりも大きいかを判定する（図１０のステップＢ６）。
【００４９】
もし、受信プロトコルデータ内のステップ番号が該当ステップ番号よりも大きいならば（図１０のステップＢ６のＹＥＳ）、入力候補収集部２６１は、ステップ番号記憶部２４に格納されている該当ステップ番号を受信プロトコルデータ内のステップ番号に更新する（図１０のステップＢ７）。このステップＢ７では、受信プロトコルデータ内の（最大確定入力順序番号フィールドに設定されている）最大確定入力順序番号が、最大確定入力順序番号記憶部２７に格納されている該当最大確定入力順序番号よりも大きいならば、この該当最大確定入力順序番号が受信プロトコルデータ内の最大確定入力順序番号に更新される。以降の説明では、該当最大確定入力順序番号が受信プロトコルデータ内の最大確定入力順序番号に更新される処理を該当最大確定入力順序番号更新処理と称する。またステップＢ７では、受信プロトコルデータの送信者に対応して他コンピュータ最大確定入力順序番号記憶部２１３に格納されている最大確定入力順序番号が、受信プロトコルデータ内の最大確定入力順序番号に更新される。
【００５０】
次に入力候補収集部２６１は、受信プロトコルデータ内の（入力パケットフィールドに設定されている）入力パケットを自候補として候補パケット記憶部２５に格納し、かつ、この自候補が入力パケットフィールドに設定され、この自候補に付されている処理種別情報が処理種別フィールドに設定された（つまり受信プロトコルデータ内の入力パケットフィールドおよび処理種別フィールドのコピーを含む）候補種類のプロトコルデータをプロトコルデータ送受信部２３によりネットワークＢを介して他のすべてのコンピュータに送信させる（図１０のステップＢ８）。このステップＢ８において入力候補収集部２６１は、受信プロトコルデータ内の入力パケット（ここでは自候補とされた入力パケット）を、当該受信プロトコルデータの（送信者フィールドの示す）送信者に対応する他候補として、候補パケット記憶部２５に格納する。つまりステップＢ８では、受信プロトコルデータ中の入力パケットが、自候補として設定されるとともに、当該受信プロトコルデータの送信者に対応する他候補としても設定される。このとき入力候補収集部２６１は、候補パケット記憶部２５内の、受信プロトコルデータの送信者に対応する他候補以外の他候補を全て破棄する（空にする）。
【００５１】
これに対し、受信プロトコルデータ内のステップ番号と該当ステップ番号とが等しいならば（図１０のステップＢ６のＮＯ，ステップＢ９のＹＥＳ）、入力候補収集部２６１は、受信プロトコルデータ内の入力パケットを、当該受信プロトコルデータの送信者に対応する他候補として候補パケット記憶部２５に格納する（図１０のステップＢ１０）。このステップＢ１０では、受信プロトコルデータ内の最大確定入力順序番号が、最大確定入力順序番号記憶部２７に格納されている該当最大確定入力順序番号よりも大きいならば、該当最大確定入力順序番号更新処理が行われる。またステップＢ１０では、受信プロトコルデータの送信者に対応して他コンピュータ最大確定入力順序番号記憶部２１３に格納されている最大確定入力順序番号が、受信プロトコルデータ内の最大確定入力順序番号に更新される。
【００５２】
入力候補収集部２６１は、ステップＢ６またはステップＢ１０を実行すると、候補パケット記憶部２５に格納された候補数が（ｎ−ｆ）個以上になったかを判定する（図１０のステップＢ１１）。
【００５３】
入力候補収集部２６１は、候補数が（ｎ−ｆ）個以上になっていないならば（図１０のステップＢ１１のＮＯ）、ステップＢ１からの処理を再び実行する。これに対し、候補数が（ｎ−ｆ）個以上になっているならば（図１０のステップＢ１１のＹＥＳ）、入力候補収集部２６１は候補一覧作成処理を終了する。なお、ステップＢ５またはステップＢ９の判定がＮＯの場合にも、ステップＢ１からの処理が再び実行される。
【００５４】
候補一覧作成処理（図９のステップＡ１）が終了すると、即ち候補パケット記憶部２５に格納された候補（入力候補）数（空でない候補数）が（ｎ−ｆ）個以上になると、入力パケット確定判定部２６内の合意部２６２は第１の入力候補選定制御手段として機能して、当該候補パケット記憶部２５に（ｎ−ｆ）個以上の同一の候補が存在するか、つまり（ｎ−ｆ）台以上のコンピュータ（少なくとも（ｎ−ｆ）台のコンピュータ）で合意がとられた（合意が形成された）候補が存在するかを判定する（図９のステップＡ２）。もし、（ｎ−ｆ）個以上の同一（同一内容）の候補が存在するならば（図９のステップＡ２のＹＥＳ）、合意部２６２は、その候補を該当入力順序番号における入力パケットとして確定する（図９のステップＡ３）。このステップＡ３において合意部２６２は、確定された入力パケットが入力受付キュー部１に存在するならば、当該入力パケットを入力受付キュー部１から削除する。
【００５５】
このように、該当入力順序番号における入力パケットが確定すると、つまり該当入力順序番号における入力パケットに関して合意がとられて、整列マルチキャストが確定すると、合意部２６２は、次工程へ移行すべく、入力順序番号記憶部２１に格納されている該当入力順序番号を次に進め（１インクリメントし）、ステップ番号記憶部２４に格納されている該当ステップ番号を初期化する（図９のステップＡ４）。このステップＡ４において合意部２６２は、候補パケット記憶部２５に格納されているすべての候補を破棄し（空にし）、遅延記憶部２８に格納されている（ｎ−１）個の遅延フラグをすべてリセットする。
【００５６】
次に合意部２６２は、候補出力先切り替え手段として機能して、確定された入力パケットに付されている処理種別情報の示す処理種別が「アプリケーション」であるかどうか（つまり「構成」であるか）を調べる（図９のステップＡ８）。「アプリケーション」であるならば（図９のステップＡ８のＹＥＳ）、合意部２６２は、確定された入力パケットをアプリケーションプログラム３に渡すとともに、当該入力パケットを入力パケットジャーナル記憶部２２に格納する（図９のステップＡ９）。ここでは、確定された入力パケットは、現在入力パケットジャーナル記憶部２２に格納されている入力パケットの列の後ろに位置するように格納される。なお、入力パケットジャーナル記憶部２２に格納されている入力パケットの列が一定の量に達しているならば、先頭の入力パケット（つまり最も古い入力パケット）が破棄される。
【００５７】
これに対し、「アプリケーション」でないならば、つまり「構成」であるならば（図９のステップＡ８のＮＯ）、合意部２６２は、確定された入力パケットを構成決定部２１０に渡すとともに、当該入力パケットを入力パケットジャーナル記憶部２２に格納する（図９のステップＡ１０）。
【００５８】
一方、（ｎ−ｆ）個以上の同一の候補が存在しなかった場合（図９のステップＡ２のＮＯ）、合意部２６２は第２の入力候補選定制御手段として機能して、今度は、候補パケット記憶部２５に過半数以上の同一の候補が存在するかを判定する（図９のステップＡ５）。もし、過半数以上の同一の候補が存在するならば（図９のステップＡ５のＹＥＳ）、合意部２６２は、その候補を選択して自候補として候補パケット記憶部２５に格納し（つまり、その候補を候補パケット記憶部２５内の自候補とし）、かつ、この自候補が入力パケットフィールドに設定され、この自候補に付されている処理種別情報が処理種別フィールドに設定された候補種類のプロトコルデータをプロトコルデータ送受信部２３によりネットワークＢを介して他のすべてのコンピュータに送信させる（図９のステップＡ６）。このステップＡ６において合意部２６２は、候補パケット記憶部２５に格納されているすべての他候補を破棄する。
【００５９】
これに対し、過半数以上の同一の候補が存在しないならば（図９のステップＡ５のＮＯ）、合意部２６２は第３の入力候補選定制御手段として機能して、候補パケット記憶部２５に格納されている入力候補の中からランダムに候補（入力パケット）を自候補として選択し、かつ、この自候補が入力パケットフィールドに設定され、この自候補に付されている処理種別情報が処理種別フィールドに設定された候補種類のプロトコルデータをプロトコルデータ送受信部２３によりネットワークＢを介して他のすべてのコンピュータに送信させる（図９のステップＡ７）。このステップＡ７において合意部２６２は、候補パケット記憶部２５に格納されているすべての他候補を破棄する。
【００６０】
合意部２６２は、ステップＡ６（第２の入力候補選定制御手段としての動作）またはステップＡ７（第３の入力候補選定制御手段としての動作）が終了すると、ステップＡ１からの処理を再び実行する。一方、ステップＡ９またはステップＡ１０（候補出力先切り替え手段としての動作）が終了すると、整列マルチキャストの１回の配送処理を終了する。
【００６１】
以上の手順で、各コンピュータ１００-iは、（ｎ−ｆ）台以上のコンピュータでの入力パケットの一致を確認しながら処理を進めていく。
【００６２】
次に、多重化実行の遅延を解消するための動作手順について説明する。  
図１１乃至図１４は、多重化実行の遅延を解消するための動作手順を示すフローチャートである。図１１乃至図１４は、前記特許文献１の図７乃至図１０に相当する。
【００６３】
整列マルチキャスト部２内の合意部２６２は、該当入力順序番号より小さい入力順序番号を持つ候補種類のプロトコルデータがプロトコルデータ送受信部２３によって受信された場合に、その入力順序番号に対応する入力パケットが入力パケットジャーナル記憶部２２に存在するかを判定する（図１１のステップＣ１）。
【００６４】
もし、該当入力順序番号より小さい入力順序番号に対応する入力パケットが入力パケットジャーナル記憶部２２に存在するならば（図１１のステップＣ１のＹＥＳ）、つまり短い多重化実行の遅延のために、該当入力順序番号より小さい入力順序番号に対応する入力パケットが入力パケットジャーナル記憶部２２に残されているならば、合意部２６２は、その入力パケットが入力パケットフィールドに設定され、その入力パケットに付されている処理種別情報が処理種別フィールドに設定された確定種類のプロトコルデータをプロトコルデータ送受信部２３によりネットワークＢを介して受信プロトコルデータの送信者に返送させる（図１１のステップＣ２）。
【００６５】
一方、該当入力順序番号より小さい入力順序番号に対応する入力パケットが入力パケットジャーナル記憶部２２に存在しないならば（図１１のステップＣ１のＮＯ）、つまり長い多重化実行の遅延のために、該当入力順序番号より小さい入力順序番号に対応する入力パケットが入力パケットジャーナル記憶部２２から既に捨てられている場合には、合意部２６２は、遅延種類のプロトコルデータをプロトコルデータ送受信部２３によりネットワークＢを介して受信プロトコルデータの送信者に返送させる（図１１のステップＣ３）。
【００６６】
また、ステップＣ２およびＣ３では、受信プロトコルデータ内の最大確定入力順序番号が、最大確定入力順序番号記憶部２７に格納されている該当最大確定入力順序番号よりも大きいならば、該当最大確定入力順序番号更新処理が行われる。またステップＣ２およびＣ３では、受信プロトコルデータの送信者に対応して他コンピュータ最大確定入力順序番号記憶部２１３に格納されている最大確定入力順序番号が、受信プロトコルデータ内の最大確定入力順序番号に更新される。
【００６７】
また、合意部２６２は、該当入力順序番号に一致する入力順序番号を持つ確定種類のプロトコルデータがプロトコルデータ送受信部２３によって受信された場合には、その受信プロトコルデータ内の入力パケットを入力パケットとして確定する（図１２のステップＤ１）。このステップＤ１において合意部２６２は、確定された入力パケットが入力受付キュー部１に存在するならば、当該入力パケットを入力受付キュー部１から削除する。またステップＤ１では、受信プロトコルデータ内の最大確定入力順序番号が、最大確定入力順序番号記憶部２７に格納されている該当最大確定入力順序番号よりも大きいならば、該当最大確定入力順序番号更新処理が行われる。ステップＤ１ではさらに、受信プロトコルデータの送信者に対応して他コンピュータ最大確定入力順序番号記憶部２１３に格納されている最大確定入力順序番号が、受信プロトコルデータ内の最大確定入力順序番号に更新される。
【００６８】
次に合意部２６２は、次工程へ移行すべく、入力順序番号記憶部２１に格納されている該当入力順序番号を次に進め（１インクリメントし）、ステップ番号記憶部２４に格納されている該当ステップ番号を初期化する（図１２のステップＤ２）。このステップＤ２において合意部２６２は、候補パケット記憶部２５に格納されているすべての候補を破棄し、遅延記憶部２８に格納されている（ｎ−１）個の遅延フラグをすべてリセットする。
【００６９】
次に合意部２６２は、候補出力先切り替え手段として機能して、確定された入力パケットに付されている処理種別情報の示す処理種別が「アプリケーション」であるかを判定する（図１２のステップＤ３）。「アプリケーション」であるならば（図１２のステップＤ３のＹＥＳ）、合意部２６２は、確定された入力パケットをアプリケーションプログラム３に渡すとともに、当該入力パケットを入力パケットジャーナル記憶部２２に格納する（図１２のステップＤ４）。
【００７０】
これに対し、「アプリケーション」でないならば（図１２のステップＤ３のＮＯ）、合意部２６２は、確定された入力パケットを構成決定部２１０に渡すとともに、当該入力パケットを入力パケットジャーナル記憶部２２に格納する（図１２のステップＤ５）。
【００７１】
一方、整列マルチキャスト部２内のスキップ判定部２９は、該当入力順序番号に一致する入力順序番号を持つ遅延種類のプロトコルデータがプロトコルデータ送受信部２３によって受信された場合に、遅延記憶部２８に格納されている（ｎ−１）個の遅延フラグのうち、当該プロトコルデータの送信者に対応する遅延フラグをセットする（図１３のステップＥ１）。このステップＥ１では、受信プロトコルデータ内の最大確定入力順序番号が、最大確定入力順序番号記憶部２７に格納されている該当最大確定入力順序番号よりも大きいならば、該当最大確定入力順序番号更新処理が行われる。またステップＥ１では、受信プロトコルデータの送信者に対応して他コンピュータ最大確定入力順序番号記憶部２１３に格納されている最大確定入力順序番号が、受信プロトコルデータ内の最大確定入力順序番号に更新される。
【００７２】
また、スキップ判定部２９は、遅延記憶部２８に格納されている（ｎ−１）個の遅延フラグのうちのセットされた遅延フラグの数と、候補パケット記憶部２５に格納されている入力候補の数との和が、（ｎ−ｆ）個以上に達したかどうかを監視する（図１４のステップＦ１）。もし、（ｎ−ｆ）個以上に達しているならば（図１４のステップＦ１のＹＥＳ）、スキップ判定部２９は、候補パケット記憶部２５に格納されている入力候補の数が（ｎ−ｆ）個未満かを判定する（図１４のステップＦ２）。もし、（ｎ−ｆ）個未満であるならば（図１４のステップＦ２のＹＥＳ）、スキップ判定部２９はスキップ動作を行う（図１４のステップＦ３）。即ちスキップ判定部２９は、入力順序番号記憶部２１に格納されている該当入力順序番号を最大確定入力順序番号記憶部２７に格納されている該当最大確定入力順序番号に更新し、ステップ番号記憶部２４に格納されている該当ステップ番号を初期ステップ番号にする。またスキップ判定部２９は、候補パケット記憶部２５を空にし、遅延記憶部２８のすべての遅延フラグをリセットした上で、プログラム状態管理部４にスキップを通知する。プログラム状態管理部４は、スキップが通知されると、該当入力順序番号の直前の状態を他のコンピュータのプログラム状態管理部４からコピーする。このために、プログラム状態管理部４は、各入力順序番号の直前の状態を最近のものから一定の量だけ保持している。
【００７３】
以上の手順で、各コンピュータ１００-iは、スプリットブレインを起こさないよう、遅延された実行が追い付く仕組みを実現する。
【００７４】
次に、各コンピュータ１００-iの構成決定部２１０によって実行される、分散システム１０００の構成を決定するための動作手順（構成決定処理）について、図１５のフローチャートを参照して説明する。本実施形態において、構成決定部２１０による構成決定処理は一定時間毎に（つまり定期的に）実行されるものとするが、ランダムなタイミングで実行されても構わない。
【００７５】
まず構成決定部２１０は、構成記憶部２１１に格納されている情報に基づき、現在分散システム１０００を構成しているコンピュータの数ｎが４を超えているかを判定する（図１５のステップＧ１）。もし、ｎが４を超えている（つまり５以上である）ならば（図１５のステップＧ１のＹＥＳ）、構成決定部２１０は、現在分散システム１０００を構成しているｎ台のコンピュータ（ここではコンピュータ１００-1〜１００-7）のうち、コンピュータ１００-i（構成記憶部２１１を含むコンピュータ１００-i）を除くすべてのコンピュータ（他コンピュータ）１００-j（ここではｊは１〜７、但しｉを除く）について、障害検出部２１０ａを用いて以下の処理を実行する（図１５のステップＧ２）。
【００７６】
まず障害検出部２１０ａは、入力順序番号記憶部２１に格納されている該当入力順序番号と、他コンピュータ最大確定入力順序番号記憶部２１３に格納されている、現在対象となっているコンピュータ１００-j（対象のコンピュータ１００-j）の最大確定入力順序番号との差を求め、この差が、最大順序番号遅延許容値記憶部２１２に格納されている最大順序番号遅延許容値Ｌよりも大きくなっているかを判定する（図１５のステップＧ３）。ここで上記差は、コンピュータ１００-iの該当入力順序番号を基準とする対象のコンピュータ１００-jにおける入力パケット列に対する処理の遅延量を示す。
【００７７】
障害検出部２１０ａは、上記差が最大順序番号遅延許容値Ｌよりも大きいならば（図１５のステップＧ３のＹＥＳ）、対象のコンピュータ１００-jは異常であると判定する。つまり障害検出部２１０ａは、上記差が最大順序番号遅延許容値Ｌよりも大きくなったことをもって、対象のコンピュータ１００-jの異常（障害）を検出する。この場合、構成決定部２１０は、分散システム１０００の構成を変更する必要があるものと、さらに具体的に述べるならば、対象のコンピュータ１００-j（異常が検出されたコンピュータ１００-j）を分散システム１０００（を構成しているコンピュータの集合）から外す（切り離す）必要があるものと判定する。
【００７８】
そこで構成決定部２１０は、対象のコンピュータ１００-j（異常が検出されたコンピュータ１００-j）を分散システム１０００（を構成しているコンピュータの集合）から外す（切り離す）合意をとる（合意を形成する）ための処理、つまり分散システム１０００の構成を変更すべきことの合意をとるための処理を、整列マルチキャスト部２（内の入力パケット確定判定部２６に含まれている合意部２６２）を用いて行う（図１５のステップＧ４）。換言するならば、構成決定部２１０は、対象のコンピュータ１００-jを分散システム１０００から外す合意を、アプリケーションプログラム３に配送されるべき入力パケットに対する整列マルチキャストと同様にしてとるために、整列マルチキャスト部２を用いる。対象のコンピュータ１００-jを分散システム１０００から外すかは、整列マルチキャストと同様に、（ｎ−ｆ）台以上のコンピュータでの合意をもって決定される。
【００７９】
本実施形態において、対象のコンピュータ１００-jを分散システム１０００から外すとは、後述するように、当該コンピュータ１００-jを示す情報（ＩＤ）を構成記憶部２１１から削除することである。つまり対象のコンピュータ１００-jを分散システム１０００から外すとは、当該コンピュータ１００-jを、分散システム１０００を構成するコンピュータの集合から論理的に外すことであり、当該コンピュータ１００-jを物理的に分散システム１０００から取り外すものではない。
【００８０】
ステップＧ４において構成決定部２１０は、対象のコンピュータ１００-jを分散システム１０００から外すことを要求する特定のパケットを入力受付キュー部１に送る。この特定のパケットには、処理種別が「構成」であることを示す処理種別情報が付されている。構成決定部２１０から入力受付キュー部１に送られた特定のパケットは、当該入力受付キュー部１で受け付けられて、当該入力受付キュー部１にキューイングされる。
【００８１】
入力受付キュー部１にキューイングされた特定のパケット（以下、特定入力パケットと称する）は、図９および図１０のフローチャートを参照しての整列マルチキャスト部２（内の合意部２６２）の動作から明らかなように、対象のコンピュータ１００-jを含むｎ台（ｎ＝７）のコンピュータ（コンピュータ１００-1〜１００-7）の整列マルチキャスト部２による整列マルチキャストの対象となる。
【００８２】
もし、ｎ台（ｎ＝７）のコンピュータ（コンピュータ１００-1〜１００-7）のうちの（ｎ−ｆ）台以上のコンピュータで特定入力パケットの合意がとられたならば（図９のステップＡ２，Ａ３）、当該（ｎ−ｆ）台以上のコンピュータの整列マルチキャスト部２では、上記特定入力パケットが、合意部２６２から構成決定部２１０に渡されるとともに、入力パケットジャーナル記憶部２２に格納される（図９のステップＡ１０）。
【００８３】
構成決定部２１０は、合意部２６２から上記特定入力パケットが渡されたことをもって、対象のコンピュータ１００-jを分散システム１０００から外す合意が（ｎ−ｆ）台以上のコンピュータでとられたと判定する（図１５のステップＧ５のＹＥＳ）。この場合、構成決定部２１０は、構成記憶部２１１から対象のコンピュータ１００-jを示す情報（ＩＤ）を削除することにより、当該対象のコンピュータを分散システム１０００から外す（図１５のステップＧ６）。
【００８４】
構成決定部２１０（コンピュータ１００-iの構成決定部２１０）は、上記ステップＧ３からの処理を、現在分散システム１０００を構成しているｎ台のコンピュータのうち、コンピュータ１００-iを除く（ｎ−１）台のコンピュータ（他コンピュータ）について繰り返す（図１５のステップＧ２）。
【００８５】
本実施形態によれば、上述のような構成決定部２１０の処理により、ｎおよびｆをスケールダウンすることができる。以下、このｎおよびｆのスケールダウンについて説明する。
【００８６】
まず、分散システム１０００が当該分散システム１０００の運用開始時に７台のコンピュータ１００-1〜１００-7（ｎ＝７，ｆ＝２）から構成される本実施形態では、あるコンピュータ（以下、第１のコンピュータと称する）の障害が検出されて、当該第１のコンピュータを分散システム１０００から外す合意が（ｎ−ｆ）台のコンピュータ（ここでは、５台のコンピュータ）でとられたものとする。この場合、分散システム１０００の構成は６台（ｎ＝６，ｆ＝１）のコンピュータから構成されるように変更される。
【００８７】
次に、６台（ｎ＝６，ｆ＝１）のコンピュータから構成される分散システム１０００において、あるコンピュータ（以下、第２のコンピュータと称する）の障害が検出されて、当該第２のコンピュータを分散システム１０００から外す合意が（ｎ−ｆ）台のコンピュータ（ここでは、５台のコンピュータ）でとられたものとする。この場合、分散システム１０００の構成は５台（ｎ＝５，ｆ＝１）のコンピュータから構成されるように変更される。
【００８８】
次に、５台（ｎ＝５，ｆ＝１）のコンピュータから構成される分散システム１０００において、あるコンピュータ（以下、第３のコンピュータと称する）の障害が検出されて、当該第３のコンピュータを分散システム１０００から外す合意が（ｎ−ｆ）台のコンピュータ（ここでは、４台のコンピュータ）でとられたものとする。この場合、分散システム１０００の構成は４台（ｎ＝４，ｆ＝１）のコンピュータから構成されるように変更される。
【００８９】
このように本実施形態によれば、分散システム１０００に含まれる多重化を構成するコンピュータの数を７台（ｎ＝７）から４台（ｎ＝４）に下げること、つまり、ｎ，ｆを７，２から４，１にスケールダウンすることができる。この状態では、ｆ＝１が実現されているため、４台（ｎ＝４）のコンピュータのうち、正常に動作するコンピュータが３台以上あれば、多重化を継続できる。つまり、障害が発生したコンピュータの数が運用開始時のｆ（ここでは２）で表される（ｆ＋１）以上（ここでは３）となっても、少なくとも３台のコンピュータが正常に動作するならば、多重化を継続でき、スプリットブレインを原理的に発生させず、タイムアウトによる故障発生時の処理の中断も発生させることがない。
【００９０】
ここで、分散システム１０００から外されるコンピュータ１００-jの異常（最大順序番号遅延許容値Ｌを超える遅延）の要因が、当該コンピュータ１００-jの一時的な高負荷のためのスローダウンにあるものとする。この場合、コンピュータ１００-jはスローダウンから回復して、構成記憶部２１１の情報に基づいてｎ台のコンピュータの１つとして動作する可能性がある。
【００９１】
しかし、コンピュータ１００-jの構成記憶部２１１の内容は、現在分散システム１０００を構成しているコンピュータの構成記憶部２１１の内容ではなく、当該コンピュータ１００-jが分散システム１０００から外された（切り離された）際の構成記憶部２１１の内容である。ここで、コンピュータ１００-jが分散システム１０００から切り離された際のｎ，ｆをｎold，ｆoldで表し、現在のｎ，ｆをｎnew，ｆnewで表すならば、コンピュータ１００-jは、（ｎnew−ｆnew）台のコンピュータではなくて、（ｎold−ｆold）台のコンピュータで合意をとる必要がある。しかし、ｎold台のコンピュータのうちのｎnew台のコンピュータは、現在の分散システム１０００を構成している。したがってコンピュータ１００-jは、当該コンピュータ１００-jを含む（ｎold−ｆold）台のコンピュータで合意をとることはできず、現在の分散システム１０００を構成しているｎnew台のコンピュータの動作に悪影響を及ぼすことはない。
【００９２】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。例えば上記実施形態では、コンピュータ１００-jの異常（障害）の検出に、該当入力順序番号と当該コンピュータ１００-jの最大確定入力順序番号との差が用いられている。しかし、コンピュータ１００-jの異常の検出に他の手法を用いることも可能である。例えば上記特許文献１に従来技術として記載されているような、ハートビート・タイムアウト・アルゴリズム、つまり各コンピュータが定期的に送出するハートビートが一定時間以上確認できない場合に、当該コンピュータの異常（障害）を判定するという手法を用いることも可能である。この手法では、上記特許文献１に従来技術の問題点として指摘されているように、障害の誤検出が発生してスプリットブレインに陥るおそれがある。しかし、ハートビート・タイムアウト・アルゴリズムによって例えばコンピュータ１００-jの障害を検出した場合に、同様の障害検出を行っているコンピュータがｎ−ｆ台以上存在することを確認することにより、つまりコンピュータ１００-jの障害の検出の合意をｎ−ｆ台以上のコンピュータでとることにより、スプリットブレインの発生を原理的に防止できる。
【００９３】
また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。
【図面の簡単な説明】
【００９４】
【図１】本発明の一実施形態に係る分散システムの構成を示すブロック図。
【図２】同実施形態の分散システムを構成するコンピュータの機能構成を示すブロック図。
【図３】同実施形態の入力受付キュー部にキューイングされるデータ（入力パケット）のデータ構造例を示す図。
【図４】同実施形態における最大確定入力順序番号記憶部のデータ構造例を示す図。
【図５】同実施形態における構成記憶部のデータ構造例を示す図。
【図６】同実施形態における最大順序番号遅延許容値記憶部のデータ構造例を示す図。
【図７】同実施形態における他コンピュータ最大確定入力順序番号記憶部のデータ構造例を示す図。
【図８】同実施形態の分散システムを構成するコンピュータ間で送受信されるプロトコルデータのレイアウトを示す図。
【図９】同実施形態において各コンピュータが実行する整列マルチキャストの１回の配送を行う基本的な部分の動作手順を示す第１のフローチャート。
【図１０】同実施形態において各コンピュータが実行する整列マルチキャストの１回の配送を行う基本的な部分の動作手順を示す第２のフローチャート。
【図１１】同実施形態において各コンピュータが実行する、多重化実行の遅延を解消するための動作手順を示す第１のフローチャート。
【図１２】同実施形態において各コンピュータが実行する、多重化実行の遅延を解消するための動作手順を示す第２のフローチャート。
【図１３】同実施形態において各コンピュータが実行する、多重化実行の遅延を解消するための動作手順を示す第３のフローチャート。
【図１４】同実施形態において各コンピュータが実行する、多重化実行の遅延を解消するための動作手順を示す第４のフローチャート。
【図１５】同実施形態において各コンピュータが実行する、分散システムの構成を決定するための動作手順を示すフローチャート。
【符号の説明】
【００９５】
１…入力受付キュー部、２…整列マルチキャスト部、３…アプリケーションプログラム、４…プログラム状態管理部、５…出力フィルタ部、２１…入力順序番号記憶部、２２…入力パケットジャーナル記憶部、２３…プロトコルデータ送受信部、２４…ステップ番号記憶部、２５…候補パケット記憶部、２６…入力パケット確定判定部、２７…最大確定入力順序番号記憶部、２８…遅延記憶部、２９…スキップ判定部、１００-1〜１００-7，１００-i…コンピュータ、２１０…構成決定部、２１０ａ…障害検出部、２１１…構成記憶部、２１２…最大順序番号遅延許容値記憶部、２１３…他コンピュータ最大確定入力順序番号記憶部、２６１…入力候補収集部、２６２…合意部、１０００…分散システム、２０００…クライアント装置、Ａ…ネットワーク、Ｂ…ネットワーク。
【図１】
2010152559.tif 000003
【図２】
2010152559.tif 000004
【図３】
2010152559.tif 000005
【図４】
2010152559.tif 000006
【図５】
2010152559.tif 000007
【図６】
2010152559.tif 000008
【図７】
2010152559.tif 000009
【図８】
2010152559.tif 000010
【図９】
2010152559.tif 000011
【図１０】
2010152559.tif 000012
【図１１】
2010152559.tif 000013
【図１２】
2010152559.tif 000014
【図１３】
2010152559.tif 000015
【図１４】
2010152559.tif 000016
【図１５】
2010152559.tif 000017