ネットワーク環境における計算負荷を考慮したデータ配送のための分散アルゴリズム

点击翻译按钮获取中文摘要

申請者らはこれまでに秘密分散共有法の一種である(k, n)しきい値法を利用した秘密分散ストレージシステム(以下SSSS : Secret Sharing Storage System)を提案している。SSSSは(k, n)しきい値法を利用しているため、従来のネットワークストレージシステムに対して、よりネットワークやハードウェアの障害に強く、より秘密データの盗聴に強いなどの利点を有している。しかし、秘密分散共有法における符号化・復号化処理は多くの時間がかかり、その高速化が重要な課題の一つである。平成18年度では以下のタスクを遂行した。秘密分散共有法における符号化・復号化処理問題をシェア配送問題として定式化した。シェア配送問題は組み合わせ最適化問題であり、その解法を検討するに当たり計算複雑度の検討が必要不可欠である。検討の結果シェア配送問題がNP困難であるという知見を得た。シェア配送問題がNP困難であることが示せたので、解くためにはヒューリスティック手法を利用する必要がある。そこで、シェア配送問題をスタイナー木問題に帰着させる方法を提案した。これにより、スタイナー木問題に対する既存手法を利用することが出来る。また、Prunded-MST等の4種類のスタイナー木問題に対する既存のヒューリスティックアルゴリズムについて、シェア配送問題に対する適用可能性を調べるために計算機上で比較実験を行った。シェア配送問題をスタイナー木問題に帰着させる場合得られる解がシェア配送問題の制約条件を満たすことは得られるスタイナー木の最適性を利用している。すなわちヒューリスティクスを用いた場合制約条件を満たすこと(実行可能性)を保障できない。そのため、評価指標としては近似度、実行可能性を用いた。各種アルゴリズムのシェア配送問題への適用性に対する知見を得た。