(57)【要約】  情報処理システムは、第１決定部と第２決定部と処理部とを備える。第１決定部は、同じデータに対してｔ２以上の第１推薦状態または第１確定状態の選択結果が選択されたことを示す第１条件を満たす場合、当該データに対して第２確定状態の選択結果を決定する。第２決定部は、同じデータに対してｔ１以上の第２確定状態の選択結果が選択されたことを示す第２条件を満たす場合、当該データに対して第１確定状態の選択結果を決定し、同じデータに対して（ｂ＋１）以上の第２確定状態の選択結果が選択されたことを示す第３条件を満たす場合、当該データに対して第１推薦状態の選択結果を決定する。処理部は、第１確定状態に決定されたデータに対して処理を実行して出力結果を出力する。
2015140942.tif 000002
【特許請求の範囲】
【請求項１】
ｎ以上（ｎはｎ＞２ｆ＋３ｂを満たす整数、ｆは０以上の整数、ｂは１以上の整数）のサーバ装置を備える情報処理システムであって、
データに対して選択された、第１確定状態、第１推薦状態、および、第２確定状態のいずれかである選択結果を受信する受信部と、
同じデータに対してｔ２（ｔ２は（ｎ＋ｂ）の過半数≦ｔ２≦ｎ−ｆ−ｂを満たす整数）以上の前記第１推薦状態または前記第１確定状態の前記選択結果が選択されたことを示す第１条件を満たす場合、当該データに対して第２確定状態の選択結果を決定する第１決定処理、を実行する第１決定部と、
同じデータに対してｔ１（ｔ１は、ｆ＋２ｂ＋１≦ｔ１≦ｎ−ｆ−ｂを満たす整数）以上の前記第２確定状態の前記選択結果が選択されたことを示す第２条件を満たす場合、当該データに対して第１確定状態の選択結果を決定し、前記第２条件を満たさず、かつ同じデータに対して（ｂ＋１）以上の第２確定状態の前記選択結果が選択されたことを示す第３条件を満たす場合、当該データに対して第１推薦状態の選択結果を決定する第２決定処理、を実行する第２決定部と、
前記第１確定状態に決定されたデータに対して処理を実行して出力結果を出力する処理部と、
ｔ３（ｔ３は、ｂ＋１≦ｔ３≦ｎ−ｆ−ｂを満たす整数）以上の同じ出力結果を受信した場合に、受信した出力結果が有効であると判定する判定部と、
を備える情報処理システム。
【請求項２】
前記受信部は、さらに、データに対して選択された第２推薦状態である選択結果を受信し、
前記第１決定処理は、さらに、前記第１条件を満たさず、かつ（ｎ−ｆ）以上から前記第１推薦状態または前記第１確定状態の選択結果が受信されたことを示す第４条件を満たす場合、前記選択結果が受信されたデータから選択された１のデータに対して第２推薦状態の選択結果を決定する処理を含み、
前記第２決定処理は、さらに、前記第２条件および前記第３条件を満たさず、かつ（ｎ−ｆ）以上から前記第２推薦状態または前記第２確定状態の選択結果が受信されたことを示す第５条件を満たす場合、前記選択結果が受信されたデータから選択された１のデータに対して第１推薦状態の選択結果を決定する処理を含む、
請求項１に記載の情報処理システム。
【請求項３】
前記第１決定処理は、前記第１条件を満たさずかつ前記第４条件を満たす場合、ランダムに選択された１のデータ、または、所定の規則に従い選択された１のデータに対して第２推薦状態の選択結果を決定する処理を含む、
請求項２に記載の情報処理システム。
【請求項４】
前記第２決定処理は、前記第５条件を満たす場合に限り、第１推薦状態の選択結果を決定する処理を含む、
請求項２に記載の情報処理システム。
【請求項５】
前記第２決定処理は、前記第２条件および前記第３条件を満たさずかつ前記第５条件を満たす場合、ランダムに選択された１のデータ、または、所定の規則に従い選択された１のデータに対して第１推薦状態の選択結果を決定する処理を含む、
請求項２に記載の情報処理システム。
【請求項６】
前記第１決定処理、および、前記第１決定処理後に実行される前記第２決定処理が、前記第１確定状態の選択結果が決定されるまで繰り返される、
請求項１に記載の情報処理システム。
【請求項７】
前記受信部は、受信した選択結果が正当であるか否かを署名に基づいて検証し、
前記第１決定部は、正当であると検証された選択結果を用いて前記第１決定処理を実行し、
前記第２決定部は、正当であると検証された選択結果を用いて前記第２決定処理を実行する、
請求項１に記載の情報処理システム。
【請求項８】
前記受信部は、さらに、前記選択結果に対応するデータを受信し、受信したデータが正当であるか否かを署名に基づいて検証し、
前記第１決定部は、さらに、正当であると検証されたデータに対応する選択結果を用いて前記第１決定処理を実行し、
前記第２決定部は、さらに、正当であると検証されたデータに対応する選択結果を用いて前記第２決定処理を実行する、
請求項７に記載の情報処理システム。
【請求項９】
前記第２決定部は、さらに、同じデータに対してｔ３以上の同じ状態の前記第１推薦状態または前記第１確定状態の選択結果が他のサーバ装置から受信された場合、当該データに対して前記同じ状態の選択結果を決定する処理を実行する、
請求項１に記載の情報処理システム。
【請求項１０】
前記受信部は、さらに、データに対して選択された第２推薦状態である選択結果を受信し、
前記第１決定部は、さらに、同じデータに対してｔ３以上の同じ状態の前記第２推薦状態または前記第２確定状態の選択結果が他のサーバ装置から受信された場合、当該データに対して前記同じ状態の選択結果を決定する処理を実行する、
請求項１に記載の情報処理システム。
【請求項１１】
前記受信部は、さらに、データに対して選択された第２推薦状態である選択結果を受信し、
前記第１決定部は、さらに、ｔ３以上の第２推薦状態の選択結果が他のサーバ装置から受信された場合、任意に選択したデータに対して第２推薦状態の選択結果を決定する処理を実行する、
請求項１に記載の情報処理システム。
【請求項１２】
前記第２決定部は、さらに、ｔ４（ｔ４は、２ｂ＋１≦ｔ４≦ｎ−ｆ−ｂを満たす整数）以上の第１推薦状態の選択結果が他のサーバ装置から受信され、かつ、同じデータに対してｔ３以上の第１推薦状態の選択結果が他のサーバ装置から受信されていない場合、任意に選択したデータに対して第１推薦状態の選択結果を決定する処理を実行する、
請求項１に記載の情報処理システム。
【請求項１３】
ｎ以上（ｎはｎ＞２ｆ＋３ｂを満たす整数、ｆは０以上の整数、ｂは１以上の整数）のサーバ装置を備える情報処理システムの前記サーバ装置であって、
データに対して選択された、第１確定状態、第１推薦状態、および、第２確定状態のいずれかである選択結果を受信する受信部と、
同じデータに対してｔ２（ｔ２は（ｎ＋ｂ）の過半数≦ｔ２≦ｎ−ｆ−ｂを満たす整数）以上の前記第１推薦状態または前記第１確定状態の前記選択結果が選択されたことを示す第１条件を満たす場合、当該データに対して第２確定状態の選択結果を決定する第１決定処理、を実行する第１決定部と、
同じデータに対してｔ１（ｔ１は、ｆ＋２ｂ＋１≦ｔ１≦ｎ−ｆ−ｂを満たす整数）以上の前記第２確定状態の前記選択結果が選択されたことを示す第２条件を満たす場合、当該データに対して第１確定状態の選択結果を決定し、前記第２条件を満たさず、かつ同じデータに対して（ｂ＋１）以上の第２確定状態の前記選択結果が選択されたことを示す第３条件を満たす場合、当該データに対して第１推薦状態の選択結果を決定する第２決定処理、を実行する第２決定部と、
前記第１確定状態に決定されたデータに対して処理を実行して出力結果を出力する処理部と、
を備えるサーバ装置。
【請求項１４】
ｎ以上（ｎはｎ＞２ｆ＋３ｂを満たす整数、ｆは０以上の整数、ｂは１以上の整数）のサーバ装置を備える情報処理システムで実行される情報処理方法であって、
データに対して選択された、第１確定状態、第１推薦状態、および、第２確定状態のいずれかである選択結果を受信する受信ステップと、
同じデータに対してｔ２（ｔ２は（ｎ＋ｂ）の過半数≦ｔ２≦ｎ−ｆ−ｂを満たす整数）以上の前記第１推薦状態または前記第１確定状態の前記選択結果が選択されたことを示す第１条件を満たす場合、当該データに対して第２確定状態の選択結果を決定する第１決定処理、を実行する第１決定ステップと、
同じデータに対してｔ１（ｔ１は、ｆ＋２ｂ＋１≦ｔ１≦ｎ−ｆ−ｂを満たす整数）以上の前記第２確定状態の前記選択結果が選択されたことを示す第２条件を満たす場合、当該データに対して第１確定状態の選択結果を決定し、前記第２条件を満たさず、かつ同じデータに対して（ｂ＋１）以上の第２確定状態の前記選択結果が選択されたことを示す第３条件を満たす場合、当該データに対して第１推薦状態の選択結果を決定する第２決定処理、を実行する第２決定ステップと、
前記第１確定状態に決定されたデータに対して処理を実行して出力結果を出力する処理ステップと、
ｔ３（ｔ３は、ｂ＋１≦ｔ３≦ｎ−ｆ−ｂを満たす整数）以上の同じ出力結果を受信した場合に、受信した出力結果が有効であると判定する判定ステップと、
を含む情報処理方法。
【請求項１５】
ｎ以上（ｎはｎ＞２ｆ＋３ｂを満たす整数、ｆは０以上の整数、ｂは１以上の整数）のサーバ装置を備える情報処理システムの前記サーバ装置が備えるコンピュータを、
データに対して選択された、第１確定状態、第１推薦状態、および、第２確定状態のいずれかである選択結果を受信する受信部と、
同じデータに対してｔ２（ｔ２は（ｎ＋ｂ）の過半数≦ｔ２≦ｎ−ｆ−ｂを満たす整数）以上の前記第１推薦状態または前記第１確定状態の前記選択結果が選択されたことを示す第１条件を満たす場合、当該データに対して第２確定状態の選択結果を決定する第１決定処理、を実行する第１決定部と、
同じデータに対してｔ１（ｔ１は、ｆ＋２ｂ＋１≦ｔ１≦ｎ−ｆ−ｂを満たす整数）以上の前記第２確定状態の前記選択結果が選択されたことを示す第２条件を満たす場合、当該データに対して第１確定状態の選択結果を決定し、前記第２条件を満たさず、かつ同じデータに対して（ｂ＋１）以上の第２確定状態の前記選択結果が選択されたことを示す第３条件を満たす場合、当該データに対して第１推薦状態の選択結果を決定する第２決定処理、を実行する第２決定部と、
前記第１確定状態に決定されたデータに対して処理を実行して出力結果を出力する処理部、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理システム、サーバ装置、情報処理方法およびプログラムに関する。
【背景技術】
【０００２】
複数のノードに同じ処理を多重化して実行する多重化システムは、可用性や信頼性を向上させる手法として実用化されている。多重化システムでは、一部のノードが停止障害となっても、他のノードが処理を継続できるため可用性が向上する。また、各ノードが出力する処理の結果を比較して、間違った結果を除外することにより信頼性が向上する。【０００３】
多重化システムの一例として、並べて設置した同一機種の専用コンピュータを多重化するシステムが存在する。この場合、コンピュータ間の通信は安定しており、コンピュータの実行速度も互いにほぼ等しい。そのため、一方のコンピュータに一定時間以上の遅延が発生した場合は、それを停止障害として扱うことが妥当である。このような環境は、同期ネットワークモデルとして分類される。【０００４】
同期ネットワークモデルでは、比較的短い時間のタイムアウトを用いて停止障害を検出できる。これを利用した二重化システムは広く一般に利用されている。いわゆるＨＡ（ハイアベイラビリティ）システムやＦＴ（フォールトトレラント）サーバが該当する。また出力結果の多数決を用いた三重化システムも実用化されている。【０００５】
一方、インターネットの発達により、インターネットを介して複数のコンピュータが連動するシステムが実用化されている。また、仮想マシンを利用したサーバも普及している。いわゆるクラウドシステムがこの典型的な例として挙げられる。一般に、ネットワーク上に高度に分散して仮想化された環境では、一過性のネットワーク遅延やコンピュータの実行の渋滞はしばしば起こることであり、これを停止障害として扱うことは妥当ではない。このような環境は、非同期ネットワークモデルとして分類される。【０００６】
非同期ネットワークモデルでは、一時的にノードが動作していないだけであれば停止障害であるとはみなさない。従って、比較的短い時間のタイムアウトでは停止障害を判定できない。停止障害の検出を行わずに多重化の一貫性を維持するためには、同期ネットワークモデルに比べてより多くの稼働ノードを必要とする。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特許第３６５５２６３号公報
【特許文献２】特許第２５３４４３０号公報
【０００８】
【非特許文献１】ＺｏｏＫｅｅｐｅｒ：  Ａ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃｏｏｒｄｉｎａｔｉｏｎ  Ｓｅｒｖｉｃｅ  ｆｏｒ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ＜ＵＲＬ：ｈｔｔｐ：／／ｚｏｏｋｅｅｐｅｒ．ａｐａｃｈｅ．ｏｒｇ／ｄｏｃ／ｃｕｒｒｅｎｔ／ｚｏｏｋｅｅｐｅｒＯｖｅｒ．ｈｔｍｌ＞
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非同期ネットワークモデルで出力結果の多数決を用いたシステムの場合、多数決に必要な出力結果が非同期に得られる。このため、特に稼働ノード数が多い場合などでは、必要な情報（出力結果）を得るまで処理が遅延する状況を回避することが望ましい。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、本発明の情報処理システムは、第１決定部と第２決定部と処理部とを備える。第１決定部は、同じデータに対してｔ２以上の第１推薦状態または第１確定状態の選択結果が選択されたことを示す第１条件を満たす場合、当該データに対して第２確定状態の選択結果を決定する。第２決定部は、同じデータに対してｔ１以上の第２確定状態の選択結果が選択されたことを示す第２条件を満たす場合、当該データに対して第１確定状態の選択結果を決定し、同じデータに対して（ｂ＋１）以上の第２確定状態の選択結果が選択されたことを示す第３条件を満たす場合、当該データに対して第１推薦状態の選択結果を決定する。処理部は、第１確定状態に決定されたデータに対して処理を実行して出力結果を出力する。
【図面の簡単な説明】
【００１１】
【図１】図１は、第１の実施形態にかかる情報処理システムの構成の一例を示すブロック図である。
【図２】図２は、第１の実施形態のクライアント装置およびサーバ装置の構成の一例を示すブロック図である。
【図３】図３は、投票記憶部に記憶されるデータのデータ構造の一例を示す図である。
【図４】図４は、整列マルチキャストの動作例を説明するための図である。
【図５】図５は、第１の実施形態における整列マルチキャストの全体の流れを示すフローチャートである。
【図６】図６は、第２の実施形態にかかる情報処理システムに含まれるサーバ装置の構成の一例を示すブロック図である。
【図７】図７は、実施形態の装置のハードウェアの構成の一例を示す図である。
【発明を実施するための形態】
【００１２】
以下に、本発明にかかる情報処理システム、サーバ装置、情報処理方法およびプログラムの実施形態を図面に基づいて詳細に説明する。なお、この実施形態によりこの発明が限定されるものではない。
【００１３】
（用語の定義）
最初に、下記実施形態で用いる用語の定義を記載する。
【００１４】
分散システム（情報処理システム）を構成する独立したコンピュータを「ノード」と呼ぶ。各ノードは独立しており、ノード間はネットワークを介して通信を行うことができる。ノードが全く動作しない状態になることを、「停止障害」と呼ぶ。ノードが誤動作する状態になることを「ビザンティン障害」と呼ぶ。停止障害とビザンティン障害とを合わせて「ノード障害」と呼ぶ。ノード障害となっていないノードのこと「稼働ノード」と呼ぶ。ビザンティン障害となっていないノードのことを「正常ノード」と呼ぶ。特に、稼働ノードは必ず正常ノードである。定義上、停止障害にはビザンティン障害は含まないものとする。ビザンティン障害の誤動作の内容は任意であり、不正侵入を原因とする場合も含む。
【００１５】
ところで、多重化システムを可用性の視点で見たとき、システムの稼働率が１つの指標となる。例えば典型的なＨＡシステムの場合、主系に停止障害が発生した後、従系がタイムアウトによって停止障害を検出してサービスを再開するまでの間、サービスは稼働しておらず稼働率がそのぶん低下する。一般に、タイムアウトを用いて停止障害を検出する方法では、稼働率を上げるためにはタイムアウトをできるだけ短い時間に設定する。しかし、タイムアウトの時間が短すぎると停止障害の誤検出が発生し、却って信頼性や可用性が低下する可能性があるというジレンマがある。この課題に対する根本的な解決策の１つとして、障害発生時にもリアルタイム性が確保できるノンブロッキング多重化が知られている。ノンブロッキング多重化は障害検出を必要とせず、障害の発生時に処理の中断が発生しない方式であるため、タイムアウトによる稼働率の低下がない。
【００１６】
多重化システムを信頼性の視点で見たとき、ビザンティン障害に耐性を持つ多重化システムはより信頼性が高い。しかし、ビザンティン障害に耐性を持って多重化の一貫性を維持するためにはより多くの稼働ノードを必要とする。例えば、同期ネットワークモデルを前提とした多重化技術で、全ノード数をｎ、許容できる最大ノード障害数をｆ、許容できる最大ビザンティン障害数をｂとするとき、ｎ＞ｆ＋２ｂが条件となる技術が存在する。
【００１７】
（第１の実施形態）
上記のように、特に稼働ノード数が多い場合などでは、必要な情報（出力結果）を得るまで処理が遅延する状況を回避することが望ましい。そこで、本実施形態の情報処理システムは、少なくともビザンティン障害に対して耐性を有し、かつ、非同期ネットワークモデルを前提とした一貫性を有し、処理の遅延を抑制することができる多重化制御処理を実現する。なお、本実施形態では、さらに障害発生時におけるリアルタイム性を確保したノンブロッキング多重化を実現することもできる。
【００１８】
本実施形態の多重化システムでは、多重化システムを構成する各ノードはすべて同じ初期状態から始まる。各ノードに入力されるデータは、整列マルチキャストを通して各ノードに配送される。その入力データに基づいて各ノードで決定性のあるプログラムが実行される。そして、その結果としてデータが出力される。
【００１９】
この方式では、各ノードの初期状態は同一であり、各ノードへの入力列は整列マルチキャストにより同一順序となり、決定性のあるプログラムの性質により、各ノードの状態は同一に保たれ、出力列も同一となる。結果として、プログラムの実行が多重化される。
【００２０】
本実施形態の情報処理システムによれば、非同期ネットワークモデルを前提として、ビザンティン障害となったコンピュータ数がｂ（最大ビザンティン障害数）以下ならば、多重化システムから得られる有効な出力データは正当である。さらに、ノード障害の数がｆ（許容できる最大ノード障害数）以下ならば、多重化システムは処理を継続できる。
【００２１】
また、本実施形態の情報処理システムでは、信頼性の閾値に相当するｆと可用性の閾値に相当するｂとを分けて設定できる。ｆをｂより大きく設定した場合、ビザンティン障害の数がｂまで発生したときでも、それに加えてさらにｆ−ｂの停止障害を許容できる。この設定は可用性が比較的重要であるシステムに向いている。逆に、ｂをｆより大きく設定した場合、ノード障害の数がｆを超えたとしても、ビザンティン障害の数がｂを越えなければ、誤動作はしない。この設定は、誤動作するぐらいなら停止してしまったほうがよい（いわゆるフェールストップ）システムに向いている。
【００２２】
非同期ネットワークモデルを前提としているので、いわゆるサーバコンピュータだけではなく、クラウドシステム内の仮想サーバや、携帯電話等のモバイル端末などをノードとしても、問題なく多重化システムが構成できる。障害検出を必要とせず、障害の発生時に処理の中断が発生しない方式のため、タイムアウトによる稼働率の低下がなく、リアルタイム性が必要なシステムにも適用可能である。
【００２３】
本実施形態にかかる情報処理システムは、複数の選挙を繰り返すことにより入力データおよび順序を決定する整列マルチキャストを実現する。選挙とは、あるラウンドの入力データから次のラウンドの入力データを決定する処理を表す。選挙は、予備選と、予備選で投票されたデータを用いて実行される信任選とを含む。「投票する」とは、各選挙で、データ、および、当該データに対する状態を選択することを表す。以下では、投票された結果のデータを「投票」という場合がある。
【００２４】
本実施形態では、整列マルチキャストによって順序が確定する入力データの列に対して、１から順に順序番号が付与される。各ラウンドには、１から順にラウンド番号が付与される。ここで、入力データが確定した時には、ラウンド番号は１にリセットされる。すなわち、各ラウンドは（順序番号、ラウンド番号）の組によって一意に特定される。
【００２５】
投票により決定される情報は、（順序番号、ラウンド番号、ノード番号、選択結果（選択された状態）、入力データ）の組である。ノード番号は、投票を行ったノードを識別する番号である。ノードを識別できれば数値（番号）以外の情報（ノード識別情報）を用いてもよい。選択結果は、推薦状態（第１推薦状態）、当選状態（第１確定状態）、補欠状態（第２推薦状態）、および、当確状態（第２確定状態）の４種類のいずれかである。なお、以下では補欠状態、当確状態、推薦状態および当選状態が選択された投票を、それぞれ補欠投票、当確投票、推薦投票および当選投票という場合がある。
【００２６】
補欠状態は、予備選により、確定する候補ではないが推薦するデータとして選択された状態を示す。当確状態は、予備選により、確定する候補のデータとして選択された状態を示す。推薦状態は、信任選により、確定ではないが推薦するデータとして選択された状態を示す。当選状態は、信任選により、確定するデータとして選択された状態を示す。
【００２７】
予備選と信任選は交互に繰り返される。予備選に用いるデータのラウンド番号は奇数であり、信任選に用いるデータのラウンド番号は偶数である。
【００２８】
図１は、第１の実施形態にかかる情報処理システム１００の構成の一例を示すブロック図である。図１に示すように、情報処理システム１００は、サーバ装置１０−１、・・・、サーバ装置１０−ｎ（ｎは４以上の整数）と、クライアント装置２０−１、・・・、クライアント装置２０−ｍ（ｍは１以上の整数）と、ネットワーク３０とを備える。以下、サーバ装置１０−１、・・・、およびサーバ装置１０−ｎを区別する必要がない場合は単にサーバ装置１０という。同様に、クライアント装置２０−１、・・・、およびクライアント装置２０−ｍを区別する必要がない場合は、単にクライアント装置２０という。サーバ装置１０が、分散システムを構成する上記ノードに相当する。
【００２９】
サーバ装置１０とクライアント装置２０は、互いに通信できるようにネットワーク３０を介して接続されている。また、サーバ装置１０は、他のサーバ装置１０と互いに通信できるようにネットワーク３０を介して接続されている。なお、各装置間の通信方式は、有線であっても無線であってもよく、また、両方を組み合わせてもよい。複数のサーバ装置１０間の通信は、クライアント装置２０とサーバ装置１０との間の通信よりも多くなるため、これらをより高速な別回線として分けてもよい。
【００３０】
図２は、第１の実施形態のクライアント装置２０およびサーバ装置１０の構成の一例を示すブロック図である。クライアント装置２０は、送受信部２１と、判定部２２と、を備える。
【００３１】
送受信部２１は、各サーバ装置１０へ入力データを送信し、また、出力データを含む出力パケットを各サーバ装置１０から受け取る。判定部２２は、各サーバ装置１０から送受信部２１が受信した出力パケットを記憶し、出力データの有効性を判定する。
【００３２】
サーバ装置１０は、未確定データ記憶部１１と、確定データ記憶部１２と、投票記憶部１３と、データ受信部１５と、データ送信部１６と、投票送受信部１７と、処理部１８と、制御部１９と、を備える。
【００３３】
データ受信部１５は、クライアント装置２０などの外部装置から送信されたデータを受信する。例えばデータ受信部１５は、クライアント装置２０から入力データを受信する。
【００３４】
未確定データ記憶部１１は、クライアント装置２０からデータ受信部１５が受信した入力データを記憶する。確定データ記憶部１２は、制御部１９により順序が確定された入力データを、決定された順序を示す順序番号と組みにして記憶する。順序が確定された入力データが未確定データ記憶部１１に記憶されている場合には、記憶されている入力データは未確定データ記憶部１１から削除される。
【００３５】
投票送受信部１７は、他のサーバ装置１０との間で投票の結果（選択結果）を送受信する。例えば投票送受信部１７は、他のサーバ装置１０からの投票を受信する。
【００３６】
投票記憶部１３は、投票送受信部１７を介して収集した他のサーバ装置１０の投票、および、制御部１９が決定した自投票を記憶する。自投票とは、自装置内の制御部１９で決定した投票である。投票記憶部１３に記憶された自投票は、投票送受信部１７を介して他のサーバ装置１０に随時送られる。
【００３７】
処理部１８は、確定データ記憶部１２から順に順序番号と入力データを読み出し、その入力データを入力として、所定の処理を実行して出力結果（出力データ）を出力する。なお、所定の処理に用いる入力データの個数は任意である。例えば、順序番号に従い１または複数の入力データが所定の処理に用いられる。また、所定の処理で出力される出力データの個数も任意である。通常は、出力データに対しても、入力データの順序番号と異なる順序番号（出力順序番号）が付与される。
【００３８】
データ送信部１６は、クライアント装置２０などの外部装置に対してデータを送信する。例えばデータ送信部１６は、処理部１８により出力された出力データを出力パケットにまとめ、クライアント装置２０の送受信部２１に送信する。ここで、出力パケットは、例えば（出力順序番号、ノード番号、出力データ）の組の形式である。
【００３９】
クライアント装置２０の判定部２２は、次に確定すべき出力データの出力順序番号（現出力順序番号）を保持する。判定部２２は、例えばｂ＋１ノード以上から、現出力順序番号を有し、同一の出力データを有する出力パケットを受信した場合に、その出力データを有効なデータとして確定し、現出力順序番号を１進める。
【００４０】
サーバ装置１０の制御部１９は、各ラウンドのデータを用いる選挙を制御する。制御部１９は、次に確定すべき入力データの順序番号（現順序番号）と、現在選挙を行っているラウンドのラウンド番号（現ラウンド番号）を保持する。現順序番号と現ラウンド番号に対応するラウンドのことを現ラウンドと呼ぶ。制御部１９は、現ラウンド番号が１の時、未確定データ記憶部１１から入力データを読み出し、ラウンド１の推薦投票として自投票を決定し投票記憶部１３に格納する。
【００４１】
また、制御部１９は、投票記憶部１３に記憶された投票を読み出し、現ラウンドに関する予備選または信任選を行い、次のラウンドの自投票を決定して投票記憶部１３に格納し、現ラウンド番号を１進める。また、制御部１９は、信任選の結果が当選となった時、その入力データと現順序番号を確定データ記憶部１２に格納し、現順序番号を１進め、現ラウンド番号を１にする。
【００４２】
制御部１９は、第１決定部５１と、第２決定部５２と、を備えている。第１決定部５１は、予備選（第１決定処理）を実行する。第２決定部５２は、信任選（第２決定処理）を実行する。
【００４３】
予備選は、現ラウンドの投票に関して、同じデータに対して例えば（ｎ＋ｂ）の過半数（＝［（ｎ＋ｂ）／２］＋１）以上の推薦状態または当選状態の投票が受信された場合（第１条件）に、次のラウンドの投票として、当該データに対して当確状態を投票することを特徴とする選挙である。
【００４４】
信任選は、現ラウンドの投票に関して、同じデータに対して例えば（ｆ＋２ｂ＋１）以上の当確状態の投票が受信された場合（第２条件）に、当該データに対して当選状態を投票し、それ以外で同じデータに対して（ｂ＋１）以上の当確状態の投票が受信された場合（第３条件）に、当該データに対して推薦状態を投票することを特徴とする選挙である。
【００４５】
なお、ノンブロッキング多重化を実現する場合は、予備選および信任選を以下のようにしてもよい。例えば、予備選では、第１条件を満たさない場合に、（ｎ−ｆ）以上の投票が受信された時点（第４条件）で、任意（例えばランダム）に選択したデータに対して補欠状態を投票するものとしてもよい。また、信任選では、第２条件を満たさず、第３条件を満たす場合に、（ｎ−ｆ）以上の投票が受信された時点で、当該データに対して推薦状態を投票するものとしてもよい。また、信任選では、第２条件および第３条件を満たさない場合に、（ｎ−ｆ）以上の投票が受信された時点（第５条件）で、任意（例えばランダム）に選択したデータに対して推薦状態を投票するものとしてもよい。
【００４６】
各ラウンドに対する自投票は、一度決定したら覆してはならない。すなわち、既に自投票が決定していたならば、新たな投票は行わない（二重投票の禁止）。整理すると、各ノードの奇数ラウンドへの投票は、推薦投票か当選投票のいずれかの一票であり、各ノードの偶数ラウンドへの投票は、補欠投票か当確投票のいずれかの一票である。
【００４７】
図３は、投票記憶部１３に記憶されるデータのデータ構造の一例を示す図である。なお図３は、ノード数ｎ＝６の場合の例である。投票記憶部１３は、順序番号、ラウンド番号、ノード番号ごとに入力データと投票した状態を記憶する。
【００４８】
図３の例では、Ａ〜Ｇが入力データである。当選投票がある場合、当該順序番号中の後続のラウンドのそのノードからの投票については、疑似的に当該入力データの当確または当選を受信したものとみなす。図３の例では、ノード２とノード３からは、順序番号ｓのラウンド５で入力データＢの当選投票を受信している。このため、順序番号ｓのラウンド６は入力データＢの当確投票を受信したとみなされ、ラウンド７は入力データＢの当選投票を受信したとみなされる。
【００４９】
なお、未確定データ記憶部１１、確定データ記憶部１２、および、投票記憶部１３は、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）、光ディスク、メモリカード、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などの一般的に利用されているあらゆる記憶媒体により構成することができる。
【００５０】
ここで図４を参照して、整列マルチキャストの動作の具体例を説明する。図４は、整列マルチキャストの動作例を説明するための図である。この例では、ｎ＝６、ｆ＝１、ｂ＝１とする。この場合、［（ｎ＋ｂ）／２］＋１＝４、ｆ＋２ｂ＋１＝４、ｎ−ｆ＝５である。以下では、６個のサーバ装置１０をそれぞれノード１〜ノード６ともいう。ノード４がビザンティン障害となっているものとする。
【００５１】
図４中、Ａ〜Ｆは入力データを表す。下線なしのＡ〜Ｆは推薦投票または補欠投票であることを表す。下線付きのＡ〜Ｆは当選投票または当確投票であることを表す。なお、推薦投票であるか補欠投票であるかの区別、および、当選投票であるか当確投票であるかの区別は、ラウンド番号が奇数であるか偶数であるかに従って区別できる。図４中、かっこで括った集合は、選挙に用いる投票の集合である。記号「−」は、選挙に用いなかった投票を示す。なお投票を収集していき必要数が揃った段階で選挙が行われるため、すべての投票が選挙に用いられるわけではない。
【００５２】
以下に整列マルチキャストの流れを説明する。
【００５３】
当該順序番号の入力データを決定するとき、各ノードの未確定データ記憶部１１には入力データＡ〜Ｆが格納されているのとする。これらの入力データは、各ノードのラウンド１の投票の入力データとなる。ただし、ビザンティン障害となっているノード４は除く（以下同様）。
【００５４】
各ノードは、ラウンド１の投票データを収集する。予備選に必要な最大の投票数はｎ−ｆ＝５である。ノード１はノード２〜ノード５までの投票を収集した。ノード１は、自投票と合わせて、５票を収集したが、［（ｎ＋ｂ）／２］＋１＝４個の同じ入力データの投票が存在しない。このため、ノード１は、ランダムに入力データＤを選び、ラウンド２の補欠投票とした。同様に、いずれの正常ノードでも５票を収集して４個の同じ入力データの投票がない。このため各ノードは、ランダムに入力データを選び、ラウンド２の補欠投票とした。
【００５５】
各ノードは、ラウンド２の投票データを収集する。信任選に必要な最大の投票数はｎ−ｆ＝５である。ノード１はノード２〜ノード５までの投票を収集した。ノード１は、自投票と合わせて、５票を収集したが、ｂ＋１＝２個以上の同じ入力データの当確投票が存在しない。このため、ノード１は、ランダムに入力データＢを選び、ラウンド３の推薦投票とした。同様に、いずれの正常ノードでも５票を収集しても２個の同じ入力データの当確投票ない。このため各ノードは、ランダムに入力データを選び、ラウンド３の推薦投票とした。なおここで、ノード４はビザンティン障害となっているため、虚偽の当確投票を各ノードに送っている点に注意する。
【００５６】
各ノードは、ラウンド３の投票データを収集する。ノード１，３，６は［（ｎ＋ｂ）／２］＋１＝４個の同じ入力データＢの投票を得たので、入力データＢの当確投票をラウンド４の投票とした。ノード２（またはノード５）は５票を収集したが、４個の同じ入力データの投票がない。このためノード２（またはノード５）は、ランダムに入力データＡ（またはＤ）を選び、ラウンド４の補欠投票とした。
【００５７】
各ノードは、ラウンド４の投票データを収集する。ノード１，２，５，６は５票を収集した。ｆ＋２ｂ＋１＝４個の同じ入力データの当確投票がないが、ｂ＋１＝２個以上の同じ入力データＢの当確投票があるので、ノード１，２，５，６は、入力データＢをラウンド５の推薦投票とした。ノード３は、４個の同じ入力データＢの当確投票があるため、入力データＢをラウンド５の当選投票とした。
【００５８】
各ノードは、ラウンド５の投票データを収集する。ノード１，２，５，６は［（ｎ＋ｂ）／２］＋１＝４個の同じ入力データＢの投票を得たので、入力データＢの当確投票をラウンド６の投票とした。ノード３は、既に当選投票を行っており、当該順序番号の入力データを確定しているので、投票の収集も選挙も行わない。
【００５９】
各ノードは、ラウンド６の投票データを収集する。ノード１，２，５，６はｆ＋２ｂ＋１＝４個の同じ入力データＢの当確投票があるため、入力データＢをラウンド７の当選投票とした。ノード３は、既に当選投票を行っており、当該順序番号の入力データを確定しているので、投票の収集も選挙も行わない。
【００６０】
この結果、すべての正常ノードで同一の入力データＢが当該順序番号の入力データとして確定した。この入力データＢは、当該順序番号とともに確定データ記憶部１２に格納される。またノード２の未確定データ記憶部１１に格納されている入力データＢは、削除される。ここまでで、整列マルチキャストが実行されたことになる。
【００６１】
確定した入力データは処理部１８に出力される。処理部１８は、確定した入力データを用いて処理を実行する。各ノードの処理部１８の処理結果として出力される出力データは、出力順序番号とノード番号とを組みにして、出力パケットとしてデータ送信部１６と送受信部２１を介して、クライアント装置２０内の判定部２２に集められる。判定部２２は、同一の出力順序番号と同一の出力データを持つ出力パケットがｂ＋１以上のノードから収集されたときに、その出力データを有効な出力データとして確定する。
【００６２】
整列マルチキャストの流れについてさらに説明する。図５は、第１の実施形態における整列マルチキャストの全体の流れを示すフローチャートである。図５は、各ノードの制御部１９（第１決定部５１、第２決定部５２）で実行される処理を表す。
【００６３】
図５の処理は、例えばクライアント装置２０または他ノードからデータを受信して、未確定データ記憶部１１や投票記憶部１３の内容が変化した時に随時実行される。
【００６４】
第１決定部５１は、現ラウンド番号が１、かつ、ラウンド１の自投票が未決定か否かを判定する（ステップＳ１）。現ラウンド番号が１、かつ、ラウンド１の自投票が未決定の場合（ステップＳ１：Ｙｅｓ）、第１決定部５１は、未確定データ記憶部１１に入力データが記憶されているか否かを判定する（ステップＳ２）。記憶されていない場合（ステップＳ２：Ｎｏ）、処理が終了する。記憶されている場合（ステップＳ２：Ｙｅｓ）、第１決定部５１は、その入力データの推薦投票をラウンド１の自投票とする（ステップＳ３）。
【００６５】
現ラウンド番号が１でないか、または、ラウンド１の自投票が決定済みの場合（ステップＳ１：Ｎｏ）、制御部１９は、現ラウンド番号が奇数であるか否かを判定する（ステップＳ４）。奇数の場合（ステップＳ４：Ｙｅｓ）、第１決定部５１は、収集した現ラウンドの投票の集合に、［（ｎ＋ｂ）／２］＋１ノード以上から同じ入力データの投票があるか否かを判定する（ステップＳ５）。［（ｎ＋ｂ）／２］＋１ノード以上から同じ入力データの投票がある場合（ステップＳ５：Ｙｅｓ）、第１決定部５１は、その入力データの当確投票を次ラウンドの自投票とする（ステップＳ６）。また第１決定部５１は、現ラウンド番号に１を加える。
【００６６】
［（ｎ＋ｂ）／２］＋１ノード以上から同じ入力データの投票がない場合（ステップＳ５：Ｎｏ）、第１決定部５１は、収集した現ラウンドの投票の集合に、（ｎ−ｆ）以上のノードからの投票があるか否かを判定する（ステップＳ７）。（ｎ−ｆ）以上のノードからの投票がない場合（ステップＳ７：Ｎｏ）、処理が終了する。
【００６７】
（ｎ−ｆ）以上のノードからの投票がある場合（ステップＳ７：Ｙｅｓ）、第１決定部５１は、収集した現ラウンドの投票の集合の中から任意に選んだ入力データの補欠投票を次ラウンドの自投票とする（ステップＳ８）。また第１決定部５１は、現ラウンド番号に１を加える。
【００６８】
ステップＳ６の後、ステップＳ８の後、および、ステップＳ４で現ラウンド番号が奇数でない（偶数である）と判定された場合（ステップＳ４：Ｎｏ）、第２決定部５２は、収集した現ラウンドの投票の集合に、（ｆ＋２ｂ＋１）以上のノードから同じ入力データの当確投票があるか否かを判定する（ステップＳ９）。（ｆ＋２ｂ＋１）以上のノードから同じ入力データの当確投票がある場合（ステップＳ９：Ｙｅｓ）、第２決定部５２は、その入力データの当選投票を次ラウンドの自投票とする（ステップＳ１０）。また、第２決定部５２は、その入力データと現順序番号を確定データ記憶部１２に格納する。また、第２決定部５２は、現順序番号を１進め、現ラウンド番号を１にする。この後、ステップＳ１に遷移する。
【００６９】
（ｆ＋２ｂ＋１）以上のノードから同じ入力データの当確投票がない場合（ステップＳ９：Ｎｏ）、第２決定部５２は、収集した現ラウンドの投票の集合に、（ｎ−ｆ）以上のノードから投票があるか否かを判定する（ステップＳ１１）。（ｎ−ｆ）以上のノードから投票がない場合（ステップＳ１１：Ｎｏ）、処理が終了する。
【００７０】
（ｎ−ｆ）以上のノードから投票がある場合（ステップＳ１１：Ｙｅｓ）、第２決定部５２は、収集した現ラウンドの投票の集合に、（ｂ＋１）以上のノードから同じ入力データの当確投票があるか否かを判定する（ステップＳ１２）。（ｂ＋１）以上のノードから同じ入力データの当確投票がある場合（ステップＳ１２：Ｙｅｓ）、第２決定部５２は、その入力データの推薦投票を次ラウンドの自投票とする（ステップＳ１３）。また、第２決定部５２は、現ラウンド番号に１を加える。この後、ステップＳ５に遷移する。
【００７１】
（ｂ＋１）以上のノードから同じ入力データの当確投票がない場合（ステップＳ１２：Ｎｏ）、第２決定部５２は、収集した現ラウンドの投票の集合の中から任意に選んだ入力データの推薦投票を次ラウンドの自投票とする（ステップＳ１４）。また、第２決定部５２は、現ラウンド番号に１を加える。この後、ステップ５に遷移する。
【００７２】
次に、上記アルゴリズムの有効性について証明する。以下の証明では、投票に含まれる入力データを投票の値とも呼ぶ。また、「＃」は集合の要素数を表す記号である。また、「∩」は集合の共通部分を表す記号である。
【００７３】
（補題１）ビザンティン障害の数がｂ以下のとき、同一ラウンドの正常ノードの当確投票の入力データはすべて等しい。
［証明］
ラウンドｒ＋１の２つの正常ノードの当確投票ｘ，ｙの値が等しいことを証明すればよい。当確投票ｘを決定した予備選で用いたラウンドｒの投票のうち、ｘと同じ値の投票の集合をＥｘとする。Ｅｘの投票を行ったノードの集合をＭｘとする。ｙに関しても同様に、ＥｙとＭｙを定義する。するとアルゴリズムの定義より、
＃（Ｍｘ）≧［（ｎ＋ｂ）／２］＋１
＃（Ｍｙ）≧［（ｎ＋ｂ）／２］＋１
である。従って、
＃（Ｍｘ∩Ｍｙ）
≧＃（Ｍｘ）＋＃（Ｍｙ）−ｎ
≧２×（［（ｎ＋ｂ）／２］＋１）−ｎ
≧２×（（ｎ＋ｂ−１）／２＋１）−ｎ＝ｂ＋１
である。すなわち、ＭｘとＭｙの共通部分は少なくともｂ＋１あり、ビザンティン障害の数はｂ以下であるから、そのうちの少なくとも１つは正常ノードである。ラウンドｒのその正常ノードの投票をｚとする。すると、正常ノードの投票は覆ることはないから、ｚ∈Ｅｘ∩Ｅｙである。Ｅｘ、Ｅｙの定義から、ｘとｚの値は等しく、同様にｙとｚの値も等しい。従って、結局ｘとｙの値は等しい。
［証明終］
【００７４】
（補題２）ビザンティン障害の数がｂ以下のとき、同一ラウンドの正常ノードの当選投票の入力データはすべて等しい。
［証明］
ラウンドｒ＋２の２つの正常ノードの当選投票ｘ，ｙの値が等しいことを証明すればよい。当選投票ｘを決定した信任選で用いたラウンドｒ＋１の投票のうち、ｘと同じ値の当確投票の集合をＥｘとする。アルゴリズムの定義より、＃（Ｅｘ）≧ｆ＋２ｂ＋１であり、ビザンティン障害の数はｂ以下であるから、そのうちの少なくとも１つは正常ノードからの投票であり、それは当確投票である。その当確投票をｚとすると、ｘの値とｚの値は等しい。一方、ｘの場合と同様に、∃ｗ、ｗは正常ノードの当確投票でｙの値とｗの値は等しい。ところが補題１より、ラウンドｒ＋１の正常ノードの当確投票の値はすべて等しいから、ｚとｗの値は等しい。従って、「ｘの値」＝「ｚの値」＝「ｗの値」＝「ｙの値」となり、ｘとｙの値は等しい。
［証明終］
【００７５】
（補題３）ビザンティン障害の数がｂ以下のとき、正常ノードの当選投票ｘがあるならば、同一ラウンドの正常ノードの推薦投票の入力データは、ｘの入力データと等しい。
［証明］
当選投票ｘのラウンドをｒ＋２とする。ラウンドｒ＋２の推薦投票をｙとする。このときｘとｙの値が等しいことを証明すればよい。ｘを決定した信任選で用いたラウンドｒ＋１の投票のうち、ｘと同じ値の当確投票の集合をＥｘとする。一方、ｙを決定した信任選で用いたラウンドｒ＋１の投票の集合をＥｙとする。Ｅｘ，Ｅｙの投票を行ったノードの集合をそれぞれＭｘ，Ｍｙとする。アルゴリズムの定義より、
＃（Ｍｘ）≧ｆ＋２ｂ＋１
＃（Ｍｙ）≧ｎ−ｆ
である。従って、
＃（Ｍｘ∩Ｍｙ）≧＃（Ｍｘ）＋＃（Ｍｙ）−ｎ≧２ｂ＋１
である。
すなわち、ＭｘとＭｙの共通部分は少なくとも２ｂ＋１あり、ビザンティン障害の数はｂ以下であるから、そのうちの少なくともｂ＋１は正常ノードである。正常ノードの投票は覆ることはないので、ＥｘとＥｙの中に少なくともｂ＋１の共通の投票があることになる。これらの共通の投票は、Ｅｘに含まれるのでｘと同じ値の当確投票である。従って、Ｅｙの中にｘと同じ値の当確投票がｂ＋１以上あることになる。すると、アルゴリズムの定義より、ｙはｘと同じ値の推薦投票でなければならない。
［証明終］
【００７６】
（補題４）当選、当確の閾値の間には、以下の式（１）の関係がある。
ｆ＋２ｂ＋１≦［（ｎ＋ｂ）／２］＋１≦ｎ−ｆ−ｂ・・・（１）
［証明］
［（ｎ＋ｂ）／２］は、（ｎ＋ｂ）／２を超えない最大の整数で、［］はいわゆるガウスの記号である。なお［（ｎ＋ｂ）／２］＋１は、ｎ＋ｂの過半数である。まず、ガウス記号の定義から以下の関係式（２）および（３）が成り立つ。
（ｎ＋ｂ）／２＜［（ｎ＋ｂ）／２］＋１・・・（２）
［（ｎ＋ｂ）／２］≦（ｎ＋ｂ）／２・・・（３）
初めに、式（１）の左の不等式を証明する。
ｎ＞２ｆ＋３ｂであるから、以下の式（４）が成り立つ。
（ｎ＋ｂ）／２＞（（２ｆ＋３ｂ）＋ｂ）／２＝ｆ＋２ｂ・・・（４）
式（４）と式（２）から、ｆ＋２ｂ＜［（ｎ＋ｂ）／２］＋１が導かれる。この式の両辺は整数なので、結局式（１）の左の不等式が導かれる。
次に、式（１）の右の不等式を証明する。
ｎ＞２ｆ＋３ｂであるから、以下の式（５）が成り立つ。
（ｎ−ｆ−ｂ）−（ｎ＋ｂ）／２＝（ｎ−２ｆ−３ｂ）／２＞０
従って、（ｎ−ｆ−ｂ）  ＞（ｎ＋ｂ）／２・・・（５）
式（３）と式（５）から、［（ｎ＋ｂ）／２］＜ｎ−ｆ−ｂが導かれるが、この式の両辺は整数なので、結局式（１）の右の不等式が導かれる。
［証明終］
【００７７】
（補題５）ビザンティン障害の数がｂ以下のとき、正常ノードの当選投票ｘがあるならば、次のラウンドの正常ノードの投票は当確投票で、その入力データはｘの入力データと等しい。
［証明］
ｘのラウンドをｒとする。ラウンドｒの投票は当選投票か推薦投票のどちらかである。従って、補題２と補題３より、ラウンドｒの正常ノードの投票の値はｘの値と等しい。すなわち、ラウンドｒの正常ノードの投票の値はすべて等しい。このとき、ラウンドｒ＋１の投票ｙが補欠投票でないことを背理法で証明する。
（背理法）ラウンドｒ＋１の投票ｙが補欠投票であると仮定する。ｙを決定した予備選で用いたラウンドｒの投票の集合をＥｙとする。アルゴリズムの定義より、＃（Ｅｙ）≧ｎ−ｆであり、ビザンティン障害の数はｂ以下であるから、そのうちの少なくともｎ−ｆ−ｂは正常ノードの投票である。上述したとおり、これらの投票はすべて同じ値である。ところが、補題４より［（ｎ＋ｂ）／２］＋１≦ｎ−ｆ−ｂであるから、［（ｎ＋ｂ）／２］＋１以上の同じ値の投票がＥｙにあることになる。これは、予備選で当確投票が選択される条件を満たしていることになるから、アルゴリズムの定義に矛盾する。よって、ｙは補欠投票ではありえない。ｙは補欠投票ではないから、当確投票である。するとｙを決定した予備選のラウンドｒの投票で［（ｎ＋ｂ）／２］＋１以上のｙの値と同じ値の投票がある。ｂ＋１≦［（ｎ＋ｂ）／２］＋１であるから、これらのうち少なくとも１つは正常ノードの投票があり、上述したとおり、その値はｘの値と等しい。従って、ｘとｙの値は等しい。
［証明終］
【００７８】
（補題６）ビザンティン障害の数がｂ以下のとき、正常ノードの当選投票ｘがあるならば、２つ後のラウンドの正常ノードの投票は当選投票で、その入力データはｘの入力データと等しい。
［証明］
ｘのラウンドをｒとする。補題５より、ラウンドｒ＋１の正常ノードの投票は当確投票であり、その値はｘの値と等しい。すなわち、ラウンドｒ＋１の正常ノードの投票の値はすべて等しい。このとき、ラウンドｒ＋２の投票ｙが推薦投票でないことを背理法で証明する。
（背理法）ラウンドｒ＋２の投票ｙが推薦投票であると仮定する。ｙを決定した信任選で用いたラウンドｒ＋１の投票の集合をＥｙとする。アルゴリズムの定義より、＃（Ｅｙ）≧ｎ−ｆであり、ビザンティン障害の数はｂ以下であるから、そのうちの少なくともｎ−ｆ−ｂは正常ノードの投票である。上述したとおり、これらの投票はすべて同じ値の当確投票である。ところが、補題４よりｆ＋２ｂ＋１≦ｎ−ｆ−ｂであるから、ｆ＋２ｂ＋１以上の同じ値の当確投票がＥｙにあることになる。これは、信任選で当選投票が選択される条件を満たしていることになるから、アルゴリズムの定義に矛盾する。よって、ｙは推薦投票ではありえない。ｙは推薦投票ではないから、当選投票である。するとｙを決定した信任選のラウンドｒ＋１の投票でｆ＋２ｂ＋１以上のｙの値と同じ値の投票がある。ｂ＋１≦ｆ＋２ｂ＋１であるから、これらのうち少なくとも１つは正常ノードの投票があり、上述したとおり、その値はｘの値と等しい。従って、ｘとｙの値は等しい。
［証明終］
【００７９】
補題２と補題６から、ビザンティン障害の数がｂ以下のとき、正常ノードの当選投票は、ラウンドが異なっているとしてもすべて同じ入力データであることがわかる。すなわち、正常ノードで最初に当選投票となったラウンドをｒとすると、ラウンドｒ＋２までにはすべての正常ノードの投票は当選投票となり、すべての正常ノードで確定する入力データは同一となる。
【００８０】
一方、ビザンティン障害となっているノードから出力されるデータは虚偽のデータであるかもしれない。しかし、判定部２２において出力パケットを収集し、ｂ＋１以上のノードから同一の出力データを受信できれば、それらのうちの少なくとも１つは正常ノードから出力されたものであるから、その出力データは正当である。
【００８１】
これにより本実施形態のアルゴリズムは、ビザンティン障害の耐性を有し、多重化の一貫性が保証されていることが証明された。
【００８２】
最後に、本実施形態のアルゴリズムが、障害の発生時にタイムアウトによる処理の中断が発生しない点（リアルタイム性）について説明する。
【００８３】
本実施形態のアルゴリズムは、ｎ−ｆの投票が収集できればラウンドが進んでいく。このとき、どのノードがどのような障害となっているかについて全く関知していない。従って、ノード障害がｆ以下であれば、どのようなタイミングで障害が発生したとしても、少なくともｎ−ｆの投票は必ず収集できるから、ラウンドが進んでいく。
【００８４】
本実施形態のアルゴリズムは、ｎ−ｆの投票が収集できた時点でラウンドが進む。障害ノード数が少ない場合には、ｎ−ｆより多くの投票を集められる可能性があるが、その収集を待つことはしない。これによって、リアルタイム性を確保することができる。すなわち、すべてのノードの投票を集めるまで待つのではなく、ｎ−ｆの投票が収集できた時点でラウンドを進めていくことにより、障害検出に依存しない多重化を実現している。なお、リアルタイム性が要求されない場合は、例えばタイムアウトになるまではすべてのノードの投票が収集されるまで待つように構成してもよい。
【００８５】
本実施形態のアルゴリズムでは、当選投票を得るまでのラウンド数については、一定ではない。これはアルゴリズム中でランダム選択に依存している箇所があるためである。ランダム選択の運が良ければ、早い段階のラウンドで各ノードの投票が同一となり、当選投票を得る。運が悪ければ、いつまでたっても各ノードの投票が同一とならない。しかし、確率的な視点では、いつまでたっても当選投票が得られない可能性は、限りなく０に近い。これは確率的終了条件と呼ばれる考え方である。
【００８６】
なお、補欠投票および推薦投票で、「ランダム」に選ぶ処理は、文字通りランダムに選んでもアルゴリズムの正当性には変わりはないが、選び方によって当選投票となるまでの平均ラウンド数が変わる。ラウンド番号が小さいときに、ヒューリスティックな方法で、各ノードが同一の入力データを選びやすいように疑似乱数を調整すると、アルゴリズムの効率が大幅に向上する。実用上は、このようなヒューリスティックな方法を用いることにより、平均的な最大ラウンド番号≒４とすることが可能である。ただし、この選択を完全に固定すると、アルゴリズムが完了しなくなる恐れがあるので、アルゴリズムとしてランダム選択がまったく不要なわけではない。
【００８７】
例えば、ランダムに投票を選択する方式の代わりに、以下のように所定の規則に従い投票を選択してもよい。
（１）ラウンドごとに優先するノードを定め、優先するノードの投票を、次の選挙で選択する。優先するノードは、ラウンドごとに変更する。例えば、ノード番号順に優先するノードを変更する。
（２）対応するデータの値が小さい投票を優先して選択する。
（３）偏りのある疑似乱数を生成する。
【００８８】
（第２の実施形態）
第１の実施形態は、クライアント装置２０と多重化システム（サーバ装置１０）との間で入出力を行う構成であった。第２の実施形態では、多重化システムαと多重化システムβの間で入出力を行う。すなわち、多重化システムαの出力データが多重化システムβの入力データとなる。
【００８９】
図６は、第２の実施形態にかかる情報処理システムに含まれるサーバ装置１０βの構成の一例を示すブロック図である。サーバ装置１０βは、情報処理システムの１つである多重化システムβに含まれる装置である。図６では１のサーバ装置１０βのみを記載しているが、サーバ装置１０βの個数は図１と同様に４以上であれば任意である。多重化システムβは、同様の構成を備える多重化システムαと接続される。
【００９０】
サーバ装置１０βは、判定部２２をさらに備える点が、図２のサーバ装置１０と異なっている。その他の構成および機能は、第１の実施形態にかかるサーバ装置１０の構成を表すブロック図である図２と同様であるので、同一符号を付し、ここでの説明は省略する。
【００９１】
図６に示すように、本実施形態では、判定部２２が多重化システムβの各サーバ装置１０βに配置される。多重化システムαの各ノード（サーバ装置１０α）から出力される出力パケットは、データ受信部１５を介して、判定部２２に入力される。判定部２２は、次に確定すべき出力データの出力順序番号（現出力順序番号）を保持する。判定部２２は、現出力順序番号を持つ出力パケットのうち、同一の出力データを持つ出力パケットが、ｂα＋１以上のノードから受信されたとき、その出力データを入力データとして、未確定データ記憶部１１に格納し、現出力順序番号を１進める。ここで、ｂαは多重化システムαの信頼性の閾値である。その他の部分については、第１の実施形態と同じである。
【００９２】
この構成によって、多重化システム間の入出力を行う場合でも、非同期ネットワークモデルを前提として、ビザンティン障害となったコンピュータ数がｂ以下ならば、多重化システムから得られる有効な出力データは正当であり、さらに、ノード障害の数がｆ以下ならば、多重化システムは処理を継続できる、多重化制御が実現される。
【００９３】
（第３の実施形態）
サイバー攻撃による不正侵入が懸念されている。分散システムへのサイバー攻撃に関する懸念の１つは、脆弱性のある、いずれか１つのノードに不正侵入され、その結果として他のノードも芋づる式に不正侵入されることである。一般的に言えば、多重化システムではノード数を多くすることにより可用性と信頼性が向上する。しかし、ノード数が多くなることにより、脆弱性のあるノードに不正侵入される可能性は高まる。仮に各ノードが互いに相互信頼していて、芋づる式に他のノードも不正侵入される構成であったとすると、セキュリティは却って下がっていることになる。
【００９４】
従って、上記懸念に対して耐性を高めるためには、各ノードが独立してセキュリティを確保し、１つのノードが乗っ取られたとしても、他のノードにそれが容易に伝染しないようにすることが必要である。具体的には、パスワードや秘密鍵を共通にしない、相互信頼の設定をしない、ノードごとにファイアウォールを設ける、ＯＳ（オペレーティングシステム）やミドルウェアは異なるものを使う、および、管理者やベンダーを固定しない、といった対策が行われている。
【００９５】
上記前提の上に立って、なりすまし攻撃をふせぐための仕組みを上記各実施形態に追加することで、最大でｂのノードが乗っ取られたとしても、正しい出力データが得られる多重化システムが構成できる。これを以下に説明する。
【００９６】
ここで懸念するなりすまし攻撃には、
（１）入力データを不正なデータに置き換える
（２）出力パケットを不正なデータに置き換える
（３）投票を不正なデータに置き換える
の３つが考えられる。
【００９７】
そもそも、クライアント装置２０が送信する入力データや、正常ノードの出力データを攻撃者が自由に改ざんできるとすると、当然、正しい結果は得られない。また、正常ノードの投票を攻撃者が自由に改ざんできるとすると、簡単にアルゴリズムの正当性が破たんして、やはり正しい結果が得られる保証はなくなる。
【００９８】
本実施形態の構成は以下のとおりである。
（Ａ）各ノードとクライアント装置２０は個別の秘密鍵を持ち、これらは互いに秘密である。
（Ｂ）それぞれの公開鍵は、各ノードとクライアント装置２０に事前に配布されている。
（Ｃ）クライアント装置２０は入力データに自身の秘密鍵で署名を付与する。
（Ｄ）各ノードは入力データをクライアント装置２０から受信するとき、その署名を検証し、正当でない入力データは破棄する。
（Ｅ）各ノードは投票に自身の秘密鍵で署名を付与する。
（Ｆ）各ノードは投票を他ノードから受信するとき、その署名を検証し、さらに、投票に含まれる入力データのクライアント装置２０の署名も検証し、正当でない投票は破棄する。
（Ｇ）各ノードは出力パケットに自身の秘密鍵で署名を付与する。
（Ｈ）クライアント装置２０は出力パケットを受信するとき、その署名を検証し、正当でない出力パケットは破棄する。
【００９９】
入力パケットは、例えば以下のフォーマットとなる。
（入力データ、入力データへのクライアント装置２０による署名）
【０１００】
投票は、例えば以下のフォーマットとなる。
（順序番号、ラウンド番号、ノード番号、選択結果、入力データ、入力データへのクライアント装置２０による署名、この投票へのノードによる署名）
【０１０１】
出力パケットは、例えば以下のフォーマットとなる。
（順序番号、ノード番号、出力データ、このパケットへのノードによる署名）
【０１０２】
これらの対策により、上記（１）、（２）、（３）のなりすましは非常に困難になり、不正侵入に対する耐性が向上する。なぜなら、クライアント装置２０または正常ノードから受信したデータは、デジタル署名によって、改ざんされていないことを検証でき、本実施形態のアルゴリズム中で行われる選挙の有効性が保証されるためである。
【０１０３】
署名の検証は、例えばデータを受信する構成部（投票送受信部１７、データ受信部１５等）で実行する。これ以外の構成部で署名の検証を実行してもよい。
【０１０４】
なお、不正侵入されたノードからは、どのような不正な投票も攻撃者は送信可能であり、これを受信した正常ノードが署名の検証だけで偽の投票を除外できるわけではない。しかし、不正侵入されたノードがｂ以下であれば、本実施形態のアルゴリズムにより出力データの正当性が保証される。
【０１０５】
対策（Ｆ）で、投票中の入力データの署名も検証する理由は、仮にこれを行わないと、ビザンティン障害ノードから送られてきた投票に含まれる不正な入力データを、補欠投票またはランダム選択の推薦投票として採用してしまい、結果としてその後のラウンドでその不正な入力データが当選投票となる可能性があるからである。
【０１０６】
入力データへの署名は、クライアント装置２０が行ったものであり、ビザンティン障害ノードはクライアント装置２０の署名は偽造できないことから、対策（Ｆ）が有効である。
【０１０７】
なお、処理部１８の入り口で、入力データの署名を検証して正当でない入力データを破棄するならば、（Ｆ）の処理で入力データの署名を検証しなくても、整合性は保たれる。しかし、この場合は、不正な入力データの破棄が遅れるため、攻撃によってアルゴリズムの効率が大きく低下するという問題がある。
【０１０８】
ところで、一般に、署名の付与および検証は計算コストが大きい。そこで、投票と出力データの署名および検証の代わりに、セキュリティが確保された通信を用いてデータを送受信するように構成してもよい。例えば、通信相手（クライアント装置２０、他のノード）との間でＳＳＬ（Secure  Sockets  Layer）などのプロトコルに従った通信を確立し、この通信を介してデータを送受信してもよい。これにより計算コストを下げることができる。
【０１０９】
次に、第２の実施形態に対して適用する場合の例を説明する。第１の実施形態の場合との差異は、出力パケットへの署名のつけ方と、入力データに付与する署名の数である。多重化システムαは、出力パケットに署名をするのではなく、「αの出力順序番号と出力データの組」に署名をする。また、多重化システムβの入力データは「αの出力順序番号と出力データの組」とする。入力データには、多重化システムαの各ノードの署名が複数付与される。多重化システムαの信頼性の閾値をｂαとしたとき、付与される署名はｂα＋１以上なければならない。ここで、署名する主体が異なる秘密鍵を持つので、これらの署名はすべて異なることに注意する。
【０１１０】
多重化システムαの出力パケットは、例えば以下のフォーマットとなる。
（αの出力順序番号、ノード番号、出力データ、［αの出力順序番号、出力データ］へのノードによる署名）
【０１１１】
多重化システムβの投票は、例えば以下のフォーマットとなる。
（βの順序番号、ラウンド番号、ノード番号、選択結果、入力データ、入力データへの多重化システムαの各ノードの署名の集合、この投票へのノードによる署名）
【０１１２】
入力データのフォーマットは、例えば［αの出力順序番号、出力データ］である。
【０１１３】
判定部２２は、正当な署名のある同じ出力順序番号と出力データを持つαの出力パケットがｂα＋１個以上あるとき、その［αの出力順序番号、出力データ］を入力データとし、それらの署名の集合をその入力データに付与する。そして、多重化システムβは、入力データの署名の検証（対策（Ｆ））として、付与されているｂα＋１個以上の多重化システムαの各署名をすべて検証する。
【０１１４】
これらの対策により、第２の実施形態においても、正常ノードに関して上記（１）、（２）、（３）のなりすましは非常に困難になり、不正侵入に対する耐性が向上する。特に、多重化システムβの対策（Ｆ）で、入力データの署名の検証として、付与されているｂα＋１個以上の多重化システムαの各署名をすべて検証することにより、不正な入力データを除外して、入力データの改ざんへの耐性を担保している。
【０１１５】
（第４の実施形態）
第１の実施形態では、各ノードの現ラウンドは選挙によってのみ進んでいく構成であったが、他ノードの投票をコピーするアルゴリズムを追加することによって、アルゴリズムの実行効率を上げることができる。
【０１１６】
コピー投票は、同一ラウンドの他ノードの投票の集合から、当該ラウンドの自投票を決定する。一方、選挙は同一ラウンドの投票の集合から、次のラウンドの自投票を決定することに注意する。
【０１１７】
コピー投票としては、一致コピー、補欠コピー、および、推薦コピーの少なくとも１つを適用できる。一致コピーは、例えば第１決定部５１および第２決定部５２が実行するように構成できる。また、補欠コピーは、例えば第２決定部５２が実行するように構成できる。また、推薦コピーは、例えば第１決定部５１が実行するように構成できる。
【０１１８】
一致コピーは、収集した同一ラウンドの投票について、（ｂ＋１）以上のノードから、「入力データと選択結果」が同じ投票が存在する場合に、その投票に、投票することを意味する。
【０１１９】
補欠コピーは、（ｂ＋１）以上のノードから補欠投票がある場合に、収集した投票の中から任意に選んだ入力データの補欠に投票することを意味する。なお、選択の対象とする投票は、他のノードから収集したすべての投票であってもよいし、（ｂ＋１）以上のノードから収集した補欠投票であってもよい。
【０１２０】
推薦コピーは、（２ｂ＋１）以上のノードから推薦投票があり、一致コピーが成立しない場合に、収集した投票の中から任意に選んだ入力データの推薦に投票することを意味する。なお、選択の対象とする投票は、他のノードから収集したすべての投票であってもよいし、（２ｂ＋１）以上のノードから収集した推薦投票であってもよい。
【０１２１】
なお、自投票が既に決まっている場合には、当該ラウンドのコピー投票は行わない。
【０１２２】
コピー投票の意義は、選挙が必要とするよりも少ない投票数で、同じラウンドの投票を決定し、結果として当該ラウンドの投票を増やしていく点にある。コピー投票を各ノードが実行していけば、やがては選挙に必要な投票数が得られる。すなわち、コピー投票自体はラウンドを進めるものではないが、結果として選挙を成立させてラウンドを進める効果がある。
【０１２３】
例として、ラウンドｒに当選投票があったとする。するとアルゴリズムの定義から、ラウンドｒ−１のｆ＋２ｂ＋１の同じ値の当確投票がある。ノード障害数の最大はｆであるから、そのうち少なくとも２ｂ＋１の投票は稼働ノードの投票である。これらはすべて同じ値の当確投票であるから、ラウンドｒ−１の一致コピーの条件を成立させるのに十分である。
【０１２４】
別の例として、ラウンドｒに当確投票があったとする。するとアルゴリズムの定義から、ラウンドｒ−１の［（ｎ＋ｂ）／２］＋１の同じ値の投票がある。ノード障害数の最大はｆであり、補題４より、ｆ＋２ｂ＋１≦［（ｎ＋ｂ）／２］＋１であるから、そのうち少なくとも２ｂ＋１の投票は稼働ノードの投票である。するとこれらのうち、当選投票か推薦投票のどちらかがｂ＋１以上あることになる。これらはすべて同じ値の当確投票であるから、ラウンドｒ−１の一致コピーの条件を成立させるのに十分である。
【０１２５】
別の例として、ラウンドｒに補欠投票があったとする。するとアルゴリズムの定義から、ラウンドｒ−１のｎ−ｆの投票がある。ノード障害数の最大はｆであるから、そのうち少なくともｎ−２ｆの投票は稼働ノードの投票である。ｎ＞２ｆ＋３ｂであるから、ｎ−２ｆ≧３ｂ＋１であり、当選投票がｂ＋１以上あるか、推薦投票が２ｂ＋１以上あることになる。稼働ノードは正常ノードであるから、前者の場合は補題２より当選投票はすべて同じ値であり一致コピーの条件が成立する。後者の場合は、推薦コピーの条件の前半が成立している。まとめると、推薦コピーか一致コピーのどちらかを成立させるのに十分である。
【０１２６】
次に、コピー投票の有効性について説明する。すなわち、ビザンティン障害ノード数がｂ以下の時、コピー投票によって多重化の一貫性が破れないことを説明する。
【０１２７】
ある正常ノードの投票ｘがあったとする。投票ｘを決定する際に収集した投票の集合をＥとする。選挙のアルゴリズムにおいて、収集する投票には自ノードの投票が含まれている必要はなく、ノード番号にも無関係である。従って、別の正常ノードが収集した投票の集合がＥと全く同じであってもよい。アルゴリズムには、ランダム選択の要素があるので、Ｅから決定される投票は必ずｘと同じになるとは限らないが、ランダム選択なので同じになる可能性はある。
【０１２８】
従って、ある正常ノードの投票ｘがあるとき、別の正常ノードの投票がｘと同じ内容（入力データと選択結果）となる可能性がある。すなわち、ある正常ノードの投票ｘの内容を別の正常ノードにコピーしたとしても、多重化の整合性は破れない。仮に、破れるとしたら、コピーではなく選挙でそれが決定した場合にも、整合性が破れるということになり矛盾する。もちろん、任意のノードから単純に投票をコピーするのは望ましくない。コピー元がビザンティン障害ノードであるかもしれないからである。しかし、ｂ＋１ノードから同一内容の投票が得られれば、そのうちの少なくとも１つは正常ノードであるので、どのノードが正常ノードであるかわからなくても、投票のコピーをしてもかまわない（一致コピーの正当性）。
【０１２９】
一方、補欠投票は、必ずランダム選択で入力データが決定されるので、ある正常ノードの補欠投票ｘがあるとき、別の正常ノードの投票は、任意の入力データの補欠投票となる可能性がある。これは、ランダム選択でビザンティン障害ノードの投票を選ぶ可能性があるためである。すると、ｂ＋１ノードから補欠投票が得られれば、そのうちの少なくとも１つは正常ノードであるので、どのノードが正常ノードであるかわからなくても、補欠投票をしてもかまわない（補欠コピーの正当性）。
【０１３０】
推薦投票は、ランダム選択の場合と、ｂ＋１以上の当確投票から決定される場合がある。２ｂ＋１ノードから推薦投票が得られれば、そのうちの少なくともｂ＋１は正常ノードの投票である。このうち、１つでもランダム選択で決定された推薦投票があるならば、補欠投票の場合と同じ論理で、任意の入力データの推薦投票をしてかまわない（推薦コピーの正当性）。一方、１つもランダム選択による推薦投票がないとすると、補題１より、正常ノードの当確投票の入力データはすべて等しいから、そこから決定される推薦投票の入力データもすべて同一となり、その場合は一致コピーの条件が成立することになる。なお推薦コピーは一致コピーが成立しないことが条件になっていることに注意する。
【０１３１】
以上で、コピー投票の正当性が示された。
【０１３２】
３種類のコピー投票はそれぞれ独立しており、一致コピー、補欠コピー、および、推薦コピーのすべてを適用してもよいし、そのうちのいくつかを適用してもよい。コピー投票の適用の度合いによって、アルゴリズムの実行効率の改善の程度が変わる。
【０１３３】
なお、補欠コピーと推薦コピーの閾値は、閾値よりも大きくてもよい。より大きい閾値の採用は、コピーによるアルゴリズムの実行効率改善を低下させるが、一方でビザンティン障害ノードからの影響も低下させるため、いちがいに悪いとは言えない。
【０１３４】
上述のように、コピー投票の変形は様々な形で可能であり、アルゴリズムの実行効率に係るが、これらの変形は設計事項であり、本発明の範囲に含まれる。
【０１３５】
（変形例１）
上記実施形態における、当選決定の閾値ｆ＋２ｂ＋１、当確決定の閾値［（ｎ＋ｂ）／２］＋１、出力データ決定の閾値ｂ＋１、および、推薦コピーの閾値２ｂ＋１をそれぞれ一般化して、ｔ１、ｔ２、ｔ３、ｔ４とする。ｔ１、ｔ２、ｔ３、ｔ４が以下の条件を満たしているならば、アルゴリズムは依然として有効である。
ｆ＋２ｂ＋１≦ｔ１≦ｎ−ｆ−ｂ
［（ｎ＋ｂ）／２］＋１≦ｔ２≦ｎ−ｆ−ｂ
ｂ＋１≦ｔ３≦ｎ−ｆ−ｂ
２ｂ＋１≦ｔ４≦ｎ−ｆ−ｂ
【０１３６】
ただし、閾値が小さいほうが、アルゴリズムの実行効率がよい。閾値を大きくするとアルゴリズムの冗長性が大きくなる効果がある。
【０１３７】
（変形例２）
上記実施形態では、補欠状態、当確状態、推薦状態、および、当選状態の４種類の状態を用いたが、他の方法で定義した状態を用いてもよい。例えば、これらの４種類の状態を以下のように置き換えてもよい。
推薦状態→奇数ラウンドの推薦状態
補欠状態→偶数ラウンドの推薦状態
当選状態→奇数ラウンドの当選状態
当確状態→偶数ラウンドの当選状態
【０１３８】
この定義方法では、見かけ上は推薦状態および当選状態の２状態となる。しかし、これらの２状態は、上記実施形態の４種類の状態と本質的に全く同じものであり、本発明の範囲に含まれる。
【０１３９】
次に、本実施形態の各装置（サーバ装置１０およびクライアント装置２０）のハードウェア構成の一例について説明する。図７は、実施形態の装置のハードウェアの構成の一例を示す図である。
【０１４０】
本実施形態の装置は、制御装置３１、主記憶装置３２、補助記憶装置３３、表示装置３４、入力装置３５および通信装置３６を備える。制御装置３１、主記憶装置３２、補助記憶装置３３、表示装置３４、入力装置３５および通信装置３６は、バス３７を介して互いに接続されている。
【０１４１】
制御装置３１は、補助記憶装置３３から主記憶装置３２に読み出されたプログラムを実行する。主記憶装置３２は、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やＲＡＭ等のメモリである。補助記憶装置３３は、例えば、ＨＤＤやメモリカード等である。表示装置３４は、装置の状態等を表示する画面である。表示装置３４は、例えば、液晶ディスプレイ等である。入力装置３５は、装置を操作するためのインタフェースである。入力装置３５は、例えば、キーボードやマウス等である。通信装置３６は、ネットワークに接続するためのインタフェースである。
【０１４２】
本実施形態の装置で実行されるプログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、メモリカード、ＣＤ−ＲおよびＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録し、コンピュータ・プログラム・プロダクトとして提供してもよい。また、本実施形態の装置で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供してもよい。また、本実施形態の装置で実行されるプログラムをダウンロードさせずに、インターネット等のネットワーク経由で提供、又は配布してもよい。また、本実施形態の装置のプログラムを、ＲＯＭ等に予め組み込んで提供してもよい。
【０１４３】
本実施形態のサーバ装置１０で実行されるプログラムは、上述したサーバ装置１０の各機能ブロックのうち、プログラムとしても実現可能な機能ブロックを含むモジュール構成となっている。
【０１４４】
また、本実施形態のクライアント装置２０で実行されるプログラムは、上述したクライアント装置２０の各機能ブロックを含むモジュール構成となっている。
【０１４５】
当該モジュールは、実際のハードウェアとしては、制御装置３１が上記記憶媒体からプログラムを読み出して実行することにより、上記各モジュールが主記憶装置３２上にロードされる。すなわち、上記各モジュールは、主記憶装置３２上に生成される。なお、装置の各機能ブロックの一部、又は全部を、プログラムにより実現せずに、ＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）等のハードウェアにより実現してもよい。
【０１４６】
なお、本実施形態では、複数のサーバ装置１０の間で投票を送受信する例について説明した。しかしながら、本実施形態は、サーバ装置１０に限らず、パーソナルコンピュータ、仮想マシン、ＯＳ上のプロセスなどにも適用可能である。同様に、クライアント装置２０を、パーソナルコンピュータ、仮想マシン、ＯＳ上のプロセスなどにすることも可能である。また、ネットワーク３０は、ＬＡＮの他に、インターネットなどの広域ネットワーク（ＷＡＮ）であってもよいし、仮想ネットワークやプロセス間通信（ＩＰＣ）などでもよい。
【０１４７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１４８】
１０、１０α、１０β  サーバ装置
１１  未確定データ記憶部
１２  確定データ記憶部
１３  投票記憶部
１５  データ受信部
１６  データ送信部
１７  投票送受信部
１８  処理部
１９  制御部
２０  クライアント装置
２１  送受信部
２２  判定部
３０  ネットワーク
５１  第１決定部
５２  第２決定部
１００  情報処理システム
【図１】
2015140942.tif 000003
【図２】
2015140942.tif 000004
【図３】
2015140942.tif 000005
【図４】
2015140942.tif 000006
【図５】
2015140942.tif 000007
【図６】
2015140942.tif 000008
【図７】
2015140942.tif 000009
【手続補正書】
【提出日】平成26年8月25日(2014.8.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ｎ以上（ｎはｎ＞２ｆ＋３ｂを満たす整数、ｆは許容される最大ノード障害数を表す０以上の整数、ｂは許容される最大ビザンティン障害数を表す１以上の整数）のサーバ装置を備える情報処理システムであって、
データに対して選択された、第１確定状態、第１推薦状態、および、第２確定状態のいずれかである選択結果を受信する受信部と、
同じデータに対してｔ２（ｔ２は（ｎ＋ｂ）／２＜ｔ２≦ｎ−ｆ−ｂを満たす整数）以上の前記第１推薦状態または前記第１確定状態の前記選択結果が選択されたことを示す第１条件を満たす場合、当該データに対して第２確定状態の選択結果を決定する第１決定処理、を実行する第１決定部と、
同じデータに対してｔ１（ｔ１は、ｆ＋２ｂ＋１≦ｔ１≦ｎ−ｆ−ｂを満たす整数）以上の前記第２確定状態の前記選択結果が選択されたことを示す第２条件を満たす場合、当該データに対して第１確定状態の選択結果を決定し、前記第２条件を満たさず、かつ同じデータに対して（ｂ＋１）以上の第２確定状態の前記選択結果が選択されたことを示す第３条件を満たす場合、当該データに対して第１推薦状態の選択結果を決定する第２決定処理、を実行する第２決定部と、
前記第１確定状態に決定されたデータに対して処理を実行して出力結果を出力する処理部と、
ｔ３（ｔ３は、ｂ＋１≦ｔ３≦ｎ−ｆ−ｂを満たす整数）以上の同じ出力結果を受信した場合に、受信した出力結果が有効であると判定する判定部と、
を備える情報処理システム。
【請求項２】
前記受信部は、さらに、データに対して選択された第２推薦状態である選択結果を受信し、
前記第１決定処理は、さらに、前記第１条件を満たさず、かつ（ｎ−ｆ）以上から前記第１推薦状態または前記第１確定状態の選択結果が受信されたことを示す第４条件を満たす場合、前記選択結果が受信されたデータから選択された１のデータに対して第２推薦状態の選択結果を決定する処理を含み、
前記第２決定処理は、さらに、前記第２条件および前記第３条件を満たさず、かつ（ｎ−ｆ）以上から前記第２推薦状態または前記第２確定状態の選択結果が受信されたことを示す第５条件を満たす場合、前記選択結果が受信されたデータから選択された１のデータに対して第１推薦状態の選択結果を決定する処理を含む、
請求項１に記載の情報処理システム。
【請求項３】
前記第１決定処理は、前記第１条件を満たさずかつ前記第４条件を満たす場合、ランダムに選択された１のデータ、または、所定の規則に従い選択された１のデータに対して第２推薦状態の選択結果を決定する処理を含む、
請求項２に記載の情報処理システム。
【請求項４】
前記第２決定処理は、前記第５条件を満たす場合に限り、第１推薦状態の選択結果を決定する処理を含む、
請求項２に記載の情報処理システム。
【請求項５】
前記第２決定処理は、前記第２条件および前記第３条件を満たさずかつ前記第５条件を満たす場合、ランダムに選択された１のデータ、または、所定の規則に従い選択された１のデータに対して第１推薦状態の選択結果を決定する処理を含む、
請求項２に記載の情報処理システム。
【請求項６】
前記第１決定処理、および、前記第１決定処理後に実行される前記第２決定処理が、前記第１確定状態の選択結果が決定されるまで繰り返される、
請求項１に記載の情報処理システム。
【請求項７】
前記受信部は、受信した選択結果が正当であるか否かを署名に基づいて検証し、
前記第１決定部は、正当であると検証された選択結果を用いて前記第１決定処理を実行し、
前記第２決定部は、正当であると検証された選択結果を用いて前記第２決定処理を実行する、
請求項１に記載の情報処理システム。
【請求項８】
前記受信部は、さらに、前記選択結果に対応するデータを受信し、受信したデータが正当であるか否かを署名に基づいて検証し、
前記第１決定部は、さらに、正当であると検証されたデータに対応する選択結果を用いて前記第１決定処理を実行し、
前記第２決定部は、さらに、正当であると検証されたデータに対応する選択結果を用いて前記第２決定処理を実行する、
請求項７に記載の情報処理システム。
【請求項９】
前記第２決定部は、さらに、同じデータに対してｔ３以上の同じ状態の前記第１推薦状態または前記第１確定状態の選択結果が他のサーバ装置から受信された場合、当該データに対して前記同じ状態の選択結果を決定する処理を実行する、
請求項１に記載の情報処理システム。
【請求項１０】
前記受信部は、さらに、データに対して選択された第２推薦状態である選択結果を受信し、
前記第１決定部は、さらに、同じデータに対してｔ３以上の同じ状態の前記第２推薦状態または前記第２確定状態の選択結果が他のサーバ装置から受信された場合、当該データに対して前記同じ状態の選択結果を決定する処理を実行する、
請求項１に記載の情報処理システム。
【請求項１１】
前記受信部は、さらに、データに対して選択された第２推薦状態である選択結果を受信し、
前記第１決定部は、さらに、ｔ３以上の第２推薦状態の選択結果が他のサーバ装置から受信された場合、任意に選択したデータに対して第２推薦状態の選択結果を決定する処理を実行する、
請求項１に記載の情報処理システム。
【請求項１２】
前記第２決定部は、さらに、ｔ４（ｔ４は、２ｂ＋１≦ｔ４≦ｎ−ｆ−ｂを満たす整数）以上の第１推薦状態の選択結果が他のサーバ装置から受信され、かつ、同じデータに対してｔ３以上の第１推薦状態の選択結果が他のサーバ装置から受信されていない場合、任意に選択したデータに対して第１推薦状態の選択結果を決定する処理を実行する、
請求項１に記載の情報処理システム。
【請求項１３】
ｎ以上（ｎはｎ＞２ｆ＋３ｂを満たす整数、ｆは許容される最大ノード障害数を表す０以上の整数、ｂは許容される最大ビザンティン障害数を表す１以上の整数）のサーバ装置を備える情報処理システムの前記サーバ装置であって、
データに対して選択された、第１確定状態、第１推薦状態、および、第２確定状態のいずれかである選択結果を受信する受信部と、
同じデータに対してｔ２（ｔ２は（ｎ＋ｂ）／２＜ｔ２≦ｎ−ｆ−ｂを満たす整数）以上の前記第１推薦状態または前記第１確定状態の前記選択結果が選択されたことを示す第１条件を満たす場合、当該データに対して第２確定状態の選択結果を決定する第１決定処理、を実行する第１決定部と、
同じデータに対してｔ１（ｔ１は、ｆ＋２ｂ＋１≦ｔ１≦ｎ−ｆ−ｂを満たす整数）以上の前記第２確定状態の前記選択結果が選択されたことを示す第２条件を満たす場合、当該データに対して第１確定状態の選択結果を決定し、前記第２条件を満たさず、かつ同じデータに対して（ｂ＋１）以上の第２確定状態の前記選択結果が選択されたことを示す第３条件を満たす場合、当該データに対して第１推薦状態の選択結果を決定する第２決定処理、を実行する第２決定部と、
前記第１確定状態に決定されたデータに対して処理を実行して出力結果を出力する処理部と、
を備えるサーバ装置。
【請求項１４】
ｎ以上（ｎはｎ＞２ｆ＋３ｂを満たす整数、ｆは許容される最大ノード障害数を表す０以上の整数、ｂは許容される最大ビザンティン障害数を表す１以上の整数）のサーバ装置を備える情報処理システムで実行される情報処理方法であって、
データに対して選択された、第１確定状態、第１推薦状態、および、第２確定状態のいずれかである選択結果を受信する受信ステップと、
同じデータに対してｔ２（ｔ２は（ｎ＋ｂ）／２＜ｔ２≦ｎ−ｆ−ｂを満たす整数）以上の前記第１推薦状態または前記第１確定状態の前記選択結果が選択されたことを示す第１条件を満たす場合、当該データに対して第２確定状態の選択結果を決定する第１決定処理、を実行する第１決定ステップと、
同じデータに対してｔ１（ｔ１は、ｆ＋２ｂ＋１≦ｔ１≦ｎ−ｆ−ｂを満たす整数）以上の前記第２確定状態の前記選択結果が選択されたことを示す第２条件を満たす場合、当該データに対して第１確定状態の選択結果を決定し、前記第２条件を満たさず、かつ同じデータに対して（ｂ＋１）以上の第２確定状態の前記選択結果が選択されたことを示す第３条件を満たす場合、当該データに対して第１推薦状態の選択結果を決定する第２決定処理、を実行する第２決定ステップと、
前記第１確定状態に決定されたデータに対して処理を実行して出力結果を出力する処理ステップと、
ｔ３（ｔ３は、ｂ＋１≦ｔ３≦ｎ−ｆ−ｂを満たす整数）以上の同じ出力結果を受信した場合に、受信した出力結果が有効であると判定する判定ステップと、
を含む情報処理方法。
【請求項１５】
ｎ以上（ｎはｎ＞２ｆ＋３ｂを満たす整数、ｆは許容される最大ノード障害数を表す０以上の整数、ｂは許容される最大ビザンティン障害数を表す１以上の整数）のサーバ装置を備える情報処理システムの前記サーバ装置が備えるコンピュータを、
データに対して選択された、第１確定状態、第１推薦状態、および、第２確定状態のいずれかである選択結果を受信する受信部と、
同じデータに対してｔ２（ｔ２は（ｎ＋ｂ）／２＜ｔ２≦ｎ−ｆ−ｂを満たす整数）以上の前記第１推薦状態または前記第１確定状態の前記選択結果が選択されたことを示す第１条件を満たす場合、当該データに対して第２確定状態の選択結果を決定する第１決定処理、を実行する第１決定部と、
同じデータに対してｔ１（ｔ１は、ｆ＋２ｂ＋１≦ｔ１≦ｎ−ｆ−ｂを満たす整数）以上の前記第２確定状態の前記選択結果が選択されたことを示す第２条件を満たす場合、当該データに対して第１確定状態の選択結果を決定し、前記第２条件を満たさず、かつ同じデータに対して（ｂ＋１）以上の第２確定状態の前記選択結果が選択されたことを示す第３条件を満たす場合、当該データに対して第１推薦状態の選択結果を決定する第２決定処理、を実行する第２決定部と、
前記第１確定状態に決定されたデータに対して処理を実行して出力結果を出力する処理部、
として機能させるためのプログラム。
【国際調査報告】
2015140942.tif 000010
2015140942.tif 000011
2015140942.tif 000012
2015140942.tif 000013