(57)【要約】【課題】通信の信頼性を向上させる並列処理装置、リダクション演算システム及びリダクション演算方法を提供する。【解決手段】分散ノード１０は、複数存在する。各分散ノード１０は、送信データの離散対数である離散対数データを求め、求めた離散対数データを送出する。リダクション装置２０は、各分散ノード１０が送出した離散対数データの和を計算する。さらに、リダクション装置２０は、算出した和を集約ノード３０へ送信する。集約ノード３０は、リダクション装置２０により送信された離散対数データの和を復号化して、各送信データを取得する。【選択図】図１
2020013336.tif 000002
【特許請求の範囲】
【請求項１】
送信データの離散対数である離散対数データを求め、求めた前記離散対数データを送出する複数の送信部と、
前記送信部が送出した前記離散対数データの和を計算し、算出した和を送信するリダクション処理部と、
前記リダクション処理部により送信された前記離散対数データの和を復号化して、前記送信データを取得する復号化部と
を備えたことを特徴とする並列処理装置。
【請求項２】
前記復号化部は、拡張ユークリッドの互除法を用いて前記復号化を行うことを特徴とする請求項１に記載の並列処理装置。
【請求項３】
前記送信部は、所定数の素数で表される符号化鍵を法とし、各前記符号化鍵の原始根を底として、前記送信データを表すそれぞれ異なる素数における離散対数を計算することで前記離散対数データを求め
前記復号化部は、前記原始根を基に離散対数の逆演算を行うことで前記離散対数データを復号化し、さらに、拡張ユークリッドの互除法を用いて復号化を行う
ことを特徴とする請求項１又は２に記載の並列処理装置。
【請求項４】
前記送信部は、前記送信データの総積が前記符号化鍵の総積よりも小さくなるように前記符号化鍵を決定することを特徴とする請求項３に記載の並列処理装置。
【請求項５】
演算を行う複数の分散ノード、集約ノード及びリダクション装置を有するリダクション演算システムであって、
各前記分散ノードは、送信データの離散対数である離散対数データを求め、求めた前記離散対数データを送出し、
前記リダクション装置は、前記分散ノードが送出した前記離散対数データの和を計算し、算出値を前記集約ノードへ送信し、
前記集約ノードは、前記リダクション装置により送信された前記算出値を復号化して前記送信データを取得する
ことを特徴とするリダクション演算システム。
【請求項６】
演算を行う複数の分散ノード、集約ノード及びリダクション装置によるリダクション演算方法であって、
前記分散ノードに、送信データの離散対数である離散対数データを求めさせ、且つ、前記離散対数データを送出させ、
前記リダクション装置に、前記分散ノードが送出した前記離散対数データの和を計算させ、算出した和を前記集約ノードへ送信させ、
前記集約ノードに、前記離散対数データの和を復号化させることで前記送信データを取得させる
ことを特徴とするリダクション演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列処理装置、リダクション演算システム及びリダクション演算方法に関する。
【背景技術】
【０００２】
大規模な分散システムでは、複数ノードを使用して実行される並列ジョブの制御や、システム全体でノードあるいはノードの構成部品などを資源として管理することが行われる。そのためには、ジョブ又はシステム全体の制御行うノードに対して、管理対象の状態情報がリアルタイムで集約されることが望ましい。
【０００３】
このような集約を行うための情報集約型通信では、ネットワーク上のデータの送受信に伴う通信量又は伝送時間が問題となる。近年の計算機システムは、各ノードを構成するコンピュータの処理速度に比べ、ノード間を繋ぐネットワークの通信速度が格段に遅い。そのため、ネットワーク上を伝送される管理対象の状態情報の通信量が、情報集約システム全体の負荷の大きさを決定する主要因となることが多い。
【０００４】
さらに、各ノードから割込み処理を伴う１対１通信を使って制御を行うノードに対して通信を行う場合、以下の問題が発生する。１つには、例えば故障発生の通知を行う場合、制御を行うノードは、各ノードが故障して通信が行われない場合と、各ノードに問題がなく通信が行われない場合とを区別することが困難である。また、多くのノードからの通信が発生すると、制御を行うノードの受信処理の負荷が大きくなってしまう。
【０００５】
そこで、管理対象の状態情報の通信量による負荷の軽減及び高速通信を実現する技術として、分散したノードからリダクション通信を使用して情報を伝達することで、１対１の通信を用いるよりも全体のメッセージサイズを小さくして高速に通信する技術がある。
【０００６】
なお、離散対数の検証方法として以下のような従来技術がある。１つの従来技術では、ｎと互いに素な整数Ｌ０に関して、Ｌ１＝Ｌ０ｋ１  ｍｏｄ  ｎ、・・・、Ｌｍ＝Ｌ０ｋｍ  ｍｏｄ  ｎとなるＬ０、・・・・、Ｌｍのうちのノルムの小さいものが使用される。そして、ｅをＧの単位元とし、ｇ０をｙの逆元としてｅ＝Πｍｉ＝０ｇｉＬｉの真理値を用いて多基底離散対数の検証が行われる。また、他の従来技術として、Ｐの位数ｑに対して、ｋ１＝ｋ２  ｍｏｄ  ｑという関係式を満たす整数ｋ１及びｋ２が求め、ｋ２Ｑ＝ｋ１Ｐを用いて離散対数の検証を行う技術がある。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００３−２１６０３０号公報
【特許文献２】特開２００３−２１６０２９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、従来の方法では総積リダクション通信を用いるため、送信するメッセージの値が大きい場合や分散したノード数が大きい場合には、リダクション時にオーバーフローが発生しやすく通信の信頼性が低下するおそれがある。また、離散対数の検証方法に関する従来技術を用いても、リダクション時のオーバーフローを抑制することは困難である。
【０００９】
開示の技術は、上記に鑑みてなされたものであって、通信の信頼性を向上させる並列処理装置、リダクション演算システム及びリダクション演算方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本願の開示する並列処理装置、リダクション演算システム及びリダクション演算方法の一つの態様において、複数の初期設定部は、送信データの離散対数である離散対数データを求め、求めた離散対数データを送出する。リダクション処理部は、前記初期設定部が送出した前記離散対数データの和を計算し、算出した和を送信する。復号化部は、前記リダクション処理部により送信された前記離散対数データの和を復号化して、前記送信データを取得する。
【発明の効果】
【００１１】
１つの側面では、本発明は、通信の信頼性を向上させることができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、リダクション演算システムの一例の構成図である。
【図２】図２は、集約ノードのブロック図である。
【図３】図３は、ノード識別子リストの一例の図である。
【図４】図４は、符号化鍵リストの一例を示す図である。
【図５】図５は、分散ノードのブロック図である。
【図６】図６は、符号化済識別子リストの一例を示す図である。
【図７】図７は、リダクション通信に関する初期設定処理の概要のフローチャートである。
【図８】図８は、初期設定時の集約ノード及び分散ノードによる処理のフローチャートである。
【図９】図９は、集約ノードによる符号化鍵の作成処理のフローチャートである。
【図１０】図１０は、分散ノードによる符号化済識別子リストの作成処理のフローチャートである。
【図１１】図１１は、リダクション通信時の処理の概要のフローチャートである。
【図１２】図１２は、リダクション通信時の分散ノードによるデータの送信処理のフローチャートである。
【図１３】図１３は、リダクション通信時の集約ノードによる送信元特定処理のフローチャートである。
【図１４】図１４は、情報処理装置のハードウェア構成図である。
【図１５】図１５は、リダクション装置のハードウェア構成図である。
【発明を実施するための形態】
【００１３】
以下に、本願の開示する並列処理装置、リダクション演算システム及びリダクション演算方法の実施例を図面に基づいて詳細に説明する。なお、以下の実施例により本願の開示する並列処理装置、リダクション演算システム及びリダクション演算方法が限定されるものではない。
【実施例】
【００１４】
図１は、リダクション演算システムの一例の構成図である。リダクション演算システム１は、図１に示すように、複数の分散ノード１０、リダクション装置２０及び集約ノード３０を有する。このリダクション演算システム１が、「並列処理装置」の一例にあたる。本実施例では、いずれかの分散ノード１０に障害が発生した場合に、障害が発生した分散ノード１０が自己を示す情報を送信し、送信された情報を用いていずれの分散ノード１０に障害が発生したかを集約ノード３０が認識する処理を例に説明する。
【００１５】
分散ノード１０には、それぞれを表すノード番号が割り当てられる。例えば、１から順番に連番の整数が各分散ノード１０にノード番号として割り当てられる。また、分散ノード１０は、各ノード番号に対して割り当てられたそれぞれ異なる素数であるノード識別子を集約ノード３０から取得する。また、分散ノード１０は、ノード識別子の離散対数を求めるための法となる符号化鍵及びその原始根の組の情報を集約ノード３０から取得する。ここで、図１では、例示的に紙面に向かって左端の分散ノード１０に対して集約ノード３０からの通信経路を付加したが、他の分散ノード１０も同様に集約ノード３０からの通信経路を有する。
【００１６】
次に、分散ノード１０は、故障が発生した場合に自己のノード番号に対応するノード識別子の離散対数を符号化鍵及び原始根を用いて算出し、符号化済識別子とする。そして、定期的な通信タイミングが到来すると、故障が発生した分散ノード１０は、算出した符号化済識別子をリダクション装置２０へ出力する。また、故障が発生していない分散ノード１０は、リダクション装置２０に対して０を出力する。この分散ノード１０が、「送信部」の一例にあたる。
【００１７】
リダクション装置２０は、各分散ノード１０から入力された値の総和を算出する。ここで、故障が発生していない分散ノード１０は０を出力するので、各分散ノード１０から入力された値の和は、故障が発生した分散ノード１０が送出した符号化済識別子の総和と言える。そして、リダクション装置２０は、算出結果である故障が発生した分散ノード１０が送出した符号化済識別子総和を集約ノード３０へ出力する。このリダクション装置２０が、「リダクション処理部」の一例にあたる。
【００１８】
集約ノード３０は、故障が発生した分散ノード１０が送出した符号化済識別子総和の入力をリダクション装置２０から受ける。そして、集約ノード３０は、符号化鍵及びユークリッド互除法を用いて故障が発生した分散ノード１０が送出した符号化済識別子総和を復号化する。さらに、集約ノード３０は、復号化によって取得した値を素因数分解するなどして、元のノード識別子を取得する。その後、集約ノード３０は、取得したノード識別子に対応するノード識別番号を取得して、いずれの分散ノード１０で故障が発生したかを特定する。この集約ノード３０が、「復号化部」の一例にあたる。
【００１９】
図２は、集約ノードのブロック図である。集約ノード３０は、図２に示すように、集約ノード初期設定部３１、集約ノード通信部３２、識別子保持部３３及び符号化鍵保持部３４を有する。識別子保持部３３及び符号化鍵保持部３４は、ハードディスクなどの記憶装置である。
【００２０】
集約ノード初期設定部３１は、リダクション通信における初期設定を行う。集約ノード初期設定部３１は、ノード識別子生成部３１１、符号化鍵生成部３１２及び初期設定情報通知部３１３を有する。
【００２１】
ノード識別子生成部３１１は、各分散ノード１０にノード識別子として素数を割り当てる。そして、ノード識別子生成部３１１は、図３に示すノード番号とノード識別子の対応を表すノード識別子リスト３０１を登録したノード識別子リストファイルを生成して、識別子保持部３３に格納する。図３は、ノード識別子リストの一例の図である。ノード識別子リスト３０１は、各ノードのノード番号に対応させて、ノード識別子生成部３１１が決定したノード識別子が登録される。さらに、ノード識別子生成部３１１は、生成した各ノード識別子を符号化鍵生成部３１２へ通知する。
【００２２】
符号化鍵生成部３１２は、ノード識別子の通知をノード識別子生成部３１１から受ける。次に、符号化鍵生成部３１２は、全ての分散ノード１０のノード識別子を乗算した値よりもその組の素数を乗算した値が大きくなる素数の組を算出する。そして、符号化鍵生成部３１２は、求めた組に含まれる素数を符号化鍵とする。ここで、符号化鍵の数、すなわち上述した素数の組に含まれる素数の数は、リダクション装置２０が取り扱う固定長の演算データの大きさをａｂｉｔとした場合、２ａ以下の数であることが好ましい。さらに、符号化鍵とする素数は、なるべく２ａに近い値であることが好ましい。符号化鍵が２ａに近い値であれば、総和を取るリダクション通信中にオーバーフローを発生し難くすることができる。
【００２３】
次に、符号化鍵生成部３１２は、符号化鍵の原始根を算出する。その後、符号化鍵生成部３１２は、図４に示す符号化鍵と原始根との対応を表す符号化鍵リスト３０２を登録した符号化鍵リストファイルを生成して、符号化鍵保持部２４へ格納する。図４は、符号化鍵リストの一例を示す図である。符号化鍵リスト３０２は、各符号化鍵に対応させて、その符号化鍵の原始根が登録される。
【００２４】
ここで、以下の２条件が成立すれば符号化済識別子総和を求める際の加法でオーバーフローが発生せず、且つ、第２復号化データｘには法を符号化鍵の総積とすることによる不定性がない。第１の条件は、離散対数であるノード識別子の総積が符号化鍵の総積よりも小さいという条件である。また、第２の条件は、符号化済識別子の総和が通信時の固定長演算の上限よりも小さいという条件である。
【００２５】
ここで、集約ノード３０において特定可能な送信データの数を分解能とした場合の各条件と分可能の対応関係について説明する。第１の条件は、求める分解能に比例させて使用する符号化鍵の数を増加させれば、分解能を大きくした場合も満足させることは可能である。また、第２の条件は、演算が加法であることから、演算が乗算の場合に比べて比較的大きな分解能に対しても満足させることができる。したがって、本実施例に係るリダクション演算システム１は、容易に分解能の向上を実現することができる。そこで、符号化鍵生成部３１２は、第１条件及び第２条件を満たすように、符号化鍵を決定することが好ましい。
【００２６】
初期設定情報通知部３１３は、識別子保持部３３が保持するノード識別子リスト３０１を確認して、ノード識別子リスト３０１に登録されたノード識別子のうち宛先の分散ノード１０のノード番号に対応するノード識別子を各分散ノード１０に対して送信する。また、初期設定情報通知部３１３は、符号化鍵保持部３４に格納された符号化鍵リスト３０２に登録された全ての符号化鍵と原始根との組の情報を取得して各分散ノード１０へ符号化鍵リスト３０２に登録された順番で送信する。以下では、初期設定情報通知部３１３が送信した符号化鍵と原始根との組の情報を単に符号化鍵リスト３０２という場合がある。以上により集約ノード３０におけるリダクション通信に関する初期設定が完了する。
【００２７】
集約ノード通信部３２は、リダクション装置２０から送信された符号化済識別情報総和から符号化済識別情報の送信元である故障が発生した分散ノード１０を特定する処理を行う。集約ノード通信部３２は、第１復号化部３２１、第２復号化部３２２、第３復号化部３２３及び特定部３２４を有する。
【００２８】
第１復号化部３２１は、障害が発生した分散ノード１０が送信した符号化済識別子の総和である符号化済識別子総和をリダクション装置２０から受信する。ここで、符号化済識別子は符号化鍵毎に生成されるため、第１復号化部３２１は、符号化鍵の数の符号化済識別子総和を受信する。次に、第１復号化部３２１は、符号化済識別子総和に対して離散対数の逆演算を行い第１復号化データを取得する。具体的には、第１復号化部３２１は、符号化済識別子総和に対して符号化鍵保持部３４に格納された符号化鍵リスト３０２から、各符号化済識別子総和に対応する符号化鍵及び原始根の組を取得する。そして、第１復号化部３２１は、対応する符号化鍵を法とする原始根の値を符号化済識別子総和の数でべき乗して第１段階の復号化を行って第１復号化データを取得する。ここで、第１復号化部３２１は、各符号化鍵に対応する第１復号化データを算出する。そして、第１復号化部３２１は、算出した各符号化鍵に対応する第１復号化データを第２復号化部３２２へ出力する。
【００２９】
第２復号化部３２２は、各符号化鍵に対応する第１復号化データの入力を第１復号化部３２１から受ける。次に、第２復号化部３２２は、全ての第１復号化データに対して符号化鍵を用いた剰余がいずれも同じ第２復号化データとなるものとする。そして、第２復号化部３２２は、決定した条件に対して拡張ユークリッドの互除法を用いて第２段階の復号化を行って第２復号化データを取得する。この第２復号化データは、故障が発生した分散ノード１０のノード番号に対応するノード識別子の積である。第２復号化部３２２は、算出した第２復号化データを第３復号化部３２３へ出力する。
【００３０】
第３復号化部３２３は、第２復号化データの入力を第２復号化部３２２から受ける。次に、第３復号化部３２３は、第２復号化データを素因数分解して第３段階の復号化を行って第３復号化データを取得する。すなわち、第３復号化部３２３は、通常の整数ないし代数的整数の素因数分解の一意性を利用して第２復号化データから素数であるノード識別子を取得する。第３復号化データは、ノード識別子にあたる。その後、第３復号化部３２３は、取得した第３復号化データを特定部３２４へ出力する。
【００３１】
特定部３２４は、第３復号化データの入力を第３復号化部３２３から受ける。次に、特定部３２４は、識別子保持部２３に格納されたノード識別子リスト３０１から、第３復号化データに対応するノード番号を取得する。これにより、特定部３２４は、故障が発生した分散ノード１０を特定することができる。その後、特定部３２４は、故障が発生した分散ノード１０のノード番号を管理者に通知するといった所定の処理を実行する。
【００３２】
ここで、集約ノード通信部３２は、１つの符号化済識別子総和を受け取った場合、ノード識別子の総積を復号することは困難である。そこで、復号を行うためには、複数の符号化済識別子総和を用いることが好ましい。そして、複数の復号化済識別子の復号には、拡張ユークリッドの互除法を用いることが好ましい。そこで、集約ノード通信部３２は、拡張ユークリッドの互除法を用いて復号化を実行する。
【００３３】
図５は、分散ノードのブロック図である。図５に示すように、分散ノード初期設定部１１、分散ノード通信部１２、符号化済識別子保持部１３及び故障検出部１４を有する。符号化済識別子保持部１３は、ハードディスクなどの記憶装置である。
【００３４】
分散ノード初期設定部１１は、自己のノード番号に対応するノード識別子を集約ノード３０の初期設定情報通知部３１３から受信する。また、分散ノード初期設定部１１は、集約ノード３０が有する符号化鍵リスト３０２に登録された全ての符号化鍵と原始根との組の情報を集約ノード３０の初期設定情報通知部３１３から符号化鍵リスト３０２の登録順に受信する。
【００３５】
次に、分散ノード初期設定部１１は、取得したノード識別子について取得した符号化鍵を法としてその符号化鍵の原始根を底とする離散対数を求め符号化済識別子とする。ノード識別子が、「送信データ」の一例にあたる。また、符号化済識別子が、「離散対数データ」の一例にあたる。
【００３６】
ここで、分散ノード初期設定部１１が離散対数を用いる理由を説明する。一般的な対数の値は浮動小数点である。浮動小数点の加算では演算誤差が生じるため、一般的な対数を用いる場合には、例えば、値Ｍ１及びＭ２に関して一般的な対数の性質ｌｏｇ（Ｍ１）＋ｌｏｇ（Ｍ２）＝ｌｏｇ（Ｍ１×Ｍ２）という式が成立しないおそれある。そのため、一般的な対数を用いる場合、元の値Ｍ及びＮを復元することが困難になる。そこで、加算による誤差を生じさせないためには整数値をとる対数を用いることが好ましく、この条件を満たすために、分散ノード初期設定部１１は、離散対数を用いる。
【００３７】
ここで、分散ノード初期設定部１１は、取得した符号化鍵と原始根の組のそれぞれについて、それらの組を取得した順に離散対数を求める。したがって、分散ノード初期設定部１１は、取得した符号化鍵と原始根の組の数と同数の符号化済識別子を取得する。そして、分散ノード初期設定部１１は、取得した符号化済識別子を用いて、例えば図６に示す符号化済識別子リスト１０１Ａを作成する。この時、分散ノード初期設定部１１は、離散対数の算出に用いた符号化鍵及び原始根の取得順に、符号化済識別子を符号化済識別子リスト１０１Ａに登録する。
【００３８】
図６は、符号化済識別子リストの一例を示す図である。図６では、４台の分散ノード１０がそれぞれ作成した符号化済識別子リスト１０１Ａ〜１０１Ｄを図示した。ノード識別子は、各分散ノード１０においてそれぞれ異なる素数であるためノード識別子の離散対数もそれぞれ異なり、符号化済識別子リスト１０１Ａ〜１０１Ｄもそれぞれ異なる値が登録される。以下では、符号化済識別子リスト１０１Ａ〜１０１Ｄをそれぞれ区別しない場合、単に「符号化済識別子リスト１０１」と表記する。
【００３９】
その後、分散ノード初期設定部１１は、作成した符号化済識別子リスト１０１を登録した符号化済識別子リストファイルを生成して符号化済識別子保持部１３に格納する。これにより、分散ノード初期設定部１１によるリダクション通信に関する初期設定は完了する。
【００４０】
ここで、本実施例では送信データがノード番号であり不変であるので、分散ノード初期設定部１１は、予め送信データの離散対数を求めて記憶した。これに対して、送信データが変化する場合、分散ノード初期設定部１１は、データの送信時に送信データの離散対数を求めることが好ましい。その場合、分散ノード初期設定部１１は、取得した自装置のノード識別子及び符号化鍵リスト３０２を、例えば符号化済識別子保持部１３に送信データの送信時まで保持させることが好ましい。
【００４１】
故障検出部１４は、分散ノード１０で故障が発生した場合、その故障の発生を検出する。そして、故障検出部１４は、故障の発生を検出すると、故障発生の通知を分散ノード通信部１２へ出力する。
【００４２】
分散ノード通信部１２は、定期的に故障に関する信号をリダクション装置２０へ送信する。具体的には、故障が発生していない分散ノード１０の場合、分散ノード通信部１２は、故障に関する信号として０の値を通知する信号をリダクション装置２０へ送信する。
【００４３】
これに対して、故障が発生した分散ノード１０の分散ノード通信部１２は、故障発生の通知を故障検出部１４から受ける。故障発生の通知を受けて、分散ノード通信部１２は、自己のノード番号の集約ノード３０への送信を決定する。次に、分散ノード通信部１２は、符号化済識別子保持部１３に格納された符号化済識別子リスト１０１から全ての符号化済識別子を取得する。そして、分散ノード通信部１２は、次の故障に関する信号の送信タイミングで、符号化済識別子リスト１０１に並んだ順に符号化済識別子をリダクション装置２０へ送信する。
【００４４】
リダクション装置２０は、符号化済識別子リスト１０１に並んだ順に符号化済識別子を、故障が発生した各分散ノード１０の分散ノード通信部１２から受信する。そして、リダクション装置２０は、各分散ノード１０から送信された符号化済識別子のうち受信した順番が同じ符号化済識別子同士を加算して符号化済識別子総和を算出する。すなわち、リダクション装置２０は、符号化済識別子リスト１０１に登録された符号化済識別子の数の符号化済識別子総和を算出する。その後、リダクション装置２０は、算出した符号化済識別子総和を、総和の要素となった符号化済識別子の受信順に集約ノード３０へ送信する。
【００４５】
次に、図７を参照して、リダクション通信に関する初期設定処理の流れについて説明する。図７は、リダクション通信に関する初期設定処理の概要のフローチャートである。以下の説明では、分散ノード１０がＮ台配置されており、各分散ノード１０にノード番号ｊ（ｊ＝１，・・・，Ｎ）が割り当てられた場合で説明する。
【００４６】
集約ノード３０は、各分散ノード１０のノード番号ｊに対して割り当てた素数で表されるノード識別子ｐ（ｊ）（ｊ＝１，・・・，Ｎ）を用いて、素数である符号化鍵ｑ（ｉ）（ｉ＝１，・・・，ｂ）を作成する。この場合、符号化鍵ｑ（ｉ）はｂ個作成される。次に、集約ノード３０は、ｂ個の符号化鍵ｑ（ｉ）のそれぞれの原始根ｒ（i）（ｉ＝１，・・・，ｂ）を作成する。そして、集約ノード３０は、符号化鍵ｑ（ｉ）と原始根ｒ（ｉ）とを対応させた符号化鍵ｑ（ｉ）及び各符号化鍵ｑ（ｉ）の原始根の組である組（ｑ（ｉ），ｒ（ｉ））（ｉ＝１，・・・，ｂ）を作成する（ステップＳ１０１）。
【００４７】
次に、集約ノード３０は、各ノード識別子ｐ（ｊ）をそれぞれのノード識別子ｐ（ｊ）が割り当てられた分散ノード１０へ通知する。また、集約ノード３０は、符号化鍵ｑ（ｉ）及び各符号化鍵の原始根ｒ（ｉ）の組（ｑ（ｉ），ｒ（ｉ））を全ての分散ノード１０へ送信する。これにより、各分散ノード１０及び集約ノード３０は、符号化鍵ｑ（ｉ）及び各符号化鍵の原始根ｒ（ｉ）の組（ｑ（ｉ），ｒ（ｉ））を共有する（ステップＳ１０２）。その後、集約ノード３０は、リダクション通信に関する初期設定処理を完了する。
【００４８】
次に、図８を参照して、初期設定時の集約ノード３０及び分散ノード１０による処理の流れについて説明する。図８は、初期設定時の集約ノード及び分散ノードによる処理のフローチャートである。図８のフローチャートで示した処理は、図７で示したリダクション通信に関する初期設定処理における処理を詳細の一例にあたる。
【００４９】
集約ノード３０のノード識別子生成部３１１は、各分散ノード１０のノード番号ｊに対して割り当てた素数で表されるノード識別子ｐ（ｊ）（ｊ＝１，・・・，Ｎ）を割り当てる。そして、ノード識別子生成部３１１は、ノード番号ｊとノード識別子ｐ（ｊ）の対応を表すノード識別子リスト３０１を作成する（ステップＳ１１１）。
【００５０】
次に、集約ノード３０の符号化鍵生成部３１２は、ノード識別子ｐ（ｊ）を用いて、それぞれ素数であるｂ個の符号化鍵ｑ（ｉ）を作成する。さらに、符号化鍵生成部３１２は、符号化鍵ｑ（ｉ）のそれぞれの原始根を求める。そして、符号化鍵生成部３１２は、ｂ個の符号化鍵ｑ（ｉ）及び原始根ｒ（ｉ）の組（ｑ（ｉ），ｒ（ｉ））が登録された符号化鍵リスト３０２を生成する（ステップＳ１１２）。
【００５１】
次に、初期設定情報通知部３１３は、各分散ノード１０に対応するノード識別子ｐ（ｊ）を送信する。また、初期設定情報通知部３１３は、ｂ個の符号化鍵ｑ（ｉ）及び原始根ｒ（ｉ）の組（ｑ（ｉ），ｒ（ｉ））の順番を決定し、順番にしたがってｂ個の符号化鍵ｑ（ｉ）及び原始根ｒ（ｉ）の組（ｑ（ｉ），ｒ（ｉ））を全ての分散ノード１０に通知する。これにより、集約ノード３０及び分散ノード１０は、ノード識別子ｐ（ｊ）、並びに、ｂ個の符号化鍵ｑ（ｉ）及び原始根ｒ（ｉ）の組（ｑ（ｉ），ｒ（ｉ））を共有する（ステップＳ１１３）。
【００５２】
次に、分散ノード１０の分散ノード初期設定部１１は、ノード識別子ｐ（ｊ）において、ｂ個の素数である各符号化鍵ｑ（ｉ）の法として原始根ｒ（ｉ）を底とする離散対数を求めて符号化済識別子ｃ（ｉ，ｊ）として記憶する（ステップＳ１１４）。
【００５３】
次に、図９を参照して、集約ノード３０による符号化鍵ｑ（ｉ）の作成処理の詳細について説明する。図９は、集約ノードによる符号化鍵の作成処理のフローチャートである。図９のフローで示した処理は、図８におけるステップＳ１１１及びＳ１１２で実行される処理の一例にあたる。
【００５４】
ノード識別子生成部３１１は、ノード番号にあたる値ｊ及びノード識別子ｐ（ｊ）を初期化してｊ＝０とし、ｐ（ｉ）＝１とする。
【００５５】
次に、ノード識別子生成部３１１は、ｊが分散ノード１０の総数であるＮより小さいか否かを判定する（ステップＳ１３２）。
【００５６】
ｊがＮより小さい場合（ステップＳ１３２：否定）、ノード識別子生成部３１１は、ｐ（ｊ）よりも大きい適当な素数を算出し、ｐ（ｊ）に算出した素数を割り当ててｐ（ｊ）の値を更新する（ステップＳ１３３）。
【００５７】
次に、ノード識別子生成部３１１は、ｊを１つインクリメントする（ステップＳ１３４）。
【００５８】
そして、ノード識別子生成部３１１は、ノード番号ｊとノード番号ｊに対応するノード識別子ｐ（ｊ）との組をノード識別子リスト３０１に登録する（ステップＳ１３５）。その後、ノード識別子生成部３１１は、ステップＳ１３２の処理に戻る。
【００５９】
一方、ｊがＮ以上の場合（ステップＳ１３２：肯定）、符号化鍵生成部３１２は、符号化鍵ｑ（ｉ）の総数であるｂ個及び符号化鍵ｑ（ｉ）を初期化して、ｂ＝０及びｑ（ｉ）＝ｐ（ｊ）とする（ステップＳ１３６）。この時点でｐ（ｊ）＝ｐ（Ｎ）であり、ｑ（ｉ）にはｐ（ｊ）の最大値が設定される。
【００６０】
次に、符号化鍵生成部３１２は、ｑ（ｉ）よりも大きい素数を算出し、算出した値をｑ（ｉ）に割り当ててｑ(ｉ)を更新する（ステップＳ１３７）。
【００６１】
次に、符号化鍵生成部３１２は、ｂを１つインクリメントする（ステップＳ１３８）。
【００６２】
そして、符号化鍵生成部３１２は、符号化鍵ｑ（ｉ）の原始根ｒ（ｉ）を算出する。次に、符号化鍵生成部３１２は、符号化鍵ｑ（ｉ）と原始根ｒ（ｉ）との組（ｑ（ｉ），ｒ（ｉ））を符号化鍵リスト３０２に追加する（ステップＳ１３９）。
【００６３】
その後、符号化鍵生成部３１２は、全てのノード識別子ｐ（ｊ）の積が全ての符号化鍵ｑ（ｉ）の積より小さいか否かを判定する（ステップＳ１４０）。全てのノード識別子ｐ（ｊ）の積が全ての符号化鍵ｑ（ｉ）の積以上の場合（ステップＳ１４０：否定）、符号化鍵生成部３１２は、処理をステップＳ１３７へ戻す。
【００６４】
これに対して、全ての符号化鍵ｑ（ｉ）の積が全てのノード識別子ｐ（ｊ）の積より大きい場合（ステップＳ１４０：肯定）、符号化鍵生成部３１２は、ノード識別子リスト３０１の先頭のエントリからノード番号ｊを読み込む（ステップＳ１４１）。すなわち、符号化鍵生成部３１２は、ｊ＝１とする。ここで、全ての符号化鍵ｑ（ｉ）の積が全てのノード識別子ｐ（ｊ）の積より大きいとは、Πｎｐ（ｉ）＜Πｂｊ＝１ｑ（ｉ）と表すことができ、上述したリダクション通信における加法時のオーバーフローを抑えるための第１の条件にあたる。すなわち、分解能ｋを達成するためには、この判定において、ノード識別子リスト３０１のうちのｋ個のノード識別子ｐ（ｊ）の積の上限が、符号化鍵ｑ（ｊ）の全ての積より小さいとの判定を用いればよい。
【００６５】
次に、符号化鍵生成部３１２は、読み込んだノード番号ｊが分散ノード１０の総数Ｎを超えてノード識別子リスト３０１の末尾にあたるか否かを判定する（ステップＳ１４２）。
【００６６】
ノード識別子リスト３０１の末尾でない場合（ステップＳ１４２：否定）、符号化鍵生成部３１２は、ノード識別子ｐ（ｊ）をノード番号ｊの分散ノード１０へ送信する。また、符号化鍵生成部３１２は、符号化鍵リスト３０２をノード番号ｊの分散ノード１０へ送信する（ステップ１４３）。
【００６７】
次に、符号化鍵生成部３１２は、ノード識別子リスト３０１における次のノード番号ｊを読み込む。すなわち、符号化鍵生成部３１２は、ノード番号ｊを１つインクリメントする（ステップＳ１４４）。
【００６８】
一方、ノード識別子リスト３０１の末尾の場合（ステップＳ１４２：肯定）、符号化鍵生成部３１２は、符号化鍵リストファイルを生成して符号化鍵保持部３４へ格納する。また、ノード識別子生成部３１１は、ノード識別子リストファイルを作成して識別子保持部３３へ格納する（ステップＳ１４５）。
【００６９】
次に、図１０を参照して、分散ノード１０による符号化済識別子リスト１０１の作成処理の詳細について説明する。図１０は、分散ノードによる符号化済識別子リストの作成処理のフローチャートである。図１０のフローで示した処理は、図８におけるステップＳ１１４で実行される処理の一例にあたる。
【００７０】
分散ノード初期設定部１１は、自装置に対応するノード識別子ｐ（ｊ）及び符号化鍵リスト３０２を含むメッセージを集約ノード３０から受信する（ステップＳ１５１）。
【００７１】
次に、分散ノード初期設定部１１は、受信したメッセージからノード識別子ｐ（ｊ）及び符号化鍵リスト３０２を読み込む（ステップＳ１５２）。
【００７２】
次に、分散ノード初期設定部１１は、符号化鍵の個数と同数のｂ個のエントリを有する符号化鍵リスト３０２を新規に作成する（ステップＳ１５３）。
【００７３】
次に、分散ノード初期設定部１１は、符号化鍵リスト３０２の先頭のエントリを選択する（ステップＳ１５４）。
【００７４】
次に、分散ノード初期設定部１１は、現在の選択がｂ個目のエントリを超えて符号化鍵リスト３０２の末尾であるか否かを判定する（ステップＳ１５５）。
【００７５】
選択の選択が末尾でない場合（ステップＳ１５５：否定）、分散ノード初期設定部１１は、現在のエントリに登録された符号化鍵ｑ（ｉ）を法とし原始根ｒ（ｉ）を底とするノード識別子ｐ（ｊ）の離散対数を求めて符号化済識別子ｃ（ｉ，ｊ）とする（ステップＳ１５６）。
【００７６】
次に、分散ノード初期設定部１１は、算出した符号化済識別子ｃ（ｉ，ｊ）を符号化鍵リスト３０２の末尾に登録する（ステップＳ１５７）。
【００７７】
次に、分散ノード初期設定部１１は、符号化鍵リスト３０２の次のエントリを選択し（ステップＳ１５８）、処理をステップＳ１５５へ戻す。
【００７８】
これに対して、現在の選択が末尾のエントリの場合（ステップＳ１５５：肯定）、分散ノード初期設定部１１は、符号化済識別子リスト１０１の作成を終了する。
【００７９】
次に、図１１を参照して、リダクション通信時の処理の流れについて説明する。図１１は、リダクション通信時の処理の概要のフローチャートである。
【００８０】
分散ノード１０は、送信データが発生した場合は符号化済識別子リスト１０１の登録順に符号化済識別子ｃ（ｉ，ｊ）（ｉ＝１，・・・，ｂ）を、送信データが発生しない場合は０を、リダクション装置２０で総和を取る方式で送信する（ステップＳ２０１）。ここで、本実施例では、故障が発生した場合に送信データが発生し、その送信データは分散ノード１０のノード番号ｊを表すノード識別子ｐ（ｊ）である。
【００８１】
集約ノード３０は、符号化済識別子ｃ（ｉ，ｊ）（ｉ＝１，・・・，ｂ）の総和である符号化済識別子総和ｅ（ｉ）（ｉ＝１，・・・，ｂ）を順に受信する（ステップＳ２０２）。
【００８２】
集約ノード３０は、符号化済識別子総和ｅ（ｉ）（ｉ＝１，・・・，ｂ）及び符号化鍵リスト３０２を使用して第１段階の復号化を実行し第１復号化データｆ（ｉ）を取得する（ステップＳ２０３）。
【００８３】
次に、集約ノード３０は、第１復号化データｆ（ｉ）に対して拡張ユークリッドの互除法を用いて第２段階の復号化を行い第２復号化データｘを算出する（ステップＳ２０４）。第２復号化データｘは、故障が発生した分散ノード１０のノード識別子ｐ（ｊ）の積である。ここで、符号化鍵ｑ（ｉ）（ｉ＝１，・・・，ｂ）は、ｂ個の相異なる素数である。そこで、Ｑ＝Πｂｉ＝１ｑ（ｉ）を法とする整数ｘでｘ＝ｆ（ｉ）  ｍｏｄ  ｑ（ｉ）が任意のｉについて成り立つｘは、ｐ（ｉ）（ｉ＝１，・・・，ｂ）及びｆ（ｉ）（ｉ＝１，・・・，ｂ）を入力データとして拡張ユークリッドの互除法で計算できる。
【００８４】
次に、集約ノード３０は、算出した第２復号化データを素因数分解して第３段階の復号化を行い、送信データの送信元の分散ノード１０のノード識別子ｐ（ｊ）を取得する（ステップＳ２０５）。
【００８５】
次に、集約ノード３０は、取得したノード識別子ｐ（ｊ）とノード識別子リスト３０１とを照合して、故障した分散ノード１０のノード番号ｊを取得する（ステップＳ２０６）。
【００８６】
ここで、図１１のフローチャートは、分散ノード１０のノード番号ｊを送信データとする場合のフローであるので、既に符号化済識別子リスト１０１が符号化済識別子保持部１３に格納された場合で説明した。ただし、送信データが変化する場合、分散ノード１０は、ステップＳ２０１の前に、送信データの離散対数を求めて符号化済識別子ｃ（ｉ，ｊ）を算出する処理を行う。
【００８７】
次に、図１２を参照して、リダクション通信時の分散ノード１０によるデータの送信処理の詳細について説明する。図１２は、リダクション通信時の分散ノードによるデータの送信処理のフローチャートである。図１２は、図１１におけるステップＳ２０１で実行される処理の一例にあたる。
【００８８】
分散ノード通信部１２は、定期的なデータ送信のタイミングが到来すると、符号化済識別子リスト１０１を符号化済識別子保持部１３から読み出す。そして、分散ノード通信部１２は、符号化済識別子リスト１０１の先頭の値を選択する（ステップＳ２１１）。
【００８９】
次に、分散ノード通信部１２は、現在の選択位置が符号化済識別子リスト１０１に登録されたｂ個の符号化済識別子ｃ（ｉ，ｊ）を超えた符号化済識別子リスト１０１の末尾であるか否かを判定する（ステップＳ２１２）。
【００９０】
現在の選択位置が符号化済識別子リスト１０１の末尾でない場合（ステップＳ２１２：否定）、分散ノード通信部１２は、選択中の符号化済識別子ｃ（ｉ，ｊ）を１つ読み込み送信データとする（ステップＳ２１３）。
【００９１】
次に、分散ノード通信部１２は、故障検出部１４からの故障発生の通知の有無により、自装置が故障が発生した分散ノード１０か否かを判定する（ステップＳ２１４）。自装置が故障が発生した分散ノード１０の場合（ステップＳ２１４：肯定）、分散ノード通信部１２は、処理をステップＳ２１６に進ませる。
【００９２】
これに対して、自装置が故障が発生した分散ノード１０でない場合（ステップＳ２１４：否定）、分散ノード通信部１２は、送信データを０に変更する（ステップＳ２１５）。
【００９３】
その後、分散ノード通信部１２は、リダクション装置２０を用いて総和を求めるリダクション通信によって分散ノード１０に送信データを送信する（ステップＳ２１６）。
【００９４】
次に、分散ノード通信部１２は、符号化済識別子リスト１０１の１つ先の値を選択し（ステップＳ２１７）、処理をステップＳ２１２へ戻す。
【００９５】
一方、現在の選択位置が符号化済識別子リスト１０１の末尾の場合（ステップＳ２１２：肯定）、分散ノード通信部１２は、データの送信処理を終了する。
【００９６】
次に、図１３を参照して、リダクション通信時の集約ノード３０による送信元特定処理の詳細な流れについて説明する。図１３は、リダクション通信時の集約ノードによる送信元特定処理のフローチャートである。図１３は、図１１におけるステップＳ２０２〜２０６で実行される処理の一例にあたる。
【００９７】
第１復号化部３２１は、符号化鍵リスト３０２の先頭のエントリを選択する（ステップＳ２２１）。
【００９８】
次に、第１復号化部３２１は、ｉを初期化して１に設定する（ステップＳ２２２）。
【００９９】
次に、第１復号化部３２１は、選択したエントリが符号化鍵リスト３０２に登録されたｂ個のエントリを超えた符号化鍵リスト３０２の末尾にあたるか否かを判定する（ステップＳ２２３）。
【０１００】
選択したエントリが符号化鍵リスト３０２の末尾でない場合（ステップＳ２２３：否定）、第１復号化部３２１は、リダクション装置２０からメッセージを受信し、受信したメッセージから符号化済識別子総和ｅ（ｉ）を取得する（ステップＳ２２４）。
【０１０１】
次に、第１復号化部３２１は、選択した符号化鍵リスト３０２のエントリから符号化鍵ｑ（ｉ）及び原始根ｒ（ｉ）を取得する（ステップＳ２２５）。
【０１０２】
次に、第１復号化部３２１は、符号化鍵ｑ（ｉ）を法として原始根ｒ（ｉ）の値を符号化済識別子総和ｅ（ｉ）乗して第１段階の復号化を行い第１復号化データｆ（ｉ）を取得する。すなわち、第１復号化部３２１は、ｆ（ｉ）＝ｒ（ｉ）＾ｅ（ｉ）という式を用いて第１復号化データｆ（ｉ）を算出する。そして、第１復号化部３２１は、第１復号化データｆ（ｉ）を自己の記憶領域に格納する（ステップＳ２２６）。
【０１０３】
次に、第１復号化部３２１は、ｉを１つインクリメントする（ステップＳ２２７）。
【０１０４】
そして、第１復号化部３２１は、符号化鍵リスト３０２の次のエントリを選択し（ステップＳ２２８）、処理をステップＳ２２３へ戻す。
【０１０５】
これに対して、選択したエントリが符号化鍵リスト３０２の末尾の場合（ステップＳ２２３：肯定）、第１復号化部３２１は、第１復号化データｆ（ｉ）（ｉ＝１，・・・，ｂ）及び符号化鍵ｑ（ｉ）（ｉ＝１，・・・，ｂ）を第２復号化部３２２へ出力する。第２復号化部３２２は、第１復号化データｆ（ｉ）（ｉ＝１，・・・，ｂ）及び符号化鍵ｑ（ｉ）（ｉ＝１，・・・，ｂ）の入力を第１復号化部３２１から受ける。そして、第２復号化部３２２は、任意のｉに対して、ｆ（ｉ）のｑ（ｉ）による剰余がｘとなる第２復号化データｘの値を拡張ユークリッドの互除法を用いて求めて第２段階の復号化を実行する（ステップＳ２２９）。すなわち、第２復号化部３２２は、ｘ＝ｆ（ｉ）  ｍｏｄ  ｑ（ｉ）を任意のｉについて満たす第２復号化データｘを算出する。そして、第２復号化部３２２は、取得したｘを第２復号化データｘを第３復号化部３２３へ出力する。
【０１０６】
第３復号化部３２３は、第２復号化データｘの入力を第２復号化部３２２から受ける。そして、第３復号化部３２３は、第２復号化データｘの値を素因数分解して第３段階の復号化を実行する（ステップＳ２３０）。その後、第３復号化部３２３は、第２復号化データｘの値を素因数分解した結果を特定部３２４へ出力する。
【０１０７】
特定部３２４は、第２復号化データｘの値を素因数分解した結果の入力を第３復号化部３２３から受ける。次に、特定部３２４は、ノード識別子リスト３０１を識別子保持部３３から読み出す。そして、特定部３２４は、ノード識別子リスト３０１の最初のエントリを選択する（ステップＳ２３１）。
【０１０８】
次に、特定部３２４は、選択したエントリがノード識別子リスト３０１に登録されたＮ個のノード識別子ｐ（ｊ）を超えたノード識別子リスト３０１の末尾にあたるか否かを判定する（ステップＳ２３２）。
【０１０９】
選択したエントリがノード識別子リスト３０１の末尾でない場合（ステップＳ２３２：否定）、特定部３２４は、ノード識別子ｐ（ｊ）が第２復号化データｘの値を素因数分解した結果に含まれるか否かを判定する（ステップＳ２３３）。
【０１１０】
ノード識別子ｐ（ｊ）が第２復号化データｘの値を素因数分解した結果に含まれる場合（ステップＳ２３３：肯定）、特定部３２４は、選択したノード識別子ｐ（ｊ）に対応するノード番号ｊの分散ノード１０が送信データの送信元であることを確認する（ステップＳ２３４）。すなわち、特定部３２４は、ノード識別子ｐ（ｊ）に対応するノード番号ｊの分散ノード１０で故障が発生したことを把握する。
【０１１１】
これに対して、ノード識別子ｐ（ｊ）が第２復号化データｘの値を素因数分解した結果に含まれない場合（ステップＳ２３３：否定）、特定部３２４は、処理をステップＳ２３５へ進ませる。
【０１１２】
その後、特定部３２４は、ノード識別子リスト３０１の次のエントリに進む（ステップＳ２３５）。
【０１１３】
次に、図３及び４に示したノード識別子リスト３０１及び符号化鍵リスト３０２が初期設定において生成された場合を例に、より具体的に本実施例に係るリダクション通信で行われる処理について説明する。ここでは、分散ノード１０は４台配置される。そして、各分散ノード１０には、図３に示すように、ノード番号として１〜４が割り当てられ、それぞれのノード番号に対して、ノード識別子として１０１，１０３，１０７及び１０９が割り当てられる。さらに、図４に示すように、符号化鍵は１２３４３及び１２３４７の２つであり、それぞれの原始根は７及び２である。ここで、４つのノード識別子の積は２つの符号化鍵の積よりも小さく、オーバーフローを抑える第１条件が満たされている。
【０１１４】
そして、例えば、ノード番号が１の分散ノード１０は、１２３４３を法として７を底とした場合と、１２３４７を法として２を底とした場合のノード識別子である１０１の離散対数を求め、それぞれ符号化済識別子として２４８６及び８８７０を得る。ノード番号が１の分散ノード１０は、符号化済識別子として２４８６及び８８７０を登録して図６に示す符号化済識別子リスト１０１Ａを生成する。同様に、ノード番号が２〜４の分散ノード１０は、図６に示す符号化済識別子リスト１０１Ｂ〜１０１Ｄを生成する。
【０１１５】
ここで、ノード番号が１、２及び４の分散ノード１０に故障が発生した場合で説明する。この場合、ノード番号が１、２及び４の分散ノード１０は、それぞれが有する符号化済識別子リスト１０１Ａ、Ｂ又はＤの値を先頭から順に総和を取るリダクション通信を用いて集約ノード３０へ送信する。これに対して、ノード番号が３の分散ノード１０は、０を２回総和を取るリダクション通信を用いて集約ノード３０へ送信する。
【０１１６】
集約ノード３０の第１復号化部３２１は、２回の通信で、それぞれ２１４０６（＝２４８６＋１０７７０＋０＋８１５０）と２０８８９（＝８８７０＋６０６２＋０＋５９５７）とを受信する。次に、第１復号化部３２１は、１２３４３を法として７の２１４０６乗と、１２３４７を法として２の２０８８９乗とを計算して、第１復号化データとして１０７１４及び１０３５０を得る。
【０１１７】
次に、第２復号化部３２２は、ｘ＝１０７１４  ｍｏｄ  １２３４３及びｘ＝１０３５０  ｍｏｄ  １２３４７に対して、拡張ユークリッドの互除法を使用し、第２復号化データとしてｘ＝１１３３９２７を求める。
【０１１８】
次に、第３復号化部３２３は、１１３３９２７を素因数分解して、１０１、１０３及び１０９に分解する。
【０１１９】
最後に、特定部３２４は、ノード識別子リスト３０１を参照して、１０１、１０３及び１０９がそれぞれノード番号の１、２及び４に対応することが分かる。したがって、特定部３２４は、ノード番号が１、２及び４の分散ノード１０から通知を受けたことを把握することができる。
【０１２０】
（ハードウェア構成）
図１４を参照して、分散ノード１０及び集約ノード３０のハードウェア構成の一例について説明する。図１４は、情報処理装置のハードウェア構成図である。分散ノード１０及び集約ノード３０は、例えば、図１４に示す情報処理装置４０によって実現される。
【０１２１】
情報処理装置４０は、ＣＰＵ４１、メモリ４２、通信インタフェース４３及び記憶装置４４を有する。ＣＰＵ４１は、バスを介してメモリ４２、通信インタフェース４３及び記憶装置４４に接続される。
【０１２２】
通信インタフェース４３は、他の装置と通信を行うインタフェースである。分散ノード１０は、この通信インタフェース４３を介して、リダクション装置２０及び集約ノード３０と通信を行う。また、集約ノード３０は、この通信インタフェース４３を介して、分散ノード１０及びリダクション装置２０と通信を行う。
【０１２３】
記憶装置４４は、ハードディスクなどの補助記憶装置である。記憶装置４４は、例えば、分散ノード１０における符号化済識別子保持部１３、並びに、集約ノード３０における識別子保持部３３及び符号化鍵保持部３４の機能を実現する。また、分散ノード１０における記憶装置４４は、分散ノード初期設定部１１、分散ノード通信部１２及び故障検出部１４の機能を実現するためのプログラムを含む各種プログラムを記憶する。また、集約ノード３０における記憶装置４４は、集約ノード初期設定部３１及び集約ノード通信部３２の機能を実現するためのプログラムを含む各種プログラムを記憶する。
【０１２４】
ＣＰＵ４１は、記憶装置４４に格納された各種プログラムを読み出してメモリ４２上に展開して実行する。これにより、分散ノード１０におけるＣＰＵ４１は、分散ノード初期設定部１１、分散ノード通信部１２及び故障検出部１４の機能を実現する。また、集約ノード３０におけるＣＰＵ４１は、集約ノード初期設定部３１及び集約ノード通信部３２の機能を実現する。
【０１２５】
次に、図１５を参照して、リダクション装置２０のハードウェア構成について説明する。図１５は、リダクション装置のハードウェア構成図である。
【０１２６】
図１５に示すように、リダクション装置２０は、通信インタフェース２０１、２０２及び２０４、並びに、加算器２０３を有する。通信インタフェース２０１及び２０２は、分散ノード１０に接続される。また、通信インタフェース２０４は、集約ノード３０に接続される。
【０１２７】
加算器２０３は、通信インタフェース２０１及び２０２を介して入力された分散ノード１０から送信された値を加算する。そして、加算器２０３が算出した加算結果が、通信インタフェース２０４を介して集約ノード３０へ送信される。
【０１２８】
以上に説明したように、本実施例に係るリダクション演算システムは、分散ノードで発生した送信データの離散対数を求め、その離散対数の総和を取るリダクション通信で集約ノードへ送信する。そして、集約ノードは、受信した離散対数の総和に対して符号化鍵及び拡張ユークリッドの互除法を用いて元の送信データを求める。このように、各分散ノードから出力された送信データの総和を送信するリダクション通信を行うことで、リダクション時にオーバーフローが発生する可能性を低減させることができ、通信の信頼性を向上させることができる。さらに、総積リダクションではなく整数の総和リダクションで実現することで、ネットワークの構成も単純にすることができ、システム設計が容易となりコストダウンを図ることができる。
【０１２９】
ここで、情報集約のための演算をソフトウェアで行う場合、任意桁数の乗算を実行することは原理上可能である。ただし、その場合、ハードウェアの演算機能を使用して計算するよりも、計算時間が大幅に増加するおそれがある。さらに、通信装置内に組み込まれた演算装置により演算と通信をソフトウェアの介在なしに行う場合と比較して、情報集約のための演算をソフトウェアで行う場合、通信時間と計算時間との合計が非常に増加するおそれがある。ただし、通信装置内に組み込まれた演算装置は、固定長データの演算が一般的である。
【０１３０】
そこで、監視するデータが発生した閾値ｋこの個別識別子からリダクションにより生成された１個の集団識別子から、入力データであるｋ個の個別識別子を復元する方法が考えられる。ここで、監視する状態である管理対象の数が閾値ｋ以下と想定される場合を、分解能ｋの監視という。また、個別識別子の集合Ｓを任意の要素数がｋ以下の部分集合Ｓ１，Ｓ２（Ｓ１はＳ２の部分集合）に対して、Ｓ１がＳ２と等しくないなら、Ｓ１の要素の総和はＳ２の要素の総和と異なるように選び、整数の加算によるリダクション通信を行う方法も考えられる。この場合、Ｓを決定する過程で、要素数がｋ個以下の部分集合を全て調べて表が作成され、リダクション結果から元のデータを取得する際にその表が用いられる。また、監視するデータが発生した閾値ｋ個以下のノードからリダクションによりｋ個のデータを生成し、生成したｋ個のデータに対して根と係数との関係を利用して元のｋ個の入力データを復元する方法も考えられる。しかし、いずれの方法であっても分解能ｋを向上させることは困難である。すなわち、いずれの方法を用いても、多数の分散ノードが送信データをリダクション通信で送信した場合、元の送信データに復元することが困難となる。
【０１３１】
さらに、対数により浮動小数点の加算で乗算を代替する方法も考えられるが、元の乗算の演算と対数の加法の演算が対等であることから、対数の加法の場合は、浮動小数点の計算誤差により、計算データのビット数が同じにしたまま分解能を上げることは困難である。
【０１３２】
これに対して、本実施例に係るリダクション演算システムは、リダクション装置がハードウェアにより加算を行うため、ソフトウェアによる任意桁数の乗算の実行に比べて通信時間及び計算時間を低減することができる。また、本実施例に係るリダクション演算システムでは、分解能を向上させる場合、生成する符号化鍵の個数を増加させることで実現することができる。そして、リダクション通信における演算が加法であることから、本実施例に係るリダクション演算システムは、上述した他の方法に比べて大きい分解能に対応することができる。
【０１３３】
ここで、以上の説明では、故障した分散ノードのノード番号を通知する場合を例に説明したが、通知する情報はこれに限らない。他の情報を送る場合にも、同様の処理により総和を取るリダクション通信を用いて集約ノードへ情報を送信することができる。
【符号の説明】
【０１３４】
１  リダクション演算システム
１０  分散ノード
１１  分散ノード初期設定部
１２  分散ノード通信部
１３  符号化済識別子保持部
１４  故障検出部
２０  リダクション装置
３０  集約ノード
３１  集約ノード初期設定部
３２  集約ノード通信部
３３  識別子保持部
３４  符号化鍵保持部
１０１，１０１Ａ〜１０１Ｄ  符号化済識別子リスト
３０１  ノード識別子リスト
３０２  符号化鍵リスト
３１１  ノード識別子生成部
３１２  符号化鍵生成部
３１３  初期設定情報通知部
３２１  第１復号化部
３２２  第２復号化部
３２３  第３復号化部
３２４  特定部
【図１】
2020013336.tif 000003
【図２】
2020013336.tif 000004
【図３】
2020013336.tif 000005
【図４】
2020013336.tif 000006
【図５】
2020013336.tif 000007
【図６】
2020013336.tif 000008
【図７】
2020013336.tif 000009
【図８】
2020013336.tif 000010
【図９】
2020013336.tif 000011
【図１０】
2020013336.tif 000012
【図１１】
2020013336.tif 000013
【図１２】
2020013336.tif 000014
【図１３】
2020013336.tif 000015
【図１４】
2020013336.tif 000016
【図１５】
2020013336.tif 000017