(57)【要約】  整列装置は、ラウンド管理部と、第１予備選挙部と、信任選挙部とを備える。第１予備選挙部は、プライマリのコンピュータから、順序番号が現在の順序番号と同一、ラウンド番号が現在のラウンド番号と同一、および、選択状態が推薦状態である投票を取得した第１の場合、プライマリのコンピュータから取得した投票に含まれるデータと、現在の順序番号と、現在のラウンド番号の次のラウンド番号と、当確状態とを含む投票を生成し、生成した投票を複数のコンピュータに出力し、現在のラウンド番号を次の値に進める。信任選挙部は、第１の閾値以上のコンピュータから、同一のデータについて、順序番号が現在の順序番号と同一、ラウンド番号が現在のラウンド番号と同一、および、選択状態が当確状態である投票を取得した第２の場合、第１の閾値以上のコンピュータから取得した投票に含まれるデータを、現在の順序番号で処理すべきデータとして決定する。
2016020986.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータに対して複数のコンピュータが同一の順序で同一の処理を実行する多重化システムにおける前記コンピュータに備えられ、前記複数のデータの処理順序を決定する整列装置であって、
現在の順序番号と現在のラウンド番号とを管理するラウンド管理部と、
前記複数のコンピュータのうちのプライマリのコンピュータから、順序番号が前記現在の順序番号と同一、ラウンド番号が前記現在のラウンド番号と同一、および、選択状態が推薦状態である投票を取得した第１の場合、前記プライマリのコンピュータから取得した前記投票に含まれるデータと、前記現在の順序番号と、前記現在のラウンド番号の次のラウンド番号と、当確状態とを含む投票を生成し、生成した前記投票を前記複数のコンピュータに出力し、前記現在のラウンド番号を次の値に進める第１予備選挙部と、
第１の閾値以上の前記コンピュータから、同一のデータについて、順序番号が前記現在の順序番号と同一、ラウンド番号が前記現在のラウンド番号と同一、および、選択状態が当確状態である投票を取得した第２の場合、前記第１の閾値以上の前記コンピュータから取得した前記投票に含まれるデータを、前記現在の順序番号で処理すべきデータとして決定する信任選挙部と、
を備える整列装置。
【請求項２】
第１予備選挙部により投票を生成しない場合であって、且つ、過半数以上のコンピュータから、同一のデータについて、順序番号が前記現在の順序番号と同一、ラウンド番号が前記現在のラウンド番号と同一、および、選択状態が推薦状態である投票を取得した第３の場合、前記過半数以上のコンピュータから取得した前記投票に含まれるデータと、前記現在の順序番号と、前記現在のラウンド番号の次のラウンド番号と、当確状態とを含む投票を生成し、生成した前記投票を前記複数のコンピュータに出力し、前記現在のラウンド番号を次の値に進める第２予備選挙部をさらに備える
請求項１に記載の整列装置。
【請求項３】
前記現在のラウンド番号が初期値である場合、第１のデータと、前記現在の順序番号と、前記現在のラウンド番号と、推薦状態とを含む投票を生成し、生成した投票を前記複数のコンピュータに出力する初期投票生成部をさらに備え、
前記第１のデータは、外部から受信した順序が決定されていないデータ、または、順序番号が前記現在の順序番号と同一且つラウンド番号が前記初期値である投票に含まれるデータである
請求項２に記載の整列装置。
【請求項４】
前記信任選挙部は、前記第１の閾値以上の前記コンピュータから取得した前記投票に含まれるデータと、前記現在の順序番号と、当選状態とを含む投票を生成し、生成した前記投票を前記複数のコンピュータに出力し、前記現在の順序番号を次の値に進め、前記現在のラウンド番号を初期値に戻す
請求項３に記載の整列装置。
【請求項５】
何れかの前記コンピュータから、順序番号が前記現在の順序番号と同一、および、選択状態が当選状態である投票を取得した場合、選択状態が当選状態である前記投票に含まれるデータを、前記現在の順序番号で処理すべきデータとして決定する当選処理部
をさらに備える請求項４に記載の整列装置。
【請求項６】
前記第１予備選挙部は、前記第１の場合以外であって、第２の閾値以上のコンピュータから、順序番号が前記現在の順序番号と同一およびラウンド番号が前記現在のラウンド番号と同一の投票を取得した場合、取得した前記投票のうち何れかの前記投票に含まれるデータと、前記現在の順序番号と、前記現在のラウンド番号の次のラウンド番号と、補欠状態とを含む投票を生成し、生成した投票を前記複数のコンピュータに出力し、前記現在のラウンド番号を次の値に進める
請求項１に記載の整列装置。
【請求項７】
前記信任選挙部は、前記第２の場合以外であって、第２の閾値以上のコンピュータから、順序番号が前記現在の順序番号と同一およびラウンド番号が前記現在のラウンド番号と同一の投票を取得した場合、取得した前記投票のうち何れかの前記投票に含まれるデータと、前記現在の順序番号と、前記現在のラウンド番号の次のラウンド番号と、推薦状態とを含む投票を生成し、生成した投票を他のコンピュータに出力し、前記現在のラウンド番号を次の値に進める
請求項１に記載の整列装置。
【請求項８】
前記信任選挙部は、第２の閾値以上のコンピュータから取得した前記投票に当確状態を含む投票が存在する場合には、前記当確状態を含む投票のデータを含む投票を生成する
請求項７に記載の整列装置。
【請求項９】
前記第２予備選挙部は、前記第３の場合以外であって、第２の閾値以上のコンピュータから、順序番号が前記現在の順序番号と同一およびラウンド番号が前記現在のラウンド番号と同一の投票を取得した場合、取得した前記投票のうち何れかの前記投票に含まれるデータと、前記現在の順序番号と、前記現在のラウンド番号の次のラウンド番号と、補欠状態とを含む投票を生成し、生成した投票を前記複数のコンピュータに出力し、前記現在のラウンド番号を次の値に進める
請求項２に記載の整列装置。
【請求項１０】
故障が許容されるコンピュータの個数をｆとした場合、前記第１の閾値は、ｆ＋１である
請求項１から９の何れか１項に記載の整列装置。
【請求項１１】
前記複数のコンピュータの個数をｎ、故障が許容されるコンピュータの個数をｆとした場合、前記第２の閾値は、ｎ−ｆである
請求項６から９の何れか１項に記載の整列装置。
【請求項１２】
前記現在のラウンド番号毎に、前記第１予備選挙部、前記第２予備選挙部および前記信任選挙部の何れか１つに処理を実行させる制御部をさらに備え、
前記制御部は、
前記現在のラウンド番号が、前記第１予備選挙部または前記第２予備選挙部の何れかが処理を実行した次の値の場合に、前記信任選挙部に処理を実行させ、
前記現在のラウンド番号が初期値の場合に、前記第１予備選挙部に処理を実行させる
請求項２に記載の整列装置。
【請求項１３】
前記現在のラウンド番号毎に、前記第１予備選挙部、前記第２予備選挙部および前記信任選挙部の何れか１つに処理を実行させる制御部をさらに備え、
前記制御部は、
前記現在のラウンド番号が、前記第１予備選挙部または前記第２予備選挙部の何れかが処理を実行した次の値の場合に、前記信任選挙部に処理を実行させ、
前記現在のラウンド番号が初期値の場合、および、前記信任選挙部が処理を実行しない値であって且つ予め定められた値の場合において、前記第１予備選挙部に処理を実行させる
請求項２に記載の整列装置。
【請求項１４】
前記現在の順序番号毎に、前記複数のコンピュータのうち何れか１つをプライマリのコンピュータとして特定するプライマリ特定部をさらに備える
請求項１に記載の整列装置。
【請求項１５】
前記プライマリ特定部は、前記複数のコンピュータのうち、前記現在の順序番号から予め定められた演算により特定される１つのコンピュータを、前記プライマリのコンピュータとして特定する
請求項１４に記載の整列装置。
【請求項１６】
前記現在の順序番号の次の順序番号のプライマリのコンピュータの識別値を発生する次プライマリ提案部と、
入力データに前記識別値を合成して、合成後のデータを処理対象のデータとして出力する合成部と、
処理順序が決定したデータを、入力データと識別値とに分離し、分離後の入力データを処理対象のデータとして出力する分離部と、
をさらに備え、
前記プライマリ特定部は、前記分離部により分離された識別値により識別されるコンピュータを、処理順序が決定したデータの次の順序番号における前記プライマリのコンピュータとして特定する
請求項１５に記載の整列装置。
【請求項１７】
前記次プライマリ提案部は、自身のコンピュータを識別する値を前記次の順序番号のプライマリのコンピュータの識別値として発生する
請求項１６に記載の整列装置。
【請求項１８】
前記次プライマリ提案部は、動作中であることが確認された前記コンピュータを識別する値を前記次の順序番号のプライマリのコンピュータの識別値として発生する
請求項１６に記載の整列装置。
【請求項１９】
前記次プライマリ提案部は、未処理の前記入力データの保留数が基準値以上のコンピュータを識別する値を、前記次の順序番号のプライマリのコンピュータの識別値として発生する
請求項１６に記載の整列装置。
【請求項２０】
請求項１から１９の何れか１項に記載の整列装置と、
前記整列装置により決定された順序でデータを処理するデータ処理部と、
を備えるデータ処理装置。
【請求項２１】
コンピュータを、請求項１から１９の何れか１項に記載の整列装置として機能させるためのプログラム。
【請求項２２】
複数のデータに対して複数のコンピュータが同一の順序で同一の処理を実行する多重化システムにおける前記コンピュータにおいて実行され、前記複数のコンピュータとの間で前記複数のデータを送受信して、前記複数のデータの処理順序を決定する整列方法であって、
前記コンピュータが、現在の順序番号と現在のラウンド番号とを管理し、
前記コンピュータが、前記複数のコンピュータのうちのプライマリのコンピュータから、順序番号が前記現在の順序番号と同一、ラウンド番号が前記現在のラウンド番号と同一、および、選択状態が推薦状態である投票を取得した第１の場合、前記プライマリのコンピュータから取得した前記投票に含まれるデータと、前記現在の順序番号と、前記現在のラウンド番号の次のラウンド番号と、当確状態とを含む投票を生成し、生成した前記投票を前記複数のコンピュータに出力し、前記現在のラウンド番号を次の値に進め、
前記コンピュータが、第１の閾値以上の前記コンピュータから、同一のデータについて、順序番号が前記現在の順序番号と同一、ラウンド番号が前記現在のラウンド番号と同一、および、選択状態が当確状態である投票を取得した第２の場合、前記第１の閾値以上の前記コンピュータから取得した前記投票に含まれるデータを、前記現在の順序番号で処理すべきデータとして決定する
整列方法。
【請求項２３】
複数のデータに対して複数のコンピュータが同一の順序で同一の処理を実行する多重化システムであって、
それぞれのコンピュータは、
前記複数のコンピュータとの間で前記複数のデータを送受信して、前記複数のデータの処理順序を決定する整列装置と、
前記整列装置により決定された順序でデータを処理するデータ処理部と、
を備え、
前記整列装置は、
現在の順序番号と現在のラウンド番号とを管理するラウンド管理部と、
前記複数のコンピュータのうちのプライマリのコンピュータから、順序番号が前記現在の順序番号と同一、ラウンド番号が前記現在のラウンド番号と同一、および、選択状態が推薦状態である投票を取得した第１の場合、前記プライマリのコンピュータから取得した前記投票に含まれるデータと、前記現在の順序番号と、前記現在のラウンド番号の次のラウンド番号と、当確状態とを含む投票を生成し、生成した前記投票を前記複数のコンピュータに出力し、前記現在のラウンド番号を次の値に進める第１予備選挙部と、
第１の閾値以上の前記コンピュータから、同一のデータについて、順序番号が前記現在の順序番号と同一、ラウンド番号が前記現在のラウンド番号と同一、および、選択状態が当確状態である投票を取得した第２の場合、前記第１の閾値以上の前記コンピュータから取得した前記投票に含まれるデータを、前記現在の順序番号で処理すべきデータとして決定する信任選挙部と、
を有する多重化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、整列装置、データ処理装置、プログラム、整列方法および多重化システムに関する。
【背景技術】
【０００２】
従来より、複数のコンピュータに同一の処理を重複して実行させる多重化システムが実用化されている。多重化システムでは、複数のコンピュータのうちのいずれかが障害状態となっても、他のコンピュータが処理を継続するので可用性が向上する。【０００３】
多重化システムを実現するために用いられる技術の一つとして、整列マルチキャストが知られている。整列マルチキャストは、処理対象の入力データを複数のコンピュータに分配するとともに、入力データの処理順序を決定する処理である。整列マルチキャストを実行することにより、それぞれのコンピュータが、同一の入力データを同一の順序で処理することができる。この結果、それぞれのコンピュータは、同一の出力データ列を出力することができる。【０００４】
ところで、整列マルチキャストでは、コンピュータ間で入力データを往復させながら、入力データを整列させる。整列マルチキャストにおいて、コンピュータ間でデータを送受信するための処理時間は、他の処理時間と比較して大きい。従って、多重化システムでは、整列マルチキャストにおけるコンピュータ間でのデータの往復回数が、高速化のためのボトルネックとなってしまう。【０００５】
従って、整列マルチキャストでは、コンピュータ間でデータを往復させる回数を短くすることが望ましい。例えば、ベストケースにおけるデータの往復回数を少なくすることは、整列マルチキャストを短時間で実行する上で重要である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】ZooKeeper、[online]、[平成２６年７月１２日検索]、インターネット＜URL:http://zookeeper.apache.org/doc/current/zookeeperInternals.html＞
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明が解決しようとする課題は、入力したデータに対して複数のコンピュータに同一の処理を同一の順序で実行させる多重化システムにおける、コンピュータ間でのデータの往復回数を少なくすることにある。
【課題を解決するための手段】
【０００８】
実施形態に係る整列装置は、複数のデータに対して複数のコンピュータが同一の順序で同一の処理を実行する多重化システムにおける前記コンピュータに備えられ、前記複数のデータの処理順序を決定する。前記整列装置は、ラウンド管理部と、第１予備選挙部と、信任選挙部とを備える。前記ラウンド管理部は、現在の順序番号と現在のラウンド番号とを管理する。前記第１予備選挙部は、前記複数のコンピュータのうちのプライマリのコンピュータから、順序番号が前記現在の順序番号と同一、ラウンド番号が前記現在のラウンド番号と同一、および、選択状態が推薦状態である投票を取得した第１の場合、前記プライマリのコンピュータから取得した前記投票に含まれるデータと、前記現在の順序番号と、前記現在のラウンド番号の次のラウンド番号と、当確状態とを含む投票を生成し、生成した前記投票を前記複数のコンピュータに出力し、前記現在のラウンド番号を次の値に進める。前記信任選挙部は、第１の閾値以上の前記コンピュータから、同一のデータについて、順序番号が前記現在の順序番号と同一、ラウンド番号が前記現在のラウンド番号と同一、および、選択状態が当確状態である投票を取得した第２の場合、前記第１の閾値以上の前記コンピュータから取得した前記投票に含まれるデータを、前記現在の順序番号で処理すべきデータとして決定する。
【図面の簡単な説明】
【０００９】
【図１】図１は、第１実施形態に係る多重化システム１０の構成を示す図である。
【図２】図２は、一つのサーバ装置２０から他のサーバ装置２０へと投票が送信される様子を示す図である。
【図３】図３は、サーバ装置２０の構成を示す図である。
【図４】図４は、整列装置３２の選挙部４６の処理を示すフローチャートである。
【図５】図５は、初期投票生成の処理を示すフローチャートである。
【図６】図６は、第１予備選挙の処理を示すフローチャートである。
【図７】図７は、第２予備選挙の処理を示すフローチャートである。
【図８】図８は、信任選挙の処理を示すフローチャートである。
【図９】図９は、当選処理を示すフローチャートである。
【図１０】図１０は、当選が決定されるまでのパスのうち、最も短いパスを示す図である。
【図１１】図１１は、プライマリのサーバ装置２０が故障している場合における当選が決定されるまでのパスを示す図である。
【図１２】図１２は、第２実施形態に係る多重化システム１０の構成を示す図である。
【図１３】図１３は、第３実施形態に係る整列装置３２の処理を示すフローチャートである。
【図１４】図１４は、実施形態に係るサーバ装置２０のハードウェア構成を示す図である。
【発明を実施するための形態】
【００１０】
以下、図面を参照しながら実施形態に係る多重化システムについて詳細に説明する。本実施形態に係る多重化システムは、入力データに対して複数のコンピュータ（例えば、データ処理装置として機能するサーバ装置）に同一の処理を同一の順序で実行させるシステムであって、コンピュータ間でのデータの往復回数を少なくすることを目的としている。
【００１１】
＜第１実施形態＞
図１は、第１実施形態に係る多重化システム１０の構成を示す図である。多重化システム１０は、複数のサーバ装置２０を備える。それぞれのサーバ装置２０は、ネットワークに接続されたコンピュータであって、互いにデータの送受信をすることができる。
【００１２】
サーバ装置２０は、クライアント装置等の外部の装置からデータを入力する。多重化システム１０に備えられる複数のサーバ装置２０のうち、何れのサーバ装置２０がデータを入力してもよい。
【００１３】
何れかのサーバ装置２０が入力したデータは、全てのサーバ装置２０にネットワークを介して送信される。それぞれのサーバ装置２０は、多重化システム１０が備える複数のサーバ装置２０が入力した全てのデータを取得する。そして、それぞれのサーバ装置２０は、入力したデータに対して、互いに同一の順序で同一の処理を実行する。これにより、それぞれのサーバ装置２０は、互いに同一の出力データ列を出力することができる。
【００１４】
本実施形態においては、処理対象のデータを複数のサーバ装置２０へと分配するとともに、データの処理順序を決定する処理を整列マルチキャストと呼ぶ。本実施形態に係る多重化システム１０によれば、整列マルチキャストでのサーバ装置２０間のデータの往復回数を少なくすることができる。
【００１５】
図２は、一つのサーバ装置２０から他のサーバ装置２０へと投票が送信される様子を示す図である。
【００１６】
本実施形態において、多重化システム１０は、ｎ個（ｎは２以上の整数）のサーバ装置２０を備える。また、多重化システム１０は、ｆ個のサーバ装置２０の故障を許容する。ｆは、ｎより小さい正の整数である。また、ｎ＞２ｆの関係を満たす。
【００１７】
それぞれのサーバ装置２０は、投票を生成し、生成した投票を自身および他のサーバ装置２０へと出力する。それぞれのサーバ装置２０は、投票の生成および出力を複数回繰り返して、整列マルチキャストを実行する。
【００１８】
投票は、データ、順序番号、ラウンド番号、ノード番号、および、選択状態を含む情報である。データは、何れかのサーバ装置２０が外部から入力したデータであり、多重化システム１０における処理対象である。
【００１９】
順序番号は、当該投票に含まれるデータを処理すべき順序を示す値である。順序番号は、順次に進められる値である。本実施形態においては、順序番号は、整数の値であって、１ずつインクリメントされる。
【００２０】
ラウンド番号は、当該投票に含まれる順序番号で処理すべきデータを決定するために、サーバ装置２０が実行する処理段階を表す値である。ラウンド番号は、初期値から順次に進められる値である。本実施形態においては、ラウンド番号は、整数の値であって、１つずつインクリメントされる。本実施形態においては、ラウンド番号の初期値は、１である。
【００２１】
なお、順序番号とラウンド番号との組をラウンドと呼ぶ。また、あるラウンドに対して、順序番号が同一であってラウンド番号が次の値であるラウンドのことを、次ラウンドと呼ぶ。また、ラウンド番号が初期値のラウンドのことを、初期ラウンドと呼ぶ。
【００２２】
ノード番号は、当該投票を生成したサーバ装置２０を識別するための整数値である。なお、それぞれのサーバ装置２０を識別する情報であれば、投票は、ノード番号に代えて、記号列であってもよい。
【００２３】
選択状態は、当該投票に含まれるデータを、サーバ装置２０がどのような状態で取り扱っているかを示す情報である。投票は、補欠状態、推薦状態、当確状態または当選状態の何れかを、選択状態として含む。
【００２４】
補欠状態は、当該投票に含まれるデータを、当該投票に含まれる順序番号で処理するデータの補欠の候補として挙げていることを示す。推薦状態は、当該投票に含まれるデータを、当該投票に含まれる順序番号で処理するデータの候補として推薦することを示す。当確状態は、当該投票に含まれるデータを、当該投票に含まれる順序番号で処理すべきデータとして、ほぼ確定させていることを示す。当選状態は、当該投票に含まれるデータを、当該投票に含まれる順序番号で処理すべきデータとして決定したことを示す。
【００２５】
なお、補欠状態を含む投票を補欠投票、推薦状態を含む投票を推薦投票、当確状態を含む投票を当確投票、当選状態を含む投票を当選投票と呼ぶ。
【００２６】
サーバ装置２０は、選挙と呼ぶ処理により、それぞれの順序番号のそれぞれのラウンド番号についての投票を生成する。サーバ装置２０は、１つのラウンド番号に対して、１つの投票を生成する。
【００２７】
サーバ装置２０は、選挙として、第１予備選挙、第２予備選挙および信任選挙の３つの処理を実行する。第１予備選挙および第２予備選挙を合わせて、予備選挙と呼ぶ。
【００２８】
予備選挙は、同一のラウンドにおいて複数のサーバ装置２０により生成された推薦投票を収集して、次ラウンドの当確投票または補欠投票を生成する処理である。信任選挙は、同一のラウンドにおいて複数のサーバ装置２０により生成された当確投票または補欠投票を収集して、次ラウンドの推薦投票または当選投票を生成する処理である。サーバ装置２０は、予備選挙と信任選挙とを、ラウンド毎に交互に繰り返して実行する。
【００２９】
本実施形態においては、サーバ装置２０は、ラウンド番号が奇数の場合に予備選挙を実行し、ラウンド番号が偶数の場合に信任選挙を実行する。従って、本実施形態においては、当確投票または補欠投票に含まれるラウンド番号は、偶数となり、推薦投票に含まれるラウンド番号は、奇数となる。
【００３０】
また、サーバ装置２０は、１つの順序番号に対して、１つの当選投票を生成する。サーバ装置２０は、信任選挙により当選投票を生成した場合、その順序番号で処理するデータを確定し、以後、その順序番号に関しては予備選挙も信任選挙も実行しない。本実施形態においては、当選投票には、ラウンド番号を含まない。
【００３１】
また、サーバ装置２０は、ある順序番号について、外部のクライアント装置からデータを入力した場合、または、他のサーバ装置２０から初期ラウンドの投票を取得した場合、初期投票生成処理を実行する。サーバ装置２０は、初期投票生成処理において、その順序番号についての初期ラウンドの推薦投票を生成する。サーバ装置２０は、初期投票生成処理を実行した後、初期ラウンドの第１予備選挙を実行する。
【００３２】
また、サーバ装置２０は、ある順序番号について、他のサーバ装置２０から当選投票を取得した場合、当選処理を実行する。サーバ装置２０は、当選処理において、取得した当選投票に含まれるデータを、その順序番号で処理するデータとして確定する。サーバ装置２０は、当選処理を実行した後には、以後、予備選挙も信任選挙も実行しない。
【００３３】
また、多重化システム１０は、複数のサーバ装置２０のうちの何れか１つがプライマリとして特定される。プライマリとなるサーバ装置２０は、常時固定であってもよいし、定期的に切り替わってもよい。定期的に切り替わる場合、プライマリのサーバ装置２０は、順序番号の単位では同一であり、全てのサーバ装置２０が既知でなければならない。
【００３４】
図３は、サーバ装置２０の構成を示す図である。サーバ装置２０は、データ受信部３１と、整列装置３２と、データ処理部３３と、データ送信部３４とを備える。データ受信部３１は、入力データを外部のクライアント装置からネットワークを介して受信する。
【００３５】
整列装置３２は、他のサーバ装置２０に備えられる整列装置３２と投票のやり取りをして、データ受信部３１により受信した入力データに対する整列マルチキャスト処理を実行する。すなわち、整列装置３２は、受信した入力データを他のサーバ装置２０に渡すとともに他のサーバ装置２０が受信した入力データを取得し、さらに、全てのサーバ装置２０が同一の順序でデータ処理を実行するように入力データの処理順序を決定する。
【００３６】
データ処理部３３は、整列装置３２により決定された順序で入力データを処理する。データ送信部３４は、データ処理部３３による処理済みのデータを、出力データとして外部のクライアント装置等にネットワークを介して送信する。
【００３７】
整列装置３２は、未確定データ記憶部４１と、投票受信部４２と、投票記憶部４３と、投票送信部４４と、プライマリ特定部４５と、選挙部４６と、確定データ記憶部４７とを有する。
【００３８】
未確定データ記憶部４１は、データ受信部３１が受信したデータのうち処理順序が未確定のデータを記憶する。
【００３９】
投票受信部４２は、他のサーバ装置２０により生成された投票をネットワークを介して受信する。投票記憶部４２は、投票受信部４２が受信した投票、および、当該サーバ装置２０自身が生成した自投票を記憶する。なお、自投票は、当該サーバ装置２０のノード番号を含む投票である。投票送信部４４は、選挙部４６が生成した自投票を、他のサーバ装置２０にネットワークを介して送信する。
【００４０】
プライマリ特定部４５は、複数のサーバ装置２０のうち何れか１つをプライマリのサーバ装置２０として特定する。本実施形態においては、プライマリ特定部４５は、特定したサーバ装置２０のノード番号を出力する。
【００４１】
プライマリ特定部４５は、一例として、選挙部４６による決定対象となっている現在の順序番号毎にプライマリのサーバ装置２０を特定する。プライマリ特定部４５は、プライマリのサーバ装置２０をそれぞれの順序番号で同一に固定してもよいし、切り替えてもよい。プライマリ特定部４５は、順序番号毎に切り替えることにより、故障したサーバ装置２０をプライマリとして特定し続けることを回避することができる。例えば、プライマリ特定部４５は、複数のサーバ装置２０のうち、現在の順序番号から予め定められた演算により特定される１つのサーバ装置２０を、プライマリのサーバ装置２０として特定する。より具体的には、例えば、プライマリ特定部４５は、順序番号を、サーバ装置２０の個数で割った余りにより特定されるノード番号のサーバ装置２０を、プライマリのサーバ装置２０として特定する。
【００４２】
選挙部４６は、未確定データ記憶部４１に記憶されたデータおよび投票記憶部４３に記憶されている投票に含まれるデータの処理順序を決定する。この場合において、選挙部４６は、初期投票生成処理、第１予備選挙、第２予備選挙、信任選挙および当選処理を実行し、自投票を決定する。選挙部４６は、処理順序が確定したデータと、処理順序を示す順序番号との組を出力する。
【００４３】
確定データ記憶部４７は、選挙部４６から出力されたデータと順序番号との組を記憶する。なお、確定データ記憶部４７にデータが格納されると、未確定データ記憶部４１に記憶された対応するデータは削除される。そして、確定データ記憶部４７は、後段のデータ処理部３３の読み出し要求に従い、順序番号に示される順序に従って、記憶しているデータをデータ処理部３３に出力する。
【００４４】
選挙部４６は、ラウンド管理部５１と、初期投票生成部５２と、第１予備選挙部５３と、第２予備選挙部５４と、信任選挙部５５と、当選処理部５６と、制御部５７とを含む。
【００４５】
ラウンド管理部５１は、選挙部４６による決定対象となっている順序番号である現在の順序番号を出力する。ラウンド管理部５１は、１ずつインクリメントされる値を、現在の順序番号として出力する。また、ラウンド管理部５１は、選挙部４６による現在の処理段階である現在のラウンド番号を出力する。ラウンド管理部５１は、初期値である１から、１ずつインクリメントされる値を、現在のラウンド番号として出力する。
【００４６】
初期投票生成部５２は、初期投票処理を実行する。より具体的には、初期投票生成部５２は、現在のラウンド番号が初期値（本実施形態では１）である場合、第１のデータと、現在の順序番号と、現在のラウンド番号と、推薦状態と、自身のサーバ装置２０のノード番号（自ノード番号）とを含む推薦投票を生成する。そして、初期投票生成部５２は、生成した推薦投票を、複数のサーバ装置２０（自身および他のサーバ装置２０の全て）に出力する。
【００４７】
なお、第１のデータは、外部から受信した順序が決定されていないデータ（未確定データ記憶部４１に記憶されているデータ）、または、投票記憶部４３に記憶されている投票のうち、順序番号が現在の順序番号と同一且つラウンド番号が初期値である投票に含まれるデータである。初期投票生成部５２は、外部から受信した順序が決定されていないデータ、および、順序番号が現在の順序番号と同一且つラウンド番号が初期値である投票の両方が存在する場合には、順序が決定されていないデータを優先して第１のデータとしてよい。
【００４８】
第１予備選挙部５３は、複数のサーバ装置２０のうちのプライマリのサーバ装置２０から、順序番号が現在の順序番号と同一、ラウンド番号が現在のラウンド番号と同一、および、選択状態が推薦状態である投票（推薦投票）を取得したかを判断する。第１予備選挙部５３は、該当する場合（第１の場合）、プライマリのサーバ装置２０から取得した推薦投票に含まれるデータと、現在の順序番号と、現在のラウンド番号の次のラウンド番号と、当確状態と、自ノード番号とを含む投票（当確投票）を生成する。そして、第１予備選挙部５３は、生成した当確投票を複数のサーバ装置２０（自身および他のサーバ装置２０の全て）に出力し、ラウンド管理部５１から出力される現在のラウンド番号を次の値に進める。
【００４９】
また、第１予備選挙部５３は、第１の場合以外であって、ｎ−ｆ個（第２の閾値）以上のサーバ装置２０から、順序番号が現在の順序番号と同一およびラウンド番号が現在のラウンド番号と同一の投票を取得したかを判断する。なお、ｎは、複数のサーバ装置２０の個数、ｆは、故障が許容されるサーバ装置２０の個数である。第１予備選挙部５３は、該当する場合には、取得した投票のうち何れかの投票に含まれるデータと、現在の順序番号と、現在のラウンド番号の次のラウンド番号と、補欠状態と、自ノード番号とを含む投票（補欠投票）を生成する。そして、第１予備選挙部５３は、生成した補欠投票を複数のサーバ装置２０（自身および他のサーバ装置２０の全て）に出力し、ラウンド管理部５１から出力される現在のラウンド番号を次の値に進める。
【００５０】
第２予備選挙部５４は、第１予備選挙部５３により投票を生成しない場合であって、且つ、過半数以上のサーバ装置２０から、同一のデータについて、順序番号が現在の順序番号と同一、ラウンド番号が現在のラウンド番号と同一、および、選択状態が推薦状態である投票（推薦投票）を取得したかを判断する。第２予備選挙部５４は、該当する場合（第３の場合）、過半数以上のサーバ装置２０から取得した推薦投票に含まれるデータと、現在の順序番号と、現在のラウンド番号の次のラウンド番号と、当確状態と、自ノード番号とを含む投票（当確投票）を生成する。そして、第２予備選挙部５４は、生成した当確投票を複数のサーバ装置２０（自身および他のサーバ装置２０の全て）に出力し、ラウンド管理部５１から出力される現在のラウンド番号を次の値に進める。
【００５１】
また、第２予備選挙部５４は、第３の場合以外であって、ｎ−ｆ個（第２の閾値）以上のサーバ装置２０から、順序番号が現在の順序番号と同一およびラウンド番号が現在のラウンド番号と同一の投票を取得したかを判断する。第２予備選挙部５４は、該当する場合、取得した投票のうち何れかの投票に含まれるデータと、現在の順序番号と、現在のラウンド番号の次のラウンド番号と、補欠状態と、自ノード番号とを含む投票（補欠投票）を生成する。そして、第２予備選挙部５４は、生成した補欠投票を複数のサーバ装置２０（自身および他のサーバ装置２０の全て）に出力し、ラウンド管理部５１から出力される現在のラウンド番号を次の値に進める。
【００５２】
信任選挙部５５は、ｆ＋１個（第１の閾値）以上のサーバ装置２０から、同一のデータについて、順序番号が現在の順序番号と同一、ラウンド番号が現在のラウンド番号と同一、および、選択状態が当確状態である投票（当確投票）を取得したかを判断する。信任選挙部５５は、該当する場合（第２の場合）、ｆ＋１個（第１の閾値）以上のサーバ装置２０から取得した当確投票に含まれるデータを、現在の順序番号で処理すべきデータとして決定する。そして、信任選挙部５５は、決定したデータと現在の順序番号との組を確定データ記憶部４７へと出力する。
【００５３】
さらに、信任選挙部５５は、ｆ＋１個（第１の閾値）以上のサーバ装置２０から取得した当確投票に含まれるデータと、現在の順序番号と、当選状態と、自ノード番号とを含む投票（当選投票）を生成する。そして、信任選挙部５５は、生成した当選投票を他のサーバ装置２０に出力し、ラウンド管理部５１から出力される現在の順序番号を次の値に進め、現在のラウンド番号を初期値に戻す。
【００５４】
また、信任選挙部５５は、第２の場合以外であって、ｎ−ｆ個（第２の閾値）以上のサーバ装置２０から、順序番号が現在の順序番号と同一およびラウンド番号が現在のラウンド番号と同一の投票を取得したかを判断する。信任選挙部５５は、該当する場合、取得した投票のうち何れかの投票に含まれるデータと、現在の順序番号と、現在のラウンド番号の次のラウンド番号と、推薦状態と、自ノード番号とを含む投票（推薦投票）を生成する。なお、信任選挙部５５は、ｎ−ｆ個（第２の閾値）以上のサーバ装置２０から取得した投票に当確投票が存在する場合には、この当確投票のデータを含む推薦投票を生成してもよい。そして、信任選挙部５５は、生成した推薦投票を複数のサーバ装置２０（自身および他のサーバ装置２０の全て）に出力し、ラウンド管理部５１から出力される現在のラウンド番号を次の値に進める。
【００５５】
当選処理部５６は、何れかのサーバ装置２０から、順序番号が現在の順序番号と同一、および、選択状態が当選状態である当選投票を取得した場合、選択状態が当選状態である当選投票に含まれるデータを、現在の順序番号で処理すべきデータとして決定する。そして、当選処理部５６は、決定したデータと現在の順序番号との組を確定データ記憶部４７へと出力する。さらに、当選処理部５６は、ラウンド管理部５１から出力される現在の順序番号を次の値に進め、現在のラウンド番号を初期値に戻す。なお、当選処理部５６は、現在の順序番号の当選投票を生成していない場合には、他のサーバ装置２０から取得した当選投票に含まれるデータと、現在の順序番号と、当選状態と、自ノード番号とを含む当選投票を生成し、生成した当選投票を他のサーバ装置２０に出力してもよい。
【００５６】
制御部５７は、現在のラウンド番号毎に、第１予備選挙部５３、第２予備選挙部５４および信任選挙部５５の何れか１つに処理を実行させる。制御部５７は、現在のラウンド番号が初期値の場合に、第１予備選挙部５３に処理を実行させる。また、制御部５７は、現在のラウンド番号が、第１予備選挙部５３または第２予備選挙部５４が処理を実行した次の値の場合に、信任選挙部５５に処理を実行させる。また、制御部５７は、現在のラウンド番号が、信任選挙部５５が処理を実行した次の値であって、且つ、第１予備選挙部５３が処理を実行しない場合に、第２予備選挙部５４に処理を実行させる。
【００５７】
例えば、ラウンド番号の初期値が１で、ラウンド番号が１ずつインクリメントされる場合には、制御部５７は、ラウンド番号が１の場合に第１予備選挙部５３に処理を実行させ、ラウンド番号が偶数の場合に信任選挙部５５に処理を実行させる。また、制御部５７は、ラウンド番号が、１以外の奇数である場合には、第２予備選挙部５４に処理を実行させる。
【００５８】
また、制御部５７は、現在のラウンド番号が初期値の場合には、第１予備選挙部５３の実行に先だって、初期投票生成部５２に処理を実行させる。また、制御部５７は、何れかのサーバ装置２０から、順序番号が現在の順序番号と同一、および、選択状態が当選状態である当選投票を取得した場合、ラウンド番号に関わらず、優先して、当選処理部５６に処理を実行させる。
【００５９】
図４は、整列装置３２の選挙部４６の処理を示すフローチャートである。整列装置３２の選挙部４６は、クライアント装置からデータを受信したことにより未確定データ記憶部４１の記憶内容が変化した場合、または、他のサーバ装置２０から投票を受信したことにより投票記憶部４３の記憶内容が変化した場合に、ステップＳ１１から処理を開始する。
【００６０】
まず、ステップＳ１１において、選挙部４６の制御部５７は、順序番号が現在の順序番号と同一の当選投票が投票記憶部４３にあるか否かを判断する。制御部５７は、ある場合には（Ｓ１１のＹｅｓ）、処理をステップＳ１９に進め、無い場合には（Ｓ１１のＮｏ）、処理をステップＳ１２に進める。
【００６１】
ステップＳ１２において、制御部５７は、現在のラウンド番号が１であるか（すなわち、初期値であるか）否かを判断する。制御部５７は、現在のラウンド番号が１である場合には（Ｓ１２のＹｅｓ）、処理をステップＳ１３に進め、現在のラウンド番号が１ではない場合には（Ｓ１２のＮｏ）、処理をステップＳ１６に進める。
【００６２】
ステップＳ１３において、制御部５７は、現在の順序番号の初期ラウンド（ラウンド番号が１）の自投票を生成したか否かを判断する。制御部５７は、自投票を生成していない場合には（Ｓ１３のＮｏ）、処理をステップＳ１４に進め、自投票を生成した場合には（Ｓ１３のＹｅｓ）、処理をステップＳ１５に進める。
【００６３】
ステップＳ１４において、制御部５７は、初期投票生成部５２を呼び出し、初期投票生成処理を実行させる。初期投票生成処理については、図５を参照してさらに説明する。制御部５７は、初期投票生成処理が終了して処理が戻ると、処理をステップＳ１５に進める。
【００６４】
ステップＳ１５において、制御部５７は、第１予備選挙部５３を呼び出し、第１予備選挙を実行させる。第１予備選挙については、図６を参照してさらに説明する。そして、制御部５７は、第１予備選挙が終了して処理が戻ると、処理をステップＳ１１に戻す。
【００６５】
また、ステップＳ１６において、制御部５７は、現在のラウンド番号が奇数か否かを判断する。制御部５７は、現在のラウンド番号が奇数の場合（Ｓ１６のＹｅｓ）、処理をステップＳ１７に進め、現在のラウンド番号が奇数でない場合（偶数の場合）（Ｓ１６のＮｏ）、処理をステップＳ１８に進める。
【００６６】
ステップＳ１７において、制御部５７は、第２予備選挙部５４を呼び出し、第２予備選挙を実行させる。第２予備選挙については、図７を参照してさらに説明する。そして、制御部５７は、第２予備選挙が終了して処理が戻ると、処理をステップＳ１１に戻す。
【００６７】
ステップＳ１８において、制御部５７は、信任選挙部５５を呼び出し、信任選挙を実行させる。信任選挙については、図８を参照してさらに説明する。そして、制御部５７は、信任選挙が終了して処理が戻ると、処理をステップＳ１１に戻す。
【００６８】
また、ステップＳ１９において、制御部５７は、当選処理部５６を呼び出し、当選処理を実行させる。当選処理については、図９を参照してさらに説明する。制御部５７は、当選処理が終了して処理が戻ると、処理をステップＳ１１に戻す。
【００６９】
図５は、初期投票生成の処理を示すフローチャートである。初期投票生成部５２は、ステップＳ１４において、制御部５７に呼び出されると、図５に示すステップＳ３１からの初期投票生成処理を実行する。
【００７０】
まず、ステップＳ３１において、初期投票生成部５２は、未確定データ記憶部４１にデータがあるか否かを判断する。初期投票生成部５２は、データがある場合（Ｓ３１のＹｅｓ）、処理をステップＳ３３に進め、データが無い場合（Ｓ３１のＮｏ）、処理をステップＳ３２に進める。
【００７１】
ステップＳ３２において、初期投票生成部５２は、投票記憶部４３に、順序番号が現在の順序番号と同一且つラウンド番号が初期値である投票があるか否かを判断する。初期投票生成部５２は、該当する投票がある場合（Ｓ３２のＹｅｓ）、処理をステップＳ３３に進める。該当する投票が無い場合（Ｓ３２のＮｏ）、初期投票生成部５２は、処理を制御部５７に戻し、制御部５７は、図４に示す全体の処理フローを終了する。
【００７２】
ステップＳ３３において、初期投票生成部５２は、第１のデータと、現在の順序番号と、現在のラウンド番号と、推薦状態と、自身のサーバ装置２０のノード番号（自ノード番号）とを含む推薦投票を生成する。ここで、第１のデータは、未確定データ記憶部４１に記憶されているデータ、または、順序番号が現在の順序番号と同一且つラウンド番号が初期値である投票に含まれるデータである。
【００７３】
続いて、ステップＳ３４において、初期投票生成部５２は、ステップＳ３３で生成した推薦投票を、複数のサーバ装置２０（自身および他のサーバ装置２０の全て）に出力する。初期投票生成部５２は、ステップＳ３４を終了すると、初期投票生成処理を終了して、処理を制御部５７に戻す。
【００７４】
図６は、第１予備選挙の処理を示すフローチャートである。第１予備選挙部５３は、ステップＳ１５において、制御部５７に呼び出されると、図６に示すステップＳ４１からの第１予備選挙を実行する。
【００７５】
まず、ステップＳ４１において、第１予備選挙部５３は、投票記憶部４３に、ノード番号がプライマリのサーバ装置２０のノード番号、順序番号が現在の順序番号と同一、ラウンド番号が現在のラウンド番号と同一、および、選択状態が推薦状態である投票（推薦投票）があるか否かを判断する。第１予備選挙部５３は、該当する推薦投票がある場合（Ｓ４１のＹｅｓ）、処理をステップＳ４２に進め、該当する推薦投票が無い場合（Ｓ４１のＮｏ）、処理をステップＳ４４に進める。
【００７６】
ステップＳ４２において、第１予備選挙部５３は、プライマリのサーバ装置２０から取得した推薦投票に含まれるデータと、現在の順序番号と、現在のラウンド番号の次のラウンド番号と、当確状態と、自ノード番号とを含む当確投票を生成する。続いて、ステップＳ４３において、第１予備選挙部５３は、生成した当確投票を複数のサーバ装置２０（自身および他のサーバ装置２０の全て）に出力する。第１予備選挙部５３は、ステップＳ４３を終了すると、処理をステップＳ４７に進める。
【００７７】
ステップＳ４４において、第１予備選挙部５３は、投票記憶部４３に、順序番号が現在の順序番号と同一およびラウンド番号が現在のラウンド番号と同一の投票が、ｎ−ｆ個（第２の閾値）以上あるか否かを判断する。第１予備選挙部５３は、ｎ−ｆ個以上の該当する投票がある場合（Ｓ４４のＹｅｓ）、処理をステップＳ４５に進める。ｎ−ｆ個以上の該当する投票が無い場合（Ｓ４４のＮｏ）、第１予備選挙部５３は、処理を制御部５７に戻し、制御部５７は、図４に示す全体の処理フローを終了する。
【００７８】
ステップＳ４５において、第１予備選挙部５３は、ｎ−ｆ個以上の該当する投票のうち何れかの投票に含まれるデータと、現在の順序番号と、現在のラウンド番号の次のラウンド番号と、補欠状態と、自ノード番号とを含む投票（補欠投票）を生成する。続いて、ステップＳ４６において、第１予備選挙部５３は、生成した補欠投票を複数のサーバ装置２０（自身および他のサーバ装置２０の全て）に出力する。第１予備選挙部５３は、ステップＳ４６を終了すると、処理をステップＳ４７に進める。
【００７９】
ステップＳ４７において、第１予備選挙部５３は、ラウンド管理部５１から出力される現在のラウンド番号を１進めて、次の値にする。第１予備選挙部５３は、ステップＳ４７を終了すると、第１予備選挙を終了して、処理を制御部５７に戻す。
【００８０】
図７は、第２予備選挙の処理を示すフローチャートである。第２予備選挙部５４は、ステップＳ１７において、制御部５７に呼び出されると、図７に示すステップＳ５１からの第２予備選挙を実行する。
【００８１】
まず、ステップＳ５１において、第２予備選挙部５４は、投票記憶部４３に、順序番号が現在の順序番号と同一、ラウンド番号が現在のラウンド番号と同一、および、選択状態が推薦状態である、同一のデータについての推薦投票が、ｎの過半数以上あるか否かを判断する。第２予備選挙部５４は、該当する推薦投票がｎの過半数以上ある場合（Ｓ５１のＹｅｓ）、処理をステップＳ５２に進め、該当する推薦投票がｎの過半数以上は無い場合（Ｓ５１のＮｏ）、処理をステップＳ５４に進める。
【００８２】
ステップＳ５２において、第２予備選挙部５４は、ｎの過半数以上取得した推薦投票に含まれるデータと、現在の順序番号と、現在のラウンド番号の次のラウンド番号と、当確状態と、自ノード番号とを含む投票（当確投票）を生成する。続いて、ステップＳ５３において、生成した当確投票を複数のサーバ装置２０（自身および他のサーバ装置２０の全て）に出力する。第２予備選挙部５４は、ステップＳ５３を終了すると、処理をステップＳ５７に進める。
【００８３】
ステップＳ５４において、第２予備選挙部５４は、投票記憶部４３に、順序番号が現在の順序番号と同一およびラウンド番号が現在のラウンド番号と同一の投票が、ｎ−ｆ個（第２の閾値）以上あるか否かを判断する。第２予備選挙部５４は、ｎ−ｆ個以上の該当する投票がある場合（Ｓ５４のＹｅｓ）、処理をステップＳ５５に進める。ｎ−ｆ個以上の該当する投票が無い場合（Ｓ５４のＮｏ）、第２予備選挙部５４は、処理を制御部５７に戻し、制御部５７は、図４に示す全体の処理フローを終了する。
【００８４】
ステップＳ５５において、第２予備選挙部５４は、ｎ−ｆ個以上の該当する投票のうち何れかの投票に含まれるデータと、現在の順序番号と、現在のラウンド番号の次のラウンド番号と、補欠状態と、自ノード番号とを含む補欠投票を生成する。続いて、ステップＳ５６において、第２予備選挙部５４は、生成した補欠投票を複数のサーバ装置２０（自身および他のサーバ装置２０の全て）に出力する。第２予備選挙部５４は、ステップＳ５６を終了すると、処理をステップＳ５７に進める。
【００８５】
ステップＳ５７において、第２予備選挙部５４は、ラウンド管理部５１から出力される現在のラウンド番号を１進めて、次の値にする。第２予備選挙部５４は、ステップＳ５７を終了すると、第２予備選挙を終了して、処理を制御部５７に戻す。
【００８６】
図８は、信任選挙の処理を示すフローチャートである。信任選挙部５５は、ステップＳ１８において、制御部５７に呼び出されると、図８に示すステップＳ６１からの信任選挙を実行する。
【００８７】
まず、ステップＳ６１において、信任選挙部５５は、順序番号が現在の順序番号と同一、ラウンド番号が現在のラウンド番号と同一、および、選択状態が当確状態である、同一のデータについての当確投票が、ｆ＋１個（第１の閾値）以上あるか否かを判断する。信任選挙部５５は、該当する当確投票がｆ＋１個以上ある場合（Ｓ６１のＹｅｓ）、処理をステップＳ６２に進め、該当する当確投票がｆ＋１個以上は無い場合（Ｓ６１のＮｏ）、処理をステップＳ６７に進める。
【００８８】
続いて、ステップＳ６２において、信任選挙部５５は、ｆ＋１個以上の当確投票に含まれるデータと、現在の順序番号と、当選状態と、自ノード番号とを含む当選投票を生成する。続いて、ステップＳ６３において、信任選挙部５５は、生成した当選投票を他のサーバ装置２０に出力する。
【００８９】
続いて、ステップＳ６４において、信任選挙部５５は、ｆ＋１個以上の当確投票に含まれるデータを、現在の順序番号で処理すべきデータとして決定する。さらに、信任選挙部５５は、決定したデータと現在の順序番号との組を確定データ記憶部４７へと出力する。
【００９０】
続いて、ステップＳ６５において、信任選挙部５５は、ラウンド管理部５１から出力される現在の順序番号を次の値に進める。続いて、ステップＳ６６において、信任選挙部５５は、現在のラウンド番号を初期値である１に戻す。信任選挙部５５は、ステップＳ６６を終了すると、信任選挙を終了して、処理を制御部５７に戻す。
【００９１】
ステップＳ６７において、信任選挙部５５は、投票記憶部４３に、順序番号が現在の順序番号と同一およびラウンド番号が現在のラウンド番号と同一の投票が、ｎ−ｆ個（第２の閾値）以上あるか否かを判断する。信任選挙部５５は、ｎ−ｆ個以上の該当する投票がある場合（Ｓ６７のＹｅｓ）、処理をステップＳ６８に進める。ｎ−ｆ個以上の該当する投票が無い場合（Ｓ６７のＮｏ）、信任選挙部５５は、処理を制御部５７に戻し、制御部５７は、図４に示す全体の処理フローを終了する。
【００９２】
ステップＳ６８において、信任選挙部５５は、ｎ−ｆ個以上の該当する投票の中に、当確投票があるか否かを判断する。信任選挙部５５は、当確投票がある場合（Ｓ６８のＹｅｓ）、処理をステップＳ６９に進め、当確投票が無い場合（Ｓ６８のＮｏ）、処理をステップＳ７０に進める。
【００９３】
ステップＳ６９において、信任選挙部５５は、当確投票に含まれるデータと、現在の順序番号と、現在のラウンド番号の次のラウンド番号と、推薦状態と、自ノード番号とを含む推薦投票を生成する。また、ステップＳ７０において、信任選挙部５５は、ｎ−ｆ個以上の該当する投票のうち何れかの投票に含まれるデータと、現在の順序番号と、現在のラウンド番号の次のラウンド番号と、推薦状態と、自ノード番号とを含む推薦投票を生成する。ステップＳ６９またはステップＳ７０の処理を終えると、信任選挙部５５は、処理をステップＳ７１に進める。
【００９４】
ステップＳ７１において、信任選挙部５５は、ステップＳ６９またはステップＳ７０で生成した推薦投票を、複数のサーバ装置２０（自身および他のサーバ装置２０の全て）に出力する。続いて、ステップＳ７２において、信任選挙部５５は、ラウンド管理部５１から出力される現在のラウンド番号を１進めて、次の値にする。信任選挙部５５は、ステップＳ７２を終了すると、信任選挙を終了して、処理を制御部５７に戻す。
【００９５】
図９は、当選処理を示すフローチャートである。当選処理部５６は、ステップＳ１９において、制御部５７に呼び出されると、図９に示すステップＳ８１からの当選処理を実行する。
【００９６】
まず、ステップＳ８１において、当選処理部５６は、取得した当確投票に含まれるデータを、現在の順序番号で処理すべきデータとして決定する。さらに、当選処理部５６は、決定したデータと現在の順序番号との組を確定データ記憶部４７へと出力する。
【００９７】
続いて、ステップＳ８２において、当選処理部５６は、ラウンド管理部５１から出力される現在の順序番号を次の値に進める。続いて、ステップＳ８３において、当選処理部５６は、現在のラウンド番号を初期値である１に戻す。当選処理部５６は、ステップＳ８３を終了すると、当選処理を終了して、処理を制御部５７に戻す。
【００９８】
＜多重化システム１０の効果＞
以上のような本実施形態に係る多重化システム１０によれば、入力したデータに対して複数のサーバ装置２０に同一の処理を同一の順序で実行させることができる。さらに、本実施形態に係る多重化システム１０によれば、サーバ装置２０の間でデータを往復させる回数を少なくすることができる。例えば、多重化システム１０によれば、ある順序番号に実行すべきデータを決定するために、ベストケースにおいて、サーバ装置２０のデータのやり取りを１往復で完了させることができる。
【００９９】
図１０は、当選が決定されるまでのパスのうち、最も短いパスを示す図である。多重化システム１０において、データが入力されてから当選投票が生成されるまでの、最も短いパスは、図１０に示す通りである。
【０１００】
すなわち、まず、第１プロセスにおいて、プライマリのサーバ装置２０は、入力データを受け付け、初期ラウンドの推薦投票を生成する（初期投票生成）。続いて、第２プロセスにおいて、プライマリのサーバ装置２０は、初期ラウンドの推薦投票を全てのサーバ装置２０に送信する。続いて、第３プロセスにおいて、それぞれのサーバ装置２０は、プライマリのサーバ装置２０からの初期ラウンドの推薦投票を受信して、第２ラウンドの当確投票を生成する（第１予備選挙）。続いて、第４プロセスにおいて、それぞれのサーバ装置２０は、第２ラウンドの当確投票を全てのサーバ装置２０に送信する。そして、第５プロセスにおいて、それぞれのサーバ装置２０は、ｆ＋１以上の第２ラウンドの当確投票を受信して、当選投票を生成する（信任選挙）。
【０１０１】
このパスの場合、多重化システム１０は、第２プロセスおよび第４プロセスで投票を送信する。すなわち、多重化システム１０は、最も短いパス（ベストケース）では、１往復分の投票の送信で処理が完了する。
【０１０２】
ここで、仮に第１予備選挙を実行しなかった場合における、当選投票が生成されるまでの処理を検討する。この場合、データが入力されてから当選投票が生成されるまでの、最も短いパスは次のとおりである。
【０１０３】
まず、第１プロセスにおいて、プライマリのサーバ装置２０は、入力データを受け付け、初期ラウンドの推薦投票を生成する（初期投票生成）。続いて、第２プロセスにおいて、プライマリのサーバ装置２０は、初期ラウンドの推薦投票を全てのサーバ装置２０に送信する。続いて、第３プロセスにおいて、それぞれのサーバ装置２０は、プライマリのサーバ装置２０からの推薦投票を受信して、初期ラウンドの推薦投票を生成する（初期投票生成）。続いて、第４プロセスにおいて、それぞれのサーバ装置２０は、初期ラウンドの推薦投票を全てのサーバ装置２０に送信する。
【０１０４】
続いて、第５プロセスにおいて、それぞれのサーバ装置２０は、過半数以上の初期ラウンドの推薦投票を受信して、第２ラウンドの当確投票を生成する（第２予備選挙）。続いて、第６プロセスにおいて、それぞれのサーバ装置２０は、第２ラウンドの当確投票を全てのサーバ装置２０に送信する。そして、第７プロセスにおいて、それぞれのサーバ装置２０は、ｆ＋１以上の第２ラウンドの当確投票を受信して、当選投票を生成する（信任選挙）。
【０１０５】
第１予備選挙を実行しない場合、多重化システム１０は、第２プロセス、第４プロセスおよび第６プロセスで投票を送信する。すなわち、多重化システム１０は、第１予備選挙を実行しない場合、１．５往復分の投票を送信しなければならない。
【０１０６】
このように本実施形態に係る多重化システム１０は、それぞれのサーバ装置２０が、第１予備選挙を実行することにより、プライマリのサーバ装置２０から推薦投票を受信した場合、その推薦投票に含まれるデータを含む当確投票を生成することができる。これにより、本実施形態に係る多重化システム１０によれば、当選投票が生成されるまでの最も短いパスでの投票の送信回数を１往復分とし、整列マルチキャリアにおけるボトルネックの影響を小さくすることができる。
【０１０７】
図１１は、プライマリのサーバ装置２０が故障している場合における当選が決定されるまでのパスを示す図である。
【０１０８】
多重化システム１０は、最大でｆ（ｆは２ｆ＜ｎを満たす整数）個までのサーバ装置２０の障害を許容する。また、多重化システム１０は、何れかのサーバ装置２０に障害が発生しても処理が中断しないというノンブロッキング性を有する。
【０１０９】
さらに、多重化システム１０におけるプライマリのサーバ装置２０は、プロトコルの調停のような、他とは異なる固有の機能を有さなくてよい。従って、多重化システム１０は、プライマリのサーバ装置２０に障害が発生した場合にも、ノンブロッキング性を満たす。つまり、多重化システム１０は、プライマリのサーバ装置２０が停止した場合にも、ｎ−ｆ個のサーバ装置２０が動作していれば、動作を継続することができる。
【０１１０】
多重化システム１０において、プライマリのサーバ装置２０の動作が停止した場合における、データが入力されてから当選投票が生成されるまでの、最も短いパスは、図１１に示すとおりである。
【０１１１】
すなわち、まず、第１プロセスにおいて、プライマリではない第１のサーバ装置２０は、入力データを受け付け、初期ラウンドの推薦投票を生成する（初期投票生成）。続いて、第２プロセスにおいて、第１のサーバ装置２０は、初期ラウンドの推薦投票を、故障のプライマリのサーバ装置２０を除く全てのサーバ装置２０に送信する。続いて、第３プロセスにおいて、それぞれのサーバ装置２０は、第１のサーバ装置２０からの推薦投票を受信して、初期ラウンドの推薦投票を生成する（初期投票生成）。続いて、第４プロセスにおいて、それぞれのサーバ装置２０は、初期ラウンドの推薦投票を、故障のプライマリのサーバ装置２０を除く全てのサーバ装置２０に送信する。
【０１１２】
続いて、第５プロセスにおいて、それぞれのサーバ装置２０は、ｎ−ｆ以上の初期ラウンドの投票を受信して、第２ラウンドの補欠投票を生成する（第１予備選挙）。続いて、第６プロセスにおいて、それぞれのサーバ装置２０は、第２ラウンドの補欠投票を、故障のプライマリのサーバ装置２０を除く全てのサーバ装置２０に送信する。
【０１１３】
続いて、第７プロセスにおいて、それぞれのサーバ装置２０は、ｎ−ｆ以上の第２ラウンドの投票を受信して、第３ラウンドの推薦投票を生成する（信任選挙）。続いて、第８プロセスにおいて、それぞれのサーバ装置２０は、第３ラウンドの推薦投票を、故障のプライマリのサーバ装置２０を除く全てのサーバ装置２０に送信する。
【０１１４】
続いて、第９プロセスにおいて、それぞれのサーバ装置２０は、過半数以上の第３ラウンドの推薦投票を受信して、第４ラウンドの当確投票を生成する（第２予備選挙）。続いて、第１０プロセスにおいて、それぞれのサーバ装置２０は、第４ラウンドの当確投票を、故障のプライマリのサーバ装置２０を除く全てのサーバ装置２０に送信する。
【０１１５】
そして、第１１プロセスにおいて、それぞれのサーバ装置２０は、ｆ＋１以上の第４ラウンドの当確投票を受信して、当選投票を生成する（信任選挙）。
【０１１６】
プライマリのサーバ装置２０が故障している場合、多重化システム１０は、第２プロセス、第４プロセス、第６プロセス、第８プロセスおよび第１０プロセスで投票を送信する。すなわち、多重化システム１０は、プライマリのサーバ装置２０が故障している場合、２．５往復分の投票を送信する。しかし、多重化システム１０は、プライマリのサーバ装置２０が故障していても、整列マルチキャストを実行することができる。
【０１１７】
以上のように、多重化システム１０は、プライマリのサーバ装置２０が動作していない場合でも、動作は中断しない。従って、多重化システム１０は、プライマリのサーバ装置２０が故障しても、他のサーバ装置２０にプライマリの機能を切り替えなくてもよい。
【０１１８】
＜アルゴリズムの正当性の証明＞
以下、多重化システム１０において、整列マルチキャストの一貫性が保たれることの正当性について証明する。以下の証明では、投票に含まれる入力データを投票の値とも呼ぶ。また、「＃」は、集合の要素数を表す記号である。また、「∩」は集合の共通部分を表す記号である。
【０１１９】
（補題１）同一ラウンドの当確投票の値は全て等しい。
［証明］
ラウンドｒの当確投票の値が互いに等しいことを証明すればよい。当確投票は第１予備選挙か、第２予備選挙のどちらかで決定する。それぞれの場合に分けて証明する。
【０１２０】
ラウンドｒの当確投票が第１予備選挙で決定した場合、第１予備選挙の定義より、ラウンドｒの当確投票の値は、プライマリのサーバ装置２０のラウンドｒ−１の推薦投票の値と等しい。プライマリのサーバ装置２０はひとつしかないから、そのラウンドｒ−１の推薦投票の値は唯一である。従って、ラウンドｒの当確投票の値は互いに等しい。
【０１２１】
ラウンドｒの当確投票が第２予備選挙で決定した場合、第２予備選挙の定義より、ラウンドｒの当確投票の値は、ｎの過半数以上の同じ値の推薦投票を集めたうえで、その値に決定している。ラウンドｒ−１の推薦投票は最大でｎしかないから、その過半数を同じ値が占めているとしたら、その値は唯一である。従ってラウンドｒの当確投票の値は互いに等しい。
［証明終］
【０１２２】
（補題２）同一ラウンドの信任選挙で決定する当選投票の値は全て等しい。
［証明］
信任選挙で当選投票が決定するとき、ｆ＋１以上の同じ値の当確投票を集めたうえで、その値に決定している。従って、当選投票の値は、信任選挙で用いる当確投票の値と等しい。ここで補題１より、同じラウンドの当確投票の値は全て等しいから、そのラウンドから信任選挙で決まる当選投票の値は全て等しい。
［証明終］
【０１２３】
（補題３）当選投票ｘが信任選挙で決定したならば、それと同じラウンドの信任選挙で決定する推薦投票の値は、ｘの値と等しい。
［証明］
それと同じラウンドの信任選挙で決定する推薦投票をｙとする。このときｘとｙの値が等しいことを証明すればよい。
【０１２４】
ｘを決定した信任選挙で用いた投票のうち、ｘと同じ値の当確投票の集合をＥｘとする。一方、ｙを決定した信任選挙で用いた投票の集合をＥｙとする。ＥｘとＥｙに含まれる投票のラウンドは全て等しい。アルゴリズムの定義より、
＃（Ｅｘ）≧ｆ＋１
＃（Ｅｙ）≧ｎ−ｆ
である。従って、
＃（Ｅｘ∩Ｅｙ）≧＃（Ｅｘ）＋＃（Ｅｙ）−ｎ≧１
である。
【０１２５】
すなわち、ＥｘとＥｙには共通の投票がある。従って、Ｅｙの中に当確投票があることになる。すると、信任選挙の定義より、ｙはランダムに選ばれた値ではなく、ｘと同じ値の推薦投票でなければならない。
［証明終］
【０１２６】
（補題４）当選投票ｘが信任選挙で決定したならば、その２つ後のラウンドの信任選挙で決まる投票は当選投票で、その値はｘの値と等しい。
［証明］
まず、ｘが決定した信任選挙の次の予備選挙を考える。このラウンドは初期ラウンドではないから、この予備選挙は第２予備選挙である。その第２予備選挙でｎ−ｆの推薦投票を収集した時、補題３よりその推薦投票の値は全てｘの値と等しく、ｎ−ｆはｎの過半数以上であるから、過半数以上のｘと同じ値の推薦投票をすでに集めていることになる。従って、第２予備選挙の定義より、その予備選挙の結果は全て当確投票となり、その値はｘの値と等しい。
【０１２７】
そうすると、その次の信任選挙でｎ−ｆの投票を収集した時、それらは全てｘと同じ値の当確投票であり、ｎ−ｆ≧ｆ＋１であるから、ｆ＋１以上のｘと同じ値の当確投票を集めていることになる。従って、信任選挙の定義より、信任選挙の結果は全て当選投票となり、その値はｘの値と等しい。
［証明終］
【０１２８】
補題２と補題４から、当選投票はラウンドが異なっているとしても全て同じ値であることがわかる。すなわち、最初に当選投票となったラウンドをｒとすると、ラウンドｒ＋２までには全ての投票はそれと同じ値の当選投票となる。
【０１２９】
これにより本実施形態の多重化システム１０は、多重化の一貫性が保証されていることが証明された。
【０１３０】
最後に、本実施形態の多重化システム１０が、障害の発生時にタイムアウトによる処理の中断が発生しない点（リアルタイム性）について説明する。
【０１３１】
本実施形態の多重化システム１０は、当選投票が得られるまで、ｎ−ｆの投票が収集できるかぎりラウンドが進んでいく。このとき、どのサーバ装置２０がどのような障害となっているかについて全く関知していない。従って、サーバ装置２０の障害数がｆ以下であれば、どのようなタイミングで障害が発生したとしても、少なくともｎ−ｆの投票は必ず収集できるから、ラウンドが進んでいく。
【０１３２】
＜第２実施形態＞
図１２は、第２実施形態に係る多重化システム１０の構成を示す図である。第２実施形態に係る多重化システム１０は、図１〜図１１を参照して説明した第１実施形態と略同一の機能および構成を有するので、略同一の機能を有する部材には同一の符号を付けて説明を省略する。
【０１３３】
第２実施形態に係る整列装置３２は、次プライマリ提案部６１と、合成部６２と、分離部６３とをさらに有する。
【０１３４】
次プライマリ提案部６１は、現在の順序番号の次の順序番号のプライマリのサーバ装置２０の識別値を発生する。識別値は、例えば、サーバ装置２０のノード番号であってよい。次プライマリ提案部６１は、どのサーバ装置２０を次の順序番号のプライマリのサーバ装置２０として提案することも可能である。次プライマリ提案部６１は、提案するサーバ装置２０を順序番号毎に固定しても、順序番号毎に変更してもよい。また、提案されるサーバ装置２０の識別値は、サーバ装置２０毎に異なってもよい。
【０１３５】
合成部６２は、未確定データ記憶部４１に記憶されている入力データに、次プライマリ提案部６１から出力された識別値を合成して、合成後のデータを処理対象のデータとして選挙部４６へと出力する。この場合において、合成部６２は、入力データと識別値とを分離可能に合成する。
【０１３６】
合成部６２は、一例として、入力データと識別値とを配列のような１つのセットデータに合成してもよい。また、合成部６２は、一例として、入力データのビット列と識別値のビット列と前後に合成して、１つのデータとしてもよい。
【０１３７】
そして、選挙部４６は、入力データと識別値とを合成したデータを、処理対象のデータとして取り扱う。従って、選挙部４６は、生成する投票に、入力データと識別値とを合成したデータを含める。また、選挙部４６は、第２予備選挙において、同一のデータの推薦投票を判定する場合に、入力データと識別値とを合成したデータが同一であるかどうかを判定する。
【０１３８】
分離部６３は、選挙部４６により処理順序が決定されたデータを、入力データと識別値とに分離する。そして、分離部６３は、分離後の識別値をプライマリ特定部４５に出力し、分離後の入力データの部分を順序番号とともに確定データ記憶部４７へと出力する。
【０１３９】
プライマリ特定部４５は、分離部６３により分離された識別値により識別されるサーバ装置２０を、処理順序が決定したデータの次の順序番号のプライマリのサーバ装置２０として特定する。そして、プライマリ特定部４５は、特定したプライマリのサーバ装置２０のノード番号を選挙部４６へと出力する。
【０１４０】
ここで、ある順序番号で処理すべきとして選挙部４６により決定されたデータは、全てのサーバ装置２０で同一となる。従って、ある順序番号で処理すべきとして選挙部４６により決定されたデータから分離された、次の順序番号のプライマリのサーバ装置２０の識別値も、全てのサーバ装置２０で同一となる。これにより、第２実施形態に係る整列装置３２は、順序番号毎に、全てのサーバ装置２０で同一のプライマリのサーバ装置２０を一貫性を持って特定することができる。
【０１４１】
また、第２実施形態に係る整列装置３２は、プライマリのサーバ装置２０を順序番号毎に動的に変更することができる。これにより、整列装置３２は、故障したサーバ装置２０をプライマリのサーバ装置２０として特定し続けてしまうことを回避することができる。
【０１４２】
また、次プライマリ提案部６１は、一例として、自身のサーバ装置２０を識別する値を、次の順序番号のプライマリのサーバ装置２０の識別値として発生してよい。これにより、次プライマリ提案部６１は、少なくとも自身のサーバ装置２０は動作しているので、動作しているサーバ装置２０（すなわち、故障していないサーバ装置２０）をプライマリとして特定することができる。
【０１４３】
また、次プライマリ提案部６１は、一例として、動作中であることが確認されたサーバ装置２０を識別する値を次の順序番号のプライマリのサーバ装置２０の識別値として発生してもよい。例えば、次プライマリ提案部６１は、投票受信部４２が受信した投票から、動作中であるサーバ装置２０を確認してもよい。また、次プライマリ提案部６１は、他のサーバ装置２０と生存確認の通信をして、動作中であるサーバ装置２０を確認してもよい。これにより、次プライマリ提案部６１は、動作しているサーバ装置２０（すなわち、故障していないサーバ装置２０）をプライマリとして特定することができる。
【０１４４】
多重化システム１０では、動作しているサーバ装置２０をプライマリのサーバ装置２０として特定することにより、サーバ装置２０間の投票のやり取りをベストケースにおいて１往復で完了させることが可能となる。従って、多重化システム１０では、動作しているサーバ装置２０をプライマリのサーバ装置２０として特定することにより、効率良く整列マルチキャストを実行させることができる。
【０１４５】
また、次プライマリ提案部６１は、一例として、未確定データ記憶部４１に記憶された未処理の入力データの保留数が、基準値以上のサーバ装置２０を識別する値を、次の順序番号のプライマリのサーバ装置２０の識別値として発生してもよい。この場合、次プライマリ提案部６１は、一例として、他のサーバ装置２０と通信をして、未処理の入力データの保留数の通知を受け、未処理の入力データの保留数が基準値以上のサーバ装置２０を検出してもよい。
【０１４６】
多重化システム１０では、プライマリのサーバ装置２０がクライアント装置から入力データを受信した場合、最も効率良く整列マルチキャストを実行させることができる。従って、多重化システム１０では、次プライマリ提案部６１が未処理の入力データの保留数が多いサーバ装置２０をプライマリのサーバ装置２０として提案することにより、保留された入力データを効率良く処理させることができる。
【０１４７】
＜第３実施形態＞
図１３は、第３実施形態に係る整列装置３２の処理を示すフローチャートである。第３実施形態に係る多重化システム１０は、図１〜図１２を参照して説明した第１実施形態および第２実施形態と略同一の機能および構成を有するので、略同一の機能を有する部材には同一の符号を付けて説明を省略する。
【０１４８】
第１実施形態および第２実施形態に係る制御部５７は、現在のラウンド番号が初期値の場合に第１予備選挙部５３に処理を実行させる。これに加えて、第３実施形態に係る制御部５７は、信任選挙部５５の処理の後であって、現在のラウンド番号が予め定められた値の場合において、第１予備選挙部５３に処理を実行させる。
【０１４９】
例えば、制御部５７は、図１３に示すように、現在のラウンド番号が１ではない奇数の場合（Ｓ１６のＹｅｓ）、ステップＳ１０１に処理を進める。ステップＳ１０１において、制御部５７は、第１予備選挙を実行するか否かを判断する。
【０１５０】
制御部５７は、第１予備選挙を実行すると判断した場合（Ｓ１０１のＹｅｓ）、処理をステップＳ１５に進めて、第１予備選挙部５３を呼び出して第１予備選挙を実行させる。制御部５７は、第１予備選挙を実行させないと判断した場合（Ｓ１０１のＮｏ）、処理をステップＳ１７に進めて、第２予備選挙部５４を呼び出して第２予備選挙を実行させる。
【０１５１】
制御部５７は、一例として、ラウンド番号を４で割った余りが１の場合に第１予備選挙（Ｓ１５）を実行させ、ラウンド番号を４で割った余りが３の場合に第２予備選挙（Ｓ１７）を実行させてもよい。また、制御部５７は、ラウンド数が予め定められた値（例えば３以上の値の整数）以下の場合に、第１予備選挙（Ｓ１５）を実行させ、ラウンド数が予め定められた値より大きい場合に、第２予備選挙（Ｓ１７）を実行させてもよい。なお、ステップＳ１０１の第１予備選挙を実行させるか、第２予備選挙を実行させるかの判断の結果は、全てのサーバ装置２０で同一である。
【０１５２】
第３実施形態に係る多重化システム１０によれば、初期ラウンド以外においても第１予備選挙を実行するので、それぞれのサーバ装置２０は、プライマリのサーバ装置２０から初期ラウンド以外の推薦投票を取得した場合にも、当確投票を生成することができる。従って、第３実施形態に係る多重化システム１０によれば、さらに効率良く、整列マルチキャストを実行することができる場合がある。
【０１５３】
以下、第３実施形態に係る多重化システム１０において、整列マルチキャストの一貫性が保たれることの正当性について証明する。
【０１５４】
（補題５）当選投票ｘが信任選挙で決定したならば、その後のラウンドの投票の値はｘの値と等しい。
［証明］
補題３より、ｘが決定した信任選挙の次の予備選挙で用いられる推薦投票の値は全てｘの値と等しい。選挙によって決定する次のラウンドの投票の値は、前のラウンドの投票の値のいずれかであるから、前のラウンドの投票の値が全て同じ値であれば、次のラウンドの投票の値も全て同じになる。従って、数学的帰納法により、その後のラウンドの投票の値はｘの値と等しい。
［証明終］
【０１５５】
補題２と補題５から、当選投票はラウンドが異なっているとしても全て同じ値であることがわかる。すなわち、最初に当選投票となったラウンドをｒとすると、ラウンドｒ以降に当選投票があったとすれば、それは同じ値になる。これにより本実施形態のアルゴリズムは、多重化の一貫性が保証されていることが証明された。
【０１５６】
第３実施形態は第１実施形態を一般化したものである。つまり、第１実施形態は第３実施形態の特別な場合としてみることができる。ただし、最短のパスの投票の送信回数が１往復分である性質は、初期ラウンドが第１予備選挙である場合にのみ得られる。
【０１５７】
なお、第３ラウンド以降で第１予備選挙を適用したとしても、最短のパスに変化はない。むしろ、プライマリのサーバ装置２０が動作していない場合には、第１予備選挙の結果は必ず補欠投票となるため、パスが２ラウンド分（＝１往復分）長くなる。従って、障害発生時のノンブロッキング性を優先すれば、第１実施形態のように第３ラウンド以降では全て第２予備選挙を使用することが妥当である。
【０１５８】
一方で、プライマリのサーバ装置２０が動作している場合には、多数決によって当確を決定する第２予備選挙よりも、プライマリのサーバ装置２０からの投票だけで当確投票が生成できる第１予備選挙の方が効率がよい可能性もある。
【０１５９】
図１４は、実施形態に係るサーバ装置２０のハードウェア構成を示す図である。サーバ装置２０は、ＣＰＵ（Central  Processing  Unit）２０１と、ＲＯＭ（Read  Only  Memory）２０２と、ＲＡＭ（Random  Access  Memory）２０３と、通信装置２０４とを備える。これらの各部は、バスにより接続される。
【０１６０】
ＣＰＵ２０１は、プログラムに従って演算処理および制御処理等を実行するプロセッサである。ＣＰＵ２０１は、ＲＡＭ２０３の所定領域を作業領域とし、記録媒体等に予め記憶された各種プログラムとの協働により各種処理を実行し、サーバ装置２０を構成する整列装置３２（ラウンド管理部５１、初期投票生成部５２、第１予備選挙部５３、第２予備選挙部５４、信任選挙部５５、当選処理部５６および制御部５７を有する選挙部４６、および、プライマリ特定部４５）並びにデータ処理部３３の機能を実現させる。
【０１６１】
ＲＯＭ２０２は、サーバ装置２０の制御に用いられるプログラムおよび各種設定情報等を書き換え不可能に記憶する。ＲＡＭ２０３は、ＳＤＲＡＭ（Synchronous  Dynamic  Random  Access  Memory）等の揮発性の記憶媒体である。ＲＡＭ２０３は、ＣＰＵ２０１の作業領域として機能する。具体的には、サーバ装置２０が実行するデータを記憶し、整列装置３２内の未確定データ記憶部４１、投票記憶部４３および確定データ記憶部４７等として機能する。
【０１６２】
通信装置２０４は、外部の機器（クライアント装置および他のサーバ装置２０等）と通信する。通信装置２０４は、データ受信部３１およびデータ送信部３４、および、整列装置３２内の投票受信部４２および投票送信部４４等として機能する。
【０１６３】
なお、サーバ装置２０は、このような構成に限らず、データ受信部３１、整列装置３２、データ処理部３３およびデータ送信部３４の少なくとも一部をハードウェア回路（例えば半導体集積回路）により実現する構成であってもよい。
【０１６４】
また、本実施形態のサーバ装置２０で実行されるプログラムは、インストール可能な形式または実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク、ＣＤ−Ｒ、ＤＶＤ（Digital  Versatile  Disk）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０１６５】
また、本実施形態のサーバ装置２０で実行されるプログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成してもよい。また、本実施形態のサーバ装置２０で実行されるプログラムをインターネット等のネットワーク経由で提供または配布するように構成してもよい。また、本実施形態のサーバ装置２０で実行されるプログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０１６６】
本実施形態のサーバ装置２０で実行されるプログラムは、上述したサーバ装置２０の各部（整列装置３２（ラウンド管理部５１、初期投票生成部５２、第１予備選挙部５３、第２予備選挙部５４、信任選挙部５５、当選処理部５６および制御部５７を有する選挙部４６、および、プライマリ特定部４５）並びにデータ処理部３３）を含むモジュール構成となっており、ＣＰＵ２０１（プロセッサ）が記憶媒体等からプログラムを読み出して実行することにより上記各部がＲＡＭ２０３上にロードされ、サーバ装置２０（整列装置３２およびデータ処理部３３）がＲＡＭ２０３上に生成されるようになっている。
【０１６７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、請求の範囲に記載された発明とその均等の範囲に含まれる。
【図１】
2016020986.tif 000003
【図２】
2016020986.tif 000004
【図３】
2016020986.tif 000005
【図４】
2016020986.tif 000006
【図５】
2016020986.tif 000007
【図６】
2016020986.tif 000008
【図７】
2016020986.tif 000009
【図８】
2016020986.tif 000010
【図９】
2016020986.tif 000011
【図１０】
2016020986.tif 000012
【図１１】
2016020986.tif 000013
【図１２】
2016020986.tif 000014
【図１３】
2016020986.tif 000015
【図１４】
2016020986.tif 000016
【国際調査報告】
2016020986.tif 000017
2016020986.tif 000018
2016020986.tif 000019
2016020986.tif 000020