信頼されないコンピューティングノードによって実行された作業の検証
信頼されないコンピューティングノードによって実行された作業を検証する技法を提供する。中央コンピューティングシステムは、第１の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき第１計算を決定する。中央コンピューティングシステムは、第２の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき同等の第２計算を作るために第１計算に適用される変換関数をも決定する。中央コンピューティングシステムは、第１の信頼されないコンピューティングノードに第１計算を割り当て、変換関数を秘密に保ちながら、第２の信頼されないコンピューティングノードに第２計算を割り当てる。中央コンピューティングシステムは、第１計算の第１結果および第２計算の第２結果を受け取る。中央コンピューティングシステムは、第１の信頼されないコンピューティングノードおよび第２の信頼されないコンピューティングノードによって実行された作業を検証するために第１結果および第２結果を分析する。
【発明の詳細な説明】
【背景技術】
【０００１】
多数のコンピューティングノードにまたがる分散大規模計算が、ますます人気のあるものになってきた。そのような大規模計算の分散化は、そうでなければ単一のコンピューティングシステムまたは少数のコンピューティングシステムの処理リソースを越える可能性がある複雑な問題を解くことを可能にする。一般に、中央コンピューティングシステムは、大規模計算の一部を各コンピューティングノードに供給する。そしてコンピューティングノードは、それに割り当てられた部分を実行し、結果を中央コンピューティングシステムに返す。その後、中央コンピューティングシステムは、コンピューティングノードからのさまざまな結果を処理して、大規模計算に対する全体的な解を判定する。
【０００２】
１つの一般的な手法は、大規模計算の諸部分を、一般大衆から採用されたボランティアに分配することである。ボランティアは、彼らのコンピュータが分散システムのコンピューティングノードとして働くことを可能にする。したがって、中央コンピューティングシステムは、ボランティアのコンピューティングノードのそれぞれに、大規模計算のうちの実行すべき部分を供給する。この手法は、ノードがボランティアによって使用中ではない時またはボランティアが彼らのコンピューティングノードの処理リソースのすべてを利用しているのではない時に、コンピューティングノードの処理リソースの利用を可能にする。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
公衆からのボランティアの使用は、処理リソースへの低コストアクセスを提供するが、複数の短所がある。第１に、大規模計算の一部を実行しつつあるコンピューティングノードは、ボランティアノードなので、中央コンピューティングシステムの視点からは信頼されないものである。したがって、コンピューティングノードが、解かれるべき問題のプログラムコード内にバグを導入すること、ユーザエラー、外部データの誤構成、または他の類似する情況の結果として、図らずも誤りを犯す可能性がある。あるいは、コンピューティングノードが、割り当てられた計算に対する誤った解を提供することによって、または別のコンピューティングノードから結果を盗み、これらの結果をそれ自体の結果として提供することによって、詐欺を試みることができる。
【０００４】
いくつかのシステムは、そのような詐欺を防ぐことを試みて、暗号化およびディジタル署名などのセキュリティ手段を提供する。しかし、そのような手段は、ある種の誤りまたは洗練された詐欺を検出することができない。たとえば、相手方が、進行中の計算に割り込み、いくつかの値を変更し、従来の暗号化およびディジタル署名が検出できない形で計算を継続することを可能にすることができる。
【課題を解決するための手段】
【０００５】
本明細書で開示される例示的実施形態は、中央コンピューティングシステムが中央コンピューティングシステムに結合された複数の信頼されないコンピューティングノードによって実行された作業を検証する方法およびコンピュータプログラム製品に関する。中央コンピューティングシステムは、第１の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき第１計算を決定する。中央コンピューティングシステムは、第２の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき同等の第２計算を作るために第１計算に適用される変換関数をも決定する。中央コンピューティングシステムは、第１の信頼されないコンピューティングノードによって実行されるために第１計算を割り当て、変換関数を秘密に保ちながら、第２の信頼されないコンピューティングノードによって実行されるために第２計算を割り当てる。中央コンピューティングシステムは、第１計算の第１結果を第１の信頼されないコンピューティングノードから、および第２計算の第２結果を第２の信頼されないコンピューティングノードから受け取る。中央コンピューティングシステムは、第１の信頼されないコンピューティングノードおよび第２の信頼されないコンピューティングノードによって実行された作業を検証するために第１結果および第２結果を分析する。
【０００６】
本明細書で開示される例示的実施形態は、コンピューティングシステムに関する。このコンピューティングシステムは、プロセッサと、データベースと、計算生成モジュールと、変換関数モジュールと、受取モジュールと、分析モジュールとを含む。計算生成モジュールは、第１の信頼されないコンピューティングノードによって実行されるべき第１計算を生成する。変換関数モジュールは、同等の第２計算を作るために第１計算に適用される変換関数を生成するか入手する。第２計算は、第２の信頼されないコンピューティングノードによって実行されるべきものである。割当てノードは、第１の信頼されないコンピューティングノードによって実行されるために第１計算を割り当て、変換関数を秘密に保ちながら、第２の信頼されないコンピューティングノードによって実行されるために第２計算を割り当てる。受取モジュールは、第１計算の第１結果を第１の信頼されないコンピューティングノードから、および第２計算の第２結果を第２の信頼されないコンピューティングノードから受け取る。分析モジュールは、第１の信頼されないコンピューティングノードおよび第２の信頼されないコンピューティングノードによって実行された作業を検証するために第１結果および第２結果を分析する。
【０００７】
前述の概要は、例示的であるのみであって、いかなる形でも限定的であることは意図されていない。上で説明された例示的態様、実施形態、および特徴に加えて、さらなる態様、実施形態、および特徴が、図面および次の詳細な説明を参照することによって明白になる。
【図面の簡単な説明】
【０００８】
【図１】分散コンピューティングシステムの例示的実施形態を示す概略図である。
【図２】図１の分散コンピューティングシステムの中央コンピューティングシステムの例示的実施形態を示す図である。
【図３】信頼されないコンピューティングノードによって実行された作業を検証する方法の例示的実施形態を示す流れ図である。
【図４】信頼されないコンピューティングノードによって実行された作業を検証する方法の代替実施形態を示す流れ図である。
【図５】本開示による信頼されないコンピューティングノードによって実行された作業を検証するための例のコンピューティングデバイスを示す図である。
【発明を実施するための形態】
【０００９】
次の詳細な説明では、次の詳細な説明の一部を形成する添付図面を参照する。図面では、文脈がそうではないと示さない限り、類似する記号が、通常は類似するコンポーネントを識別する。この詳細な説明、図面、および特許請求の範囲で説明される例示的実施形態は、限定的であることを意図されていない。本明細書で提示される主題の趣旨または範囲から逸脱せずに、他の実施形態を利用することができ、他の変更を行うことができる。本明細書で全体的に説明され図面に示された本開示の諸態様を、さまざまな異なる構成で配置し、置換し、組み合わせ、分離し、設計でき、そのすべてが本明細書で明示的に企図されることが、たやすく理解されるであろう。
【００１０】
本明細書で開示される実施形態は、分散コンピューティングシステムに関する。分散コンピューティングシステムは、中央コンピューティングシステムに動作可能に結合された複数の信頼されないコンピューティングノードを含む。中央コンピューティングシステムは、複数の信頼されないコンピューティングノードの処理リソースを利用して、一般に大量の処理リソースを必要とする大規模複雑計算を実行するのを助ける。
【００１１】
複数の信頼されないコンピューティングノードは、計算の少なくとも一部を実行できる処理リソースを有する任意のタイプのコンピューティングシステムとすることができる。例は、デスクトップコンピュータ、ラップトップコンピュータ、携帯電話機、およびＰＤＡを含むが、これらに限定はされない。複数の信頼されないコンピューティングノードは、中央コンピューティングシステムがそれらのコンピューティングノードの動作に対する直接制御を有しないので、中央コンピューティングシステムの視点からは信頼されない。
【００１２】
したがって、本明細書で開示される実施形態は、中央コンピューティングシステムが、複数の信頼されないコンピューティングノードによって実行された作業を検証する機構を提供する。本明細書で開示される実施形態は、偽造者またはたかり屋である信頼されないコンピューティングノードに対して防御する。偽造者とは、実際には割り当てられた作業を行わない時にそれを行うふりをするノードであり、たかり屋は、それ自体または別のノードによって以前に実行された作業をコピーすることを試みる。破壊者は、悪い結果を完全な計算に注入することを試みる、一種の偽造者である。したがって、偽造者およびたかり屋は、詐欺的な無効な情報を中央コンピューティングシステムに提供する場合がある。
【００１３】
さらに、本明細書で開示される実施形態は、複数の信頼されないコンピューティングノードによる共謀に対して防御する。より詳細に説明されるように、信頼されないコンピューティングノードによって実行されるべき異なるが同等の計算を提供することによって、詐欺的な無効な結果をもたらすために一緒に働く２つのノードの能力が、減らされる。
【００１４】
一実施形態によれば、中央コンピューティングシステムは、信頼されないコンピューティングノードが実行を助けなければならない第１計算を決定する。一般に、第１計算は、第１の信頼されないコンピューティングノードによって実行される。第１計算を、計算コンポーネントに分割することができ、各サブセットは、１つの信頼されないコンピューティングノードによって実行される。
【００１５】
共謀、たかり、または偽造に対して保護するために、中央コンピューティングシステムは、同等の第２計算を作るために第１計算に適用される変換関数をも決定する。変換関数は、第２計算を第１計算と同等にする任意の関数である。したがって、同等な計算は、変換関数が除去されるときに、第１計算と実質的に同一の計算である。変換関数の例に加えて、さらなる詳細を、下で提供する。一般に、同等の第２計算は、第２の信頼されないコンピューティングノードによって実行される。変換関数を、複数の変換関数コンポーネントを含む変換空間から選択することができる。
【００１６】
その後、中央コンピューティングシステムは、第１計算を第１の信頼されないコンピューティングノードに割り当て、第２計算を第２の信頼されないコンピューティングノードに割り当てることができ、その結果、両方の計算を実行できるようになる。詐欺または共謀に対して保護するために、第１および第２の信頼されないコンピューティングノードを、ランダムに選択し、割り当てることができる。さらに、同等の第２計算を作るのに使用される変換関数は、追加の保護手段として、第１および第２の信頼されないコンピューティングノードから秘密に保たれる。
【００１７】
計算が、信頼されないコンピューティングノードによって実行された後に、第１計算の第１結果を、第１の信頼されないコンピューティングノードから受け取ることができる。第２計算の第２結果も、第２の信頼されないコンピューティングノードから受け取ることができる。
【００１８】
第１および第２の結果を分析して、第１および第２の信頼されないコンピューティングノードによって実行された作業を検証することができる。すなわち、結果の分析は、ノードの一方または両方がたかり屋または偽造者であるかどうか、あるいは２つのノードが共謀して詐欺的な無効な結果を提供したかどうかを判定するのを助ける。この分析は、第２結果から変換関数を除去し、その後、第１結果と第２結果とを比較することができる。第２結果からの変換の除去が、通常は変換関数の逆関数を第２結果に適用することによって実行されることを了解されたい。第２結果への変換の逆のこの適用は、以下でより詳細に説明するように、２つの結果を実質的に同一にするので、結果は、結果が有効である場合には一般に同一であり、結果の一方または両方が無効である場合には一般に異なる。詐欺に対するさらなる保護手段として、信頼されないコンピューティングノードのヒストリカル信頼性を、ヒストリカルデータのデータベースを調べることによって分析することができる。さらに、１つまたは複数の確率関数を結果に適用して、結果が有効である確率を判定することができる。
【００１９】
本開示のそれぞれの態様の複数の例示的実施形態を、下で例として添付図面を参照して与える。図１は、中央コンピューティングシステム１１０ならびに複数の信頼されないコンピューティングノード１３０、１４０、１５０、および１６０を含む分散コンピューティングシステム１００の例示的実施形態の概略図である。図１は、任意の追加の個数の信頼されないコンピューティングノード１７０（省略記号によって示される）を分散コンピューティングシステム１００に含めることができることをも示す。当業者は、図１に示されたものとは異なる個数の信頼されないコンピューティングノードがあってもよいことを了解するであろう。多くの実施形態では、数千個または数百万個の信頼されないコンピューティングノードがあってもよい。
【００２０】
中央コンピューティングシステム１１０を、ネットワーク１２０によって、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０に結合することができる。図１に示されているように、中央コンピューティングシステム１１０および信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０は、ネットワーク１２０を介して互いに両方向で通信することができる。ネットワーク１２０は、中央コンピューティングシステム１１０または信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０と互換の任意のネットワークとすることができ、例として、衛星ネットワーク、８０２．１１ネットワーク、パーソナルコンピュータネットワーク（たとえば、ＬＡＮ、ＷＡＮ）、無線ネットワーク（たとえば、Ｂｌｕｅｔｏｏｔｈ、ＷｉＦｉ）、セルラネットワーク、電話網（たとえば、地上の通信線またはＰＳＴＮ）、データネットワーク、インターネット、または類似物、あるいはその任意の組合せを含むことができる。
【００２１】
１つの例示的実施形態では、中央コンピューティングシステム１１０は、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０によって少なくとも部分的に実行されるべき大規模で通常は複雑な計算を生成する。以下でより詳細に説明するように、中央コンピューティングシステム１１０は、第１計算を生成し、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０のうちのいくつかが実行するために、第１計算の一部をネットワーク１２０を介して供給することができる。中央コンピューティングシステム１１０は、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０のうちのいくつかが実行するために、秘密の変換関数に基づいて同等の第２計算をも生成することができる。
【００２２】
信頼されないコンピューティングノード１３０、１４０、１５０、および１６０は、それぞれ処理リソース１３５、１４５、１５５、および１６５を含む。処理リソース１３５、１４５、１５５、および１６５は、コンピューティングノード１３０、１４０、１５０、および１６０が第１計算もしくは第２計算またはこれらの計算の一部を実行することを可能にする、プロセッサと任意の他のコンピュータハードウェアおよび／またはソフトウェアとを表す。また、信頼されないコンピューティングノード１７０のいずれもが、第１計算または第２計算を実行するためにプロセッサおよび他の処理リソースを含むことに留意されたい。
【００２３】
図２に、中央コンピューティングシステム１１０の例示的実施形態ならびに分散コンピューティングシステム１００のより詳細な図を示す。図２では、ネットワーク１２０が省略され、その結果、この図の追加の特徴を、より明瞭に見られるようになっている。図示されているように、中央コンピューティングシステム１１０は、これからより詳細に説明される、さまざまな動作モジュールおよびデータベースを含む。本明細書で開示される実施形態から注意をそらさないようにするために、結合されるものとして図示されてはいないが、中央コンピューティングシステム１１０のさまざまな動作モジュールおよびデータベースを、コンピュータバス、他の配線、または環境が保証するときの無線接続など、任意の妥当な手段によって互いに結合できることを理解されたい。
【００２４】
図示されているように、中央コンピューティングシステム１１０は、プロセッサ２１０を含む。プロセッサ２１０は、任意の妥当なプロセッサとすることができ、動作中には、中央コンピューティングシステム１１０がさまざまな動作を実行することを可能にする。いくつかの実施形態では、プロセッサ２１０に、中央コンピューティングシステム１１０のさまざまな動作モジュールによってアクセスして、モジュールに処理リソースを与えることができる。他の実施形態では、動作モジュールは、代替プロセッサへのアクセスを有することができる。
【００２５】
中央コンピューティングシステム１１０は、データベース２２０をも含む。データベース２２０は、任意のタイプの妥当な不揮発性メモリまたは揮発性メモリとすることができる。１つの例示的実施形態では、データベース２２０は、ヒストリ２２５を含むことができる。ヒストリ２２５は、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０によって中央コンピューティングシステム１１０に供給された過去の結果を含むことができる。以下でより詳細に説明するように、ヒストリ１２５を中央コンピューティングシステム１１０によって使用して、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０の信頼性を判定することができる。データベース２２０は、中央コンピューティングシステム１１０内に含まれるものとして図示されているが、いくつかの実施形態では、データベース２２０を、中央コンピューティングシステム１１０からアクセス可能でありながら中央コンピューティングシステム１１０の外部とすることができる。
【００２６】
計算生成モジュール２３０も、中央コンピューティングシステム１１０に含まれる。計算生成モジュール２３０は、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０のうちの１つまたは複数などの、１つまたは複数の信頼されないコンピューティングノードによって実行されるべき第１計算２８０を生成することができる。第１計算２８０は、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０が実行を助けることを中央コンピューティングシステム１１０が望む任意の計算とすることができる。いくつかの例示的実施形態では、第１計算２８０を、１つまたは少数の信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０によって解くことができる単一の問題とすることができる。しかし、第１計算２８０は、一般に、複数の部分に分解され、計算のために多数の信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０に分配される、大規模で複雑な問題である。たとえば、第１計算２８０を、第１計算コンポーネント２８０ａ、２８０ｂ、および図２で省略記号によって示されているように潜在的に任意の個数の追加の第１計算コンポーネント２８０ｃに分割することができる。
【００２７】
中央コンピューティングシステム１１０は、変換関数モジュール２４０を含む。一実施形態では、変換関数モジュール２４０は、変換関数２４５を生成することができる。変換関数２４５は、一般に、変換関数２４５が第１計算２８０に適用される時に、第１計算２８０と同等の第２計算２９０が作られる形で第１計算２８０に関連する。したがって、変換関数２４５は、一般に、第１計算２８０に関連する問題のタイプに基づいて選択される。変換関数２４５が、変換自体および変換関数の逆関数を含むことを了解されたい。
【００２８】
もう１つの実施形態では、変換関数モジュール２４０は、中央コンピューティングシステム１１０のユーザまたは別のコンピューティングシステムから変換関数を入手することができる。そのような実施形態では、ユーザまたは他のコンピューティングシステムは、変換関数を変換関数モジュール２４０に供給することができる。代替案では、ユーザまたは他のコンピューティングシステムは、変換関数モジュール２４０に、使用できるさまざまな変換関数を含む、ある変換テンプレートを選択させ、検証させ、または調整させることができる。したがって、変換関数モジュール２４０が、変換関数を生成することができ、あるいは、変換関数モジュール２４０が、ユーザまたは別のコンピューティングシステムから変換関数を入手することができることを了解されたい。たとえば、第１計算２８０が、各次元が複雑、近似的に連続、または他の形で非常に可変である空間解釈を扱う問題に関連すると仮定する。そのような第１計算２８０は、線形の変換関数２４５を示唆する。たとえば、Ｘが３Ｄ形状の集合であり、第１計算２８０が、Ｘに含まれる形状の総体積を計算することであると仮定する。すると、変換関数２４５を、線形変換の空間から選択することができる。
【００２９】
述べたように、第１計算２８０への変換関数２４５の適用は、第１計算２８０と同等な第２計算２９０を作る。前に述べたように、同等な問題または同等な計算とは、変換関数２４５が除去された時に、第１の問題または第１の計算と実質的に同一の問題または計算である。単純な線形変換を使用して、この点を示すことができる。たとえば、第１計算２８０が、１＋１という単純な式であったと仮定する。さらに、変換関数２４５が、ｆ（ｘ）＝ｘ＊１００という線形変換であったと仮定する。式１＋１に適用されるときに、１００＋１００という同等の第２計算２９０が作られるはずである。すぐにわかるように、１＋１の結果は２であり、１００＋１００の結果は２００である。この線形変換の逆を結果２００に適用することは、第２計算２９０に２という結果を与え、これは、第１計算２８０の２という結果と実質的に同一である。単純な式および単純な線形変換が、例示を簡単にするために使用されたが、より複雑な変換をより複雑な問題に対して使用できることを了解されたい。前に述べたように、第１計算２８０のタイプは、一般に、どのタイプの変換関数２４５を同等の第２計算２９０を作るのに使用できるのかを規定する。
【００３０】
１つの例示的実施形態では、変換関数２４５を、複数の変換関数コンポーネント２４５ａ、２４５ｂ、および図２で省略記号によって示されように潜在的に任意の個数の追加の変換関数コンポーネント２４５ｃに分割できる変換空間とすることができる。そのような実施形態では、変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃのうちの任意の１つを第１計算２８０に適用して、同等の第２計算２９０を作ることができる。
【００３１】
第１計算２８０が複数の第１計算コンポーネント２８０ａ、２８０ｂ、および２８０ｃに分割される実施形態では、変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃのうちの任意の１つを特定の第１計算コンポーネントサブセット２８０ａ、２８０ｂ、および２８０ｃに適用して、第２計算２９０を作ることができる。たとえば、変換関数サブセット２４５ｂを第１計算コンポーネントサブセット２８０ａに適用して、同等の第２計算２９０を作ることができる。後の時に、変換関数サブセット２４５ｂを第１計算サブセット２８０ｂに適用して、同等の第２計算２９０を作ることができる。さらに後の時に、変換関数サブセット２４５ａを第１計算コンポーネントサブセット２８０ａに適用して、同等の第２計算２９０を作ることができる。したがって、変換関数空間の変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃのうちの任意の１つを使用して、同等の第２計算２９０を作ることができる。
【００３２】
中央コンピューティングシステム１００は、さらに、割当てモジュール２５０を含む。割当てモジュール２５０は、第１計算１８０および第２計算２９０を実行するために、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０のうちの２つをランダムに割り当てることができる。２つの信頼されないコンピューティングノード、このケースでは信頼されないコンピューティングノード１３０および１４０をランダムに選択しまたは割り当てることによって、２つの信頼されないコンピューティングノードが互いに共謀し、または一方のコンピューティングノードに他方のコンピューティングノードからの結果を盗ませる可能性が、減らされる。
【００３３】
図示の実施形態では、信頼されないコンピューティングノード１３０は、第１計算２８０を実行するために、割当てモジュール２５０によってランダムに割り当てられる。計算全体またはより大きくより複雑な計算のサブセットのいずれであれ、第１計算２８０を、図２に示されているように、信頼されないコンピューティングノード１３０に供給することができる。次に、信頼されないコンピューティングノード１３０は、処理リソース１３５を使用して、第１計算２８０を少なくとも部分的に実行することができる。
【００３４】
割当てモジュール２５０は、同等の第２計算２９０を実行するために、信頼されないコンピューティングノード１４０をランダムに割り当てることができる。第２計算２９０を、図２に示されているように信頼されないコンピューティングノード１４０に供給することができる。信頼されないコンピューティングノード１４０は、処理リソース１４５を使用して、第２計算２９０を少なくとも部分的に実行することができる。
【００３５】
追加の保護手段として、変換関数２４５を、信頼されないコンピューティングノード１３０および１４０から秘密に保つことができる。了解されるように、信頼されないコンピューティングノード１３０または１４０のいずれかが変換関数２４５のアイデンティティを知った場合には、信頼されないコンピューティングノード１３０または１４０の一方または両方が第１計算２８０および第２計算２９０の解が何であるべきなのかを推測することを試みることが、はるかに簡単になるはずである。変換関数２４５を秘密に保つことによって、無効な結果が信頼されないコンピューティングノード１３０または１４０によって返される可能性が、減らされる。
【００３６】
第１計算２８０が、前に述べたように複数の第１計算コンポーネント２８０ａ、２８０ｂ、および２８０ｃに分割される実施形態では、割当てモジュール２５０は、第１計算コンポーネント２８０ａ、２８０ｂ、および２８０ｃのうちのどれが、信頼されないコンピューティングノード１３０などのランダムに選択された信頼されないコンピューティングノードに割り当てられるのかを、ランダムに選択することができる。同様に、変換関数２４５が、複数の変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃを有する変換空間である実施形態では、割当てモジュール２５０または変換関数モジュール２４０は、変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃのうちのどれが、同等の第２計算２９０を生成するのに使用されるべきなのかをランダムに選択することができる。第１計算サブセット２８０ａ、２８０ｂ、または２８０ｃおよび変換関数サブセット２４５ａ、２４５ｂ、または２４５ｃのランダム選択は、この例では信頼されないコンピューティングノード１３０または１４０による共謀に対する追加のセキュリティを提供する。
【００３７】
受取モジュール２６０は、この例では、信頼されないコンピューティングノード１３０から第１計算２８０の第１結果２８５を受け取ることができ、信頼されないコンピューティングノード１４０から第２計算２９０の第２結果２９５をも受け取ることができる。
【００３８】
前に述べたように、信頼されないコンピューティングノード１３０および１４０（ならびに信頼されないコンピューティングノード１５０、１６０、および１７０）は、それらが中央コンピューティングシステム１１０によって制御されないので、信頼されない。したがって、中央コンピューティングシステム１１０は、信頼されないコンピューティングノード１３０および１４０によって返された結果が有効であるかどうかを知らない。無効な結果を返すことによる結果の偽造または別の信頼されないコンピューティングノードによって実行された作業をコピーすることによるたかりに備えるために、中央コンピューティングシステム１１０は、分析モジュール２７０を含む。分析モジュール２７０は、第１結果２８５および第２結果２９５を分析して、信頼されないコンピューティングノード１３０および１４０によって実行された作業を検証することができる。
【００３９】
１つの例示的実施形態では、分析モジュール２７０は、第２結果２９５から変換関数２４５を除去することによって、第１結果２８５および第２結果２９５を分析することができる。次に、分析モジュール２７０は、第１結果２８５および第２結果２９５をお互いと比較することができる。線形変換の例に関して前に上で説明したように、第２結果２９５からの変換関数２４５の除去は、信頼されないコンピューティングノード１３０および１４０によって、第１計算２８０および第２計算２９０が正しく実行され、有効な結果が供給されたときに、第２結果２９５が第１結果２８５と実質的に同一となるようにする。したがって、第１結果２８５と第２結果２９５とがお互いと一致する場合には、信頼されないコンピューティングノード１３０および１４０が有効な結果を提供した可能性が高い。信頼されないコンピューティングノード１３０と１４０との両方が無効な同等の結果を提供する形で共謀する可能性や、一方の信頼されないノードが他方の信頼されないノードの結果と一致する詐欺的結果を提供する可能性は、非常に低い。
【００４０】
その一方で、分析モジュール２７０が、比較の後に第１結果２８５と第２結果２９５との間の差を見つける場合には、信頼されないコンピューティングノード１３０および１４０のうちの少なくとも１つ、おそらく信頼されないコンピューティングノード１３０と１４０との両方が、無効な結果を提供したことを意味する可能性がある。その後、これらの結果を中央コンピューティングシステム１１０によって疑わしいと見なすことができる。
【００４１】
１つの例示的実施形態では、第１結果２８５および／または第２結果２９５が、一連の中間結果を含む場合がある。たとえば、第１結果２８５が、一連の第１中間結果２８５ａ、２８５ｂ、および図２で省略記号によって示されるように潜在的に任意の個数の追加の中間結果２８５ｃを含む場合がある。同様に、第２結果２９５が、一連の第２中間結果２９５ａ、２９５ｂ、および図２で省略記号によって示されるように潜在的に任意の個数の追加の中間結果２９５ｃを含む場合がある。そのような実施形態では、第１計算２８０および／または第２計算２９０を変更して、完全な第１結果２８５および第２結果２９５が判定され、中央コンピューティングシステム１１０に返される前に、中間結果を判定し、中央コンピューティングシステム１１０に返すことを可能にすることができる。
【００４２】
分析モジュール２７０は、第１中間結果２８５ａ、２８５ｂ、および２８５ｃならびに第２中間結果２９５ａ、２９５ｂ、および２９５ｃを、たとえばそれらを比較して信頼されないコンピューティングノード１３０および１４０が無効な結果を供給したかどうかを判定することによって、分析することができる。第１中間結果２８５ａ、２８５ｂ、および２８５ｃが第２中間結果２９５ａ、２９５ｂ、および２９５ｃと一致する場合には、それらの結果が有効である可能性が高い。第１中間結果２８５ａ、２８５ｂ、および２８５ｃが第２中間結果２９５ａ、２９５ｂ、および２９５ｃと一致しない場合には、それらの結果が無効である可能性が高い。中間結果の使用は、信頼されないコンピューティングノード１３０および１４０が、両方が同等の無効な中間結果を供給する形で共謀しまたは一方の信頼されないノードが他方の信頼されないノードの中間結果と一致する詐欺的中間結果を提供する可能性が非常に低いので、詐欺および共謀に対する追加の保護を提供する。
【００４３】
１つの例示的実施形態では、変換関数２４５の逆関数を、第２中間結果２９５ａ、２９５ｂ、および２９５ｃのそれぞれに適用することができる。そのような適用は、第２中間結果２９５ａ、２９５ｂ、および２９５ｃを対応する第１中間結果２８５ａ、２８５ｂ、および２８５ｃと同等にするはずである。そのような実施形態では、変換関数２４５が、単一の関数である必要がないことに留意されたい。たとえば、変換関数２４５を、それぞれ、第２計算２９０を作るために第１計算２８０に、第２中間結果２９５ａ、２９５ｂ、および２９５ｃに、ならびに第２結果２９５に適用される多重の全単射（multiple bijection）とすることができる。
【００４４】
述べたように、分析モジュール２７０は、第１計算２８０の第１結果２８５および第２計算２９０の第２結果２９５を分析して、それらがおそらく有効であるかどうかを判定する。しかし、分析モジュール２７０によって実行される分析が、個々の信頼されないコンピューティングノードの信頼性を判定できないことがあり得る。たとえば、信頼されないコンピューティングノード１３０からの第１結果２８５が、信頼されないコンピューティングノード１４０からの第２結果２９５と一致しない場合に、これは、必ずしも、信頼されないコンピューティングノード１３０が不正直に詐欺的結果を供給したことを意味しない。信頼されないコンピューティングノード１４０が詐欺的結果を供給したか、または、信頼されないコンピューティングノード１３０が、第１計算２８０を実行する時に本当に間違ったことがあり得る。
【００４５】
この例では信頼されないコンピューティングノード１３０または１４０のどれが、詐欺的結果または無効な結果を供給した可能性があるのかを判定するのを助けるために、第１結果２８５および第２結果２９５は、データベース２２０に供給され、ヒストリ２２５に含められる。前に述べたように、ヒストリ２２５は、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０によって供給された以前の計算からのすべてのヒストリカル結果を含むことができる。
【００４６】
分析モジュール２７０は、ヒストリ２２５にアクセスして、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０の信頼性を判定することができる。信頼されないコンピューティングノード１３０が、その結果が一致する信頼されないコンピューティングノードの対に含まれることのヒストリを有する場合には、現在の不一致が、信頼されないコンピューティングノード１４０によって引き起こされたか、本当の間違いであると仮定することができる。その一方で、信頼されないコンピューティングノード１３０が、その結果が一致しない信頼されないコンピューティングノードの多数の対に含まれることのヒストリを有する場合には、信頼されないコンピューティングノード１３０を、疑問視することができ、その結果を無視することができる。類似する分析を、信頼されないコンピューティングノード１４０および実際にすべての信頼されないコンピューティングノードによって供給された結果に対して実行することができる。したがって、ヒストリ２２５の使用は、特定の信頼されないコンピューティングノードを信頼すべきかどうかを、その信頼されないコンピューティングノードのヒストリカル動作に基づいて検証するための追加のチェックを提供する。了解されるように、信頼されないコンピューティングノードは、そのヒストリ２２５に格納された結果の過半数が有効である場合には信頼できる可能性が高く、そのヒストリ２２５に格納された結果の過半数またはそのかなりの割合が無効である場合には信頼できる可能性が低い。
【００４７】
いくつかの実施形態では、第１計算２８０および／または第２計算２９０を、暗号化、ディジタル署名、または難読化などのさまざまなテクノロジを用いて補強することもできる。これらのテクノロジは、信頼されないコンピューティングノードによる改竄に対する追加の障壁を提供するために含めることができる。
【００４８】
中央コンピューティングシステム１１０が変換関数２４５を秘密に保った場合であっても、信頼されないコンピューティングノード１３０が、変換関数２４５を学習しまたは推測することが可能である場合がある。その場合には、信頼されないコンピューティングノード１３０は、無効な第１結果２８５を悪意を持って供給できる可能性があり、あるいは、第２結果２９５をより簡単にコピーし、この結果をそれ自体の結果として渡すことができる可能性がある。
【００４９】
あるいは、第１計算２８０が、信頼されないコンピューティングノード１３０が５０％超の確率で正しい答えを推測することを可能にするタイプのものである場合がある。そのような場合には、信頼されないコンピューティングノード１３０は、第１計算２８０の実行を止めることができ、正しい結果となる大きい可能性のゆえに、毎回結果を単純に推測することができる。
【００５０】
そのような情況を検出するのを助けるために、分析モジュール２７０は、確率モジュール２７５を含むことができる。確率モジュールは、第１結果２８５および第２結果２９５に１つまたは複数の確率関数を適用して、これらの結果が有効であるかどうかならびに信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０が信頼できるものであるかどうかを判定することができる。したがって、第１結果２８５および第２結果２９５が正しく判定され、単に正しく推測されたのでも盗まれたのでもないことの確率の判定は、中央コンピューティングシステム１１０が、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０の信頼性を検証する追加の形を提供する。いくつかの確率関数の例を、これから述べる。
【００５１】
ある大きいタスク（第１計算２８０など）が、多数のｘに関するｆ（ｘ）の計算を必要とすると仮定する。ｆ：Ｘ→Ｙであるものとする。ｘが一様に分布する確率変数であると考えられる場合に、ｆ（ｘ）の確率分布が狭過ぎ、その結果、正しい値の推測が妥当と思われるようになる場合には、ｆは、結果ｙに加えて、ある中間状態ｓを出力するように変更される。したがって、ｆ（ｘ）＝（ｓ，ｒ）である。未知の真の結果を、ｙ１＝（ｓ，ｒ）を用いて表す。
【００５２】
εが、ノードが所有する背景情報であるものとする。ノードが作業を実行しない確率を、Ｐ（Ｅ（ｎ））によって表す。Ｅ（ｎ））の場合には、ノードｎは、作業を偽造することを試みている。この場合に、ノードが推測していると言う。正しい答えを推測する確率を、Ｐ（ｙ＝ｙ１｜ε）によって表す。
【００５３】
作業要求ｆ（ｘ）は、ある計算ノードｎに与えられる。それと同時に、別の作業要求ｆ（ｘ’）が生成される。ｆ（ｘ’）＝（ｓ’，ｒ’）であるものとする。ｘ’を選択するために、まず、ｘ’＝ｇ（ｘ）である場合に限ってｇ（ｓ）＝ｓ’かつｇ（ｒ）＝ｒ’になる、変換関数ｇ：Ｘ→Ｘを見つける。作業要求ｆ（ｘ’）は、別のノードｎ２に与えられ、変換ｇ∈Ｇが、秘密として保たれる。
【００５４】
Ｐ（ｎｉ（ｇ）｜ε）は、ノードｎｉが秘密の変換ｇを学習するか推測する確率であるものとする。ｇが、大きい空間から選択され、その秘密がセキュアに保たれる場合には、Ｐ（ｎｉ（ｇ）｜ε）は、小さくなる。
【００５５】
次に、両方のノードは、それに割り当てられた作業を実行すると主張し、結果ｙ＝（ｓ，ｒ）およびｙ１＝（ｓ’，ｒ’）を報告する。下の表１に、可能である、ノードの異なる結果のさまざまな確率を示す。言い換えると、さまざまな情況に関してｙ＝ｙ１がどうなるかを示す。
【００５６】
【表１】
表１
【００５７】
したがって、ｙがｙ１と等しくない確率は
【００５８】
【数１】
である。
【００５９】
図３は、信頼されないコンピューティングノードによって実行された作業を検証する方法３００の例示的実施形態の流れ図である。図示の実施形態では、方法３００ならびに本明細書で説明する他の方法およびプロセスは、処理ステップ、機能動作、イベント、および／または行為などとして説明することができ、ハードウェア、ソフトウェア、および／またはファームウェアによって実行できる、さまざまな機能ブロックまたはアクションを示す。方法３００は、ブロック３０２、３０４、３０６、３０８、３１０、および／または３１２によって示されるように、１つまたは複数の動作を含む。ブロック３０２では、第１の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき第１計算を決定する。たとえば、１つの例示的実施形態では、計算生成モジュール２３０が、信頼されないコンピューティングノード１３０などの第１の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき第１計算２８０を生成することができる。いくつかの実施形態では、第１計算２８０を、第１計算コンポーネント２８０ａ、２８０ｂ、および２８０ｃに分割することができる。
【００６０】
ブロック３０４では、第２の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき同等の第２計算を作るために第１計算に適用されるべき変換関数を決定する。たとえば、１つの例示的実施形態では、変換関数モジュール２４０は、第１計算２８０のタイプに基づいて、変換関数２４５を生成することができる。もう１つの例示的実施形態では、変換関数モジュールは、コンピューティングシステム１１０のユーザまたは別のコンピューティングシステムから変換関数を入手することができる。変換関数２４５を、第１計算２８０に適用して、信頼されないコンピューティングノード１４０などの第２の信頼されないコンピューティングノードによって実行できる第２計算２９０を作ることができる。いくつかの実施形態では、変換関数２４５を、複数の変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃを含む変換空間とすることができる。
【００６１】
ブロック３０６では、第１計算を、第１の信頼されないコンピューティングノードに割り当て、ブロック３０８では、第２計算を、第２の信頼されないコンピューティングノードに割り当てる。第１の信頼されないコンピューティングノードおよび第２の信頼されないコンピューティングノードへの第１計算および第２計算の割当ては、それぞれ、第１および第２の信頼されないコンピューティングノードから変換関数を秘密に保ちながら行われる。たとえば、１つの例示的実施形態では、割当てモジュール２５０が、第１計算２８０を信頼されないコンピューティングノード１３０に割り当てることができ、第２計算２９０を信頼されないコンピューティングノード１４０に割り当てることができる。
【００６２】
ブロック３１０では、第１計算の第１結果を第１の信頼されないコンピューティングノードから受け取り、第２計算の第２結果を第２の信頼されないコンピューティングノードから受け取る。たとえば、１つの例示的実施形態では、受取モジュール２６０は、信頼されないコンピューティングノード１３０から第１結果２８５を受け取ることができ、信頼されないコンピューティングノード１４０から第２結果２９５を受け取ることができる。いくつかの実施形態では、第１結果２８５は、第１中間結果２８５ａ、２８５ｂ、および２８５ｃを含むことができる。第２結果２９５は、第２中間結果２９５ａ、２９５ｂ、および２９５ｃを含むことができる。
【００６３】
ブロック３１２では、第１結果および第２結果を分析して、信頼されないコンピューティングノードによって実行された作業を検証する。１つの例示的実施形態では、分析モジュール２７０は、第１結果２８５および第２結果２９５を分析して、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０によって実行された作業を検証することができる。この形で、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０の信頼性を判定することができる。
【００６４】
いくつかの実施形態では、分析モジュール２７０は、第２結果２９５から変換関数２４５を除去し、その後、第２結果２９５を第１結果２８５と比較する。結果が実施的に同一である場合には、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０が有効な結果を供給した可能性が高い。しかし、結果が異なる場合には、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０の一方または両方が無効な結果を供給した可能性が高い。
【００６５】
ヒストリカルデータベースにアクセスすることもでき、その結果、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０の実行の履歴を、以前に説明したように判定することができる。さらに、１つまたは複数の確率関数を結果に適用して、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０の信頼性を判定するのを助けることができる。
【００６６】
方法３００は、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０が、結果の推測または無効な結果の供給などの詐欺にかかわったかどうかを中央コンピューティングシステム１１０が判定するための機構を提供する。さらに、方法３００は、中央コンピューティングシステム１１０が、無効な結果を提供するための信頼されないコンピューティングノード１３０と信頼されないコンピューティングノード１４０との間の共謀を判定することを可能にする。
【００６７】
当業者は、上記ならびに本明細書で開示される他のプロセスおよび方法について、それらのプロセスおよび方法で実行される機能を、異なる順序で実施できることを了解するであろう。さらに、概要を示されたステップおよび動作は、例としてのみ提供され、ステップおよび方法の一部を、開示される実施形態の本質から逸脱せずに、オプションとし、より少数のステップおよび動作に組み合わせ、あるいは追加のステップおよび動作に拡張することができる。
【００６８】
図４は、信頼されないコンピューティングノードによって実行された作業を検証する代替の方法４００の例示的実施形態の流れ図である。方法４００は、ブロック４０２、４０４、４０６、４０８、４１０、４１２、４１４、４１６、および／または４１８によって示される１つまたは複数の動作を含む。ブロック４０２では、第１計算および変換関数コンポーネントを含む変換空間を選択する。たとえば、第１計算２８０を、計算生成モジュール２３０によって選択することができる。変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃを含む変換関数２４５を、第１計算２８０に基づいて変換関数モジュール２４０によって選択することができる。
【００６９】
ブロック４０４では、第１計算をコンポーネントに分割する。たとえば、第１計算２８０を、計算生成モジュール２３０によって第１計算コンポーネント２８０ａ、２８０ｂ、および２８０ｃに分割することができる。
【００７０】
ブロック４０６では、変換関数コンポーネントのうちの１つを、第１計算コンポーネントのうちの１つに適用するためにランダムに選択する。これが、第２計算を作る。たとえば、第１変換関数サブセット２４５ａをランダムに選択し、ランダムに選択された第１計算サブセット２８０ａに適用することができる。これは、第２計算２９０を作ることができる。
【００７１】
ブロック４０８では、第１計算サブセットおよび第２計算を実行するために、信頼されないコンピューティングノードの対をランダムに選択する。たとえば、割当てモジュール２５０は、第１計算サブセット２８０ａを実行するために信頼されないコンピューティングノード１３０を、第２計算２９０を実行するために信頼されないコンピューティングノード１４０をランダムに選択することができる。
【００７２】
ブロック４１０では、ランダムに選択された変換関数サブセットを秘密に保ちながら、第１計算サブセットが、第１の信頼されないコンピューティングノードに割り当てられ、第２計算が、第２の信頼されないコンピューティングノードに割り当てられる。たとえば、割当てモジュール２５０は、第１計算サブセット２８０ａを信頼されないコンピューティングノード１３０に割り当てることができ、第２計算２９０を信頼されないコンピューティングノード１４０に割り当てることができる。変換関数サブセット２４５ａは、信頼されないコンピューティングノードから秘密に保たれる。
【００７３】
ブロック４１２では、第１結果を第１の信頼されないコンピューティングノードから受け取り、第２結果を第２の信頼されないコンピューティングノードから受け取る。たとえば、受取モジュール２６０は、信頼されないコンピューティングノード１３０から第１結果２８５を受け取ることができ、信頼されないコンピューティングノード１４０から第２結果２９５を受け取ることができる。
【００７４】
ブロック４１４では、第１結果および第２結果を分析する。たとえば、分析モジュール２７０は、第１結果２８５および第２結果２９５を、前に説明した形のいずれかで分析することができる。
【００７５】
ブロック４１６では、第１結果および第２結果をデータベースに記録する。たとえば、第１結果２８５および第２結果２９５を、データベース２２０に記録することができる。結果を、ヒストリ２２５に追加することができ、前に説明したように信頼されないコンピューティングノードの信頼性を判定するのを助けるのに使用することができる。
【００７６】
判断ブロック４１８では、結果が有効であったかどうかを判定する。この判定は、前に説明したように、結果の比較、ヒストリカル分析、および確率関数の適用を使用して行うことができる。
【００７７】
結果が、有効である可能性が高いと判定される場合には（判断ブロック４１８のＹｅｓ）、この方法は、実行すべき他の計算がない場合に終了することができる。そうではなく、実行すべき他の計算がある場合には、この方法はブロック４０２に戻り、この方法が繰り返される。
【００７８】
結果が、有効である可能性が高くはないと判定される場合には（判断ブロック４１８のＮｏ）、この方法は、ブロック４０６に戻ることができ、ここで、第１および第２の信頼されないコンピューティングノードとは異なる、２つの新しい信頼されないコンピューティングノードを、ランダムに選択することができる。その後、方法４００の残りのブロックを実行して、新たに選択された信頼されないコンピューティングノードが有効な結果を供給するかどうかを判定することができる。たとえば、ブロック４０６に戻った後に、割当てモジュール２５０は、第１計算サブセット２８０ａを実行するために信頼されないコンピューティングノード１５０をランダムに選択することができ、第２計算２９０を実行するために信頼されないコンピューティングノード１６０をランダムに選択することができる。その後、方法４００の残りのブロックを実行することができる。
【００７９】
本開示は、さまざまな態様の例示として意図された、本願で説明される特定の実施形態に関して限定されてはならない。当業者が了解するように、その趣旨および範囲から逸脱せずに、多数の修正形態および変形形態を作ることができる。本明細書で列挙されるものに加えて、本開示の範囲に含まれる機能的に同等の方法および装置は、前述の説明から当業者には明白であろう。そのような修正形態および変形形態は、添付の特許請求の範囲の範囲に含まれることが意図されている。本開示は、添付の特許請求の範囲に与えられる同等物のすべての範囲に加えて、添付の特許請求の範囲の項目のみによって限定されなければならない。本開示が、もちろん変化することのできる特定の方法、試薬、化合物、合成物、または生体系に限定されてはならないことを理解されたい。本明細書で使用される用語法が、特定の実施形態を説明するためのみのものであって、限定的であることを意図されていないことをも理解されたい。
【００８０】
例示的実施形態では、本明細書で説明される動作、プロセスなどのいずれをも、コンピュータ可読媒体に格納されたコンピュータ可読命令として実施することができる。コンピュータ可読命令を、モバイルユニット、ネットワーク要素、および／または任意の他のコンピューティングデバイスのプロセッサによって実行することができる。
【００８１】
システムの諸態様のハードウェア実施態様とソフトウェア実施態様との間には、区別がほとんど残されておらず、ハードウェアまたはソフトウェアの使用は、一般に（ある文脈でハードウェアとソフトウェアとの間の選択が重要になり得るという点で、必ずではないが）、コスト対効率のトレードオフを表す設計選択である。本明細書で説明されるプロセスおよび／またはシステムおよび／または他のテクノロジを実施できるさまざまな手段（たとえば、ハードウェア、ソフトウェア、および／またはファームウェア）があり、その上、好ましい手段は、それらのプロセスおよび／またはシステムおよび／または他のテクノロジが展開される文脈に伴って変化する。たとえば、実装者が、速度および正確さが主要であると判定する場合に、実装者は、主にハードウェア手段および／またはファームウェア手段を選ぶことができ、柔軟性が主要である場合には、実装者は、主にソフトウェア実施態様を選ぶことができ、あるいは、やはりその代わりに、実装者は、ハードウェア、ソフトウェア、および／またはファームウェアのある組合せを選ぶことができる。
【００８２】
前述の詳細な説明は、ブロック図、流れ図、および／または例の使用を介してデバイスおよび／またはプロセスのさまざまな実施形態を示した。そのようなブロック図、流れ図、および／または例が、１つまたは複数の機能および／または動作を含む限り、そのようなブロック図、流れ図、または例に含まれる各機能および／または各動作を、個別におよび／または集合的に、広範囲のハードウェア、ソフトウェア、ファームウェア、または事実上すべてのその組合せによって実施できることが、当業者によって理解されるであろう。一実施形態では、本明細書で説明される主題の複数の部分を、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、ディジタル信号プロセッサ（ＤＳＰ）、または他の集積フォーマットを介して実施することができる。しかし、当業者は、本明細書で開示される実施形態のいくつかの態様を、全体的にまたは部分的に、集積回路内で、１つまたは複数のコンピュータ上で動作する１つまたは複数のコンピュータプログラムとして（たとえば、１つまたは複数のコンピュータシステム上で動作する１つまたは複数のプログラムとして）、１つまたは複数のプロセッサ上で動作する１つまたは複数のプログラムとして（たとえば、１つまたは複数のマイクロプロセッサ上で動作する１つまたは複数のプログラムとして）、ファームウェアとして、または事実上すべてのそれらの組合せとして同等に実施できることと、回路網の設計ならびに／あるいはソフトウェアおよびまたはファームウェアのコードの記述が、本開示を考慮すると当業者の技量に十分に含まれることとを認めるであろう。さらに、当業者は、本明細書で説明される主題の機構を、さまざまな形でプログラム製品として配布できることと、本明細書で説明される主題の例示的実施形態が、配布を実際に実行するのに使用される信号担持媒体の特定のタイプにかかわりなく適用されることとを了解するであろう。信号担持媒体の例は、フロッピディスク、ハードディスクドライブ、ＣＤ、ＤＶＤ、ディジタルテープ、コンピュータメモリ、その他などの記録可能型媒体と、ディジタル通信媒体および／またはアナログ通信媒体（たとえば、光ファイバケーブル、導波管、有線通信リンク、無線通信リンクなど）などの伝送型媒体とを含むが、これらに限定はされない。
【００８３】
当業者は、当技術分野で、デバイスおよび／またはプロセスを本明細書で示す形で記述し、その後、工学的実践を使用して、そのように記述されたデバイスおよび／またはプロセスをデータ処理システムに統合することが一般的であることを認めるであろう。すなわち、本明細書で説明されるデバイスおよび／またはプロセスの少なくとも一部を、妥当な量の実験を介してデータ処理システムに統合することができる。当業者は、通常のデータ処理システムが、一般に、システムユニットハウジング、ビデオディスプレイデバイス、揮発性メモリおよび不揮発性メモリなどのメモリ、マイクロプロセッサおよびディジタル信号プロセッサなどのプロセッサ、オペレーティングシステム、ドライバ、グラフィカルユーザインターフェース、およびアプリケーションプログラムなどの計算エンティティ、タッチパッドまたはタッチスクリーンなどの１つまたは複数の対話デバイス、ならびに／あるいはフィードバックループおよび制御モータ（たとえば、位置および／または速度を感知するフィードバック、コンポーネントおよび／または量を移動しかつ／または調整する制御モータ）を含む制御システムのうちの１つまたは複数を含むことを認めるであろう。通常のデータ処理システムを、一般にデータコンピューティング／通信および／またはネットワークコンピューティング／通信システムで見られるものなど、任意の適切な市販コンポーネントを利用して実施することができる。
【００８４】
本明細書で説明される主題は、時々、異なる他のコンポーネントに含まれるかこれに接続される異なるコンポーネントを示す。そのような図示のアーキテクチャが、単に例示であることと、実際に、同一の機能性を達成する多数の他のアーキテクチャを実施できることとを理解されたい。概念的な意味で、同一の機能性を達成するためのコンポーネントのすべての配置は、所望の機能性が達成されるように効果的に「関連付けられる」。したがって、特定の機能性を達成するために組み合わされる本明細書の任意の２つのコンポーネントを、アーキテクチャまたは中間コンポーネントにかかわりなく、所望の機能性が達成されるように互いに「関連付けられる」と見なすことができる。同様に、そのように関連付けられた任意の２つのコンポーネントを、所望の機能性を達成するために互いに「動作可能に接続される」または「動作可能に結合される」と見なすこともでき、そのように関連付けられ得る任意の２つのコンポーネントを、所望の機能性を達成するために互いに「動作可能に結合可能である」と見なすこともできる。動作可能に結合可能の特定の例は、物理的に嵌合可能なコンポーネントおよび／または物理的に相互作用するコンポーネント、ならびに／あるいは無線で相互作用可能なコンポーネントおよび／または無線で相互作用するコンポーネント、ならびに／あるいは論理的に相互作用するコンポーネントおよび／または論理的に相互作用可能なコンポーネントを含むが、これらに限定はされない。
【００８５】
図５に、本開示による分散コンピューティングシステム内の信頼されないコンピューティングノードによって実行された作業を検証するために配置された例のコンピューティングデバイス５００を示す。非常に基本的な構成５０２では、コンピューティングデバイス５００は、一般に、１つまたは複数のプロセッサ５０４およびシステムメモリ５０６を含む。メモリバス５０８を、プロセッサ５０４とシステムメモリ５０６との間で通信するのに使用することができる。
【００８６】
所望の構成に応じて、プロセッサ５０４を、マイクロプロセッサ（μＰ）、マイクロコントローラ（μＣ）、ディジタル信号プロセッサ（ＤＳＰ）、またはその任意の組合せを含むがこれらに限定はされない任意のタイプのプロセッサとすることができる。プロセッサ５０４は、レベル１キャッシュ５１０およびレベル２キャッシュ５１２などのキャッシングのもう１つのレベル、プロセッサコア５１４、およびレジスタ５１６を含むことができる。例のプロセッサコア５１４は、算術論理ユニット（ＡＬＵ）、浮動小数点ユニット（ＦＰＵ）、ディジタル信号処理コア（ＤＳＰコア）、またはその任意の組合せを含むことができる。例のメモリコントローラ５１８を、プロセッサ５０４と共に使用することもでき、あるいは、いくつかの実施態様では、メモリコントローラ５１８を、プロセッサ５０４の内部の部分とすることができる。
【００８７】
所望の構成に応じて、システムメモリ５０６を、揮発性メモリ（ＲＡＭなど）、不揮発性メモリ（ＲＯＭ、フラッシュメモリ、その他など）、またはその任意の組合せを含むがこれらに限定はされない任意のタイプのメモリとすることができる。システムメモリ５０６は、オペレーティングシステム５２０、１つまたは複数のアプリケーション５２２、およびプログラムデータ５２４を含むことができる。アプリケーション５２２は、図３の方法３００および図４の方法４００に関して説明されたものを含む本明細書で説明される機能を実行するように配置された検証アプリケーション５２６を含むことができる。プログラムデータ５２４は、信頼されないコンピューティングノードによって供給された結果を分析するのに有用である可能性がある分析情報５２８を含むことができる。いくつかの実施形態では、アプリケーション５２２を、本明細書で説明されるように信頼されないコンピューティングノードによって実行された作業を検証できるように、オペレーティングシステム５２０上でプログラムデータ５２４を用いて動作するように配置することができる。この説明された基本構成５０２は、図５では、内側の破線の中のコンポーネントによって示されている。
【００８８】
コンピューティングデバイス５００は、基本構成５０２と任意の必要なデバイスおよびインターフェースとの間の通信を容易にする追加の特徴または機能性ならびに追加のインターフェースを有することができる。たとえば、バス／インターフェースコントローラ５３０を使用して、基本構成５０２と１つまたは複数のデータストレージデバイス５３２との間のストレージインターフェースバス５３４を介する通信を容易にすることができる。データストレージデバイス５３２は、リムーバブルストレージデバイス５３６、ノンリムーバブルストレージデバイス５３８、またはその組合せとすることができる。リムーバブルストレージデバイスおよびノンリムーバブルストレージデバイスの例は、少数を挙げると、フレキシブルディスクドライブおよびハードディスクドライブ（ＨＤＤ）などの磁気ディスクデバイス、コンパクトディスク（ＣＤ）ドライブまたはディジタル多用途ディスク（ＤＶＤ）ドライブなどの光ディスクドライブ、ソリッドステートドライブ（ＳＳＤ）、およびテープドライブを含む。コンピュータ記憶媒体の例は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報のストレージのための任意の方法またはテクノロジで実施された、揮発性および不揮発性の、リムーバブルおよびノンリムーバブルの媒体を含むことができる。
【００８９】
システムメモリ５０６、リムーバブルストレージデバイス５３６、およびノンリムーバブルストレージデバイス５３８は、コンピュータ記憶媒体の例である。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、もしくは他のメモリテクノロジ、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）、もしくは他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、もしくは他の磁気ストレージデバイス、または所望の情報を格納するのに使用でき、コンピューティングデバイス５００によってアクセスできる任意の他の媒体を含むが、これらに限定はされない。すべてのそのようなコンピュータ記憶媒体を、コンピューティングデバイス５００の一部とすることができる。
【００９０】
コンピューティングデバイス５００は、さまざまなインターフェースデバイス（たとえば、出力デバイス５４２、周辺インターフェース５４４、および通信デバイス５４６）から基本構成５０２へのバス／インターフェースコントローラ５３０を介する通信を容易にするインターフェースバス５４０をも含むことができる。例の出力デバイス５４２は、グラフィックス処理ユニット５４８およびオーディオ処理ユニット５５０を含み、グラフィックス処理ユニット５４８およびオーディオ処理ユニット５５０は、１つまたは複数のＡ／Ｖポート５５２を介してディスプレイまたはスピーカなどのさまざまな外部デバイスと通信するように構成され得る。例の周辺インターフェース５４４は、シリアルインターフェースコントローラ５５４またはパラレルインターフェースコントローラ５５６を含み、シリアルインターフェースコントローラ５５４またはパラレルインターフェースコントローラ５５６は、入力デバイス（たとえば、キーボード、マウス、ペン、音声入力デバイス、タッチ入力デバイスなど）などの外部デバイスまたは他の周辺デバイス（たとえば、プリンタ、スキャナなど）と１つまたは複数のＩ／Ｏポート５５８を介して通信するように構成され得る。例の通信デバイス５４６は、ネットワークコントローラ５６０を含み、ネットワークコントローラ５６０は、ネットワーク通信リンクを介し、１つまたは複数の通信ポート５６４を介する１つまたは複数の他のコンピューティングデバイス５６２との通信を容易にするように配置され得る。
【００９１】
ネットワーク通信リンクを、通信媒体の１つの例とすることができる。通信媒体を、一般に、搬送波または他のトランスポート機構などの変調されたデータ信号内のコンピュータ可読命令、データ構造、プログラムモジュール、または他のデータによって実施することができ、通信媒体は、任意の情報配布媒体を含むことができる。「変調されたデータ信号」は、その特性のうちの１つまたは複数を、信号内で情報を符号化する形でセットされまたは変更された信号とすることができる。限定ではなく例として、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体と、音響、ラジオ周波数（ＲＦ）、マイクロ波、赤外線（ＩＲ）、および他の無線媒体などの無線媒体とを含むことができる。用語コンピュータ可読媒体は、本明細書で使用されるときに、記憶媒体と通信媒体との両方を含むことができる。
【００９２】
コンピューティングデバイス５００を、セル電話機、携帯情報端末（ＰＤＡ）、パーソナルメディアプレイヤデバイス、無線ウェブウォッチデバイス、パーソナルヘッドセットデバイス、特定用途向けデバイス、または上記の機能のいずれかを含むハイブリッドデバイスなどの小フォームファクタのポータブル（またはモバイル）電子デバイスの一部として実施することができる。コンピューティングデバイス５００を、ラップトップコンピュータ構成と非ラップトップコンピュータ構成との両方を含むパーソナルコンピュータとして実施することもできる。
【００９３】
本明細書での実質的にすべての複数形および／または単数形の用語の使用に関して、当業者は、文脈および／または応用例に適切に、複数形から単数形におよび／または単数形から複数形に変換することができる。さまざまな単数／複数の置換が、明瞭にするために本明細書で明示的に示される場合がある。
【００９４】
一般に、本明細書、特に添付の特許請求の範囲（たとえば、添付の特許請求の範囲の本体）で使用される用語は、一般に、「オープンな」用語として意図されていること（たとえば、用語「ｉｎｃｌｕｄｉｎｇ（含む）」は、「ｉｎｃｌｕｄｉｎｇ ｂｕｔ ｎｏｔ ｌｉｍｉｔｅｄ ｔｏ（を含むがこれに限定されない）」と解釈されなければならず、用語「ｈａｖｉｎｇ（有する）」は、「ｈａｖｉｎｇ ａｔ ｌｅａｓｔ（少なくとも〜を有する）」と解釈されなければならず、用語「ｉｎｃｌｕｄｅｓ（含む）」は、「ｉｎｃｌｕｄｅｓ ｂｕｔ ｉｓ ｎｏｔ ｌｉｍｉｔｅｄ ｔｏ（を含むがこれに限定されない）」と解釈されなければならないことなど）が、当業者によって理解されるであろう。さらに、特定の個数の導入される請求項の記述が意図される場合には、そのような意図が、特許請求の範囲で明示的に記述され、そのような記述がない場合には、そのような意図が存在しないことが、当業者によって理解されるであろう。たとえば、理解の助けとして、次の添付の特許請求の範囲は、請求項の記述を導入するために導入句「ａｔ ｌｅａｓｔ ｏｎｅ（少なくとも１つの）」および「ｏｎｅ ｏｒ ｍｏｒｅ（１つまたは複数の）」の使用を含む場合がある。しかし、そのような句の使用は、同一の請求項が導入句「ｏｎｅ ｏｒ ｍｏｒｅ」または「ａｔ ｌｅａｓｔ ｏｎｅ」および「ａ」または「ａｎ」などの不定冠詞を含むときであっても、不定冠詞「ａ」または「ａｎ」による請求項の記述の導入が、そのように導入された請求項の記述を含む任意の特定の請求項を１つのみのそのような記述を含む実施形態に限定することを暗示すると解釈されてはならず（たとえば、「ａ」および／または「ａｎ」は、「ａｔ ｌｅａｓｔ ｏｎｅ」または「ｏｎｅ ｏｒ ｍｏｒｅ」を意味すると解釈されなければならない）、同一のことが、請求項の記述を導入するのに使用される定冠詞の使用にもあてはまる。さらに、特定の個数の導入される請求項の記述が明示的に記述される場合であっても、当業者は、そのような記述を、少なくとも記述された数を意味する（たとえば、他の修飾成句を伴わない「２つの記述」という最低限の記述は、少なくとも２つの記述または複数の記述を意味する）と解釈しなければならないことを認めるであろう。さらに、「ａｔ ｌｅａｓｔ ｏｎｅ ｏｆ Ａ，Ｂ，ａｎｄ Ｃ，ｅｔｃ．（Ａ、Ｂ、およびＣのうちの少なくとも１つ、など）」に類似する慣例が使用される場合に、一般に、そのような構文は、当業者がその慣例を理解する意味であることが意図されている（たとえば、「ａ ｓｙｓｔｅｍ ｈａｖｉｎｇ ａｔ ｌｅａｓｔ ｏｎｅ ｏｆ Ａ，Ｂ，ａｎｄ Ｃ（Ａ、Ｂ、およびＣのうちの少なくとも１つを有するシステム）」は、Ａのみ、Ｂのみ、Ｃのみ、ＡとＢとを一緒に、ＡとＣとを一緒に、ＢとＣとを一緒に、ならびに／またはＡ、Ｂ、およびＣを一緒に有するシステムを含むが、これに限定はされないなど）。「ａｔ ｌｅａｓｔ ｏｎｅ ｏｆ Ａ，Ｂ，ｏｒ Ｃ，ｅｔｃ．（Ａ、Ｂ、またはＣのうちの少なくとも１つ、など）」に類似する慣例が使用される場合に、一般に、そのような構文は、当業者がその慣例を理解する意味であることが意図されている（たとえば、「ａ ｓｙｓｔｅｍ ｈａｖｉｎｇ ａｔ ｌｅａｓｔ ｏｎｅ ｏｆ Ａ，Ｂ，ｏｒ Ｃ（Ａ、Ｂ、またはＣのうちの少なくとも１つを有するシステム）」は、Ａのみ、Ｂのみ、Ｃのみ、ＡとＢとを一緒に、ＡとＣとを一緒に、ＢとＣとを一緒に、ならびに／またはＡ、Ｂ、およびＣを一緒に有するシステムを含むが、これに限定はされないなど）。さらに、複数の代替の項目を表す事実上すべての選言的単語および／または句は、明細書、特許請求の範囲、または図面のいずれに含まれるものであれ、項目のうちの１つ、項目のいずれか、または両方の項目を含む可能性を企図すると理解されなければならないことが、当業者によって理解されるであろう。たとえば、句「Ａ ｏｒ Ｂ（ＡまたはＢ）」は、「Ａ」または「Ｂ」または「ＡおよびＢ」の可能性を含むと理解される。
【００９５】
さらに、本開示の特徴または態様が、Ｍａｒｋｕｓｈ ｇｒｏｕｐに関して説明される場合に、当業者は、本開示が、これによってＭａｒｋｕｓｈ ｇｒｏｕｐの任意の個々のメンバまたはメンバのサブグループに関しても説明されることを認めるであろう。
【００９６】
当業者によって理解されるように、書面による説明を提供することに関してなど、すべてにおいて、本明細書で開示されるすべての範囲は、任意のすべての可能な部分範囲およびその部分範囲の組合せをも包含する。すべてのリストされた範囲を、少なくとも等しい半分、１／３、１／４、１／５、１／１０などに分割された同一の範囲を十分に記述し、可能にするものとしてたやすく認めることができる。非限定的な例として、本明細書で述べられる各範囲を、下側１／３、中央１／３、および上側１／３などにたやすく分解することができる。やはり当業者によって理解されるように、「ｕｐ ｔｏ（まで）」、「ａｔ ｌｅａｓｔ（少なくとも）」、および類似物などのすべての言葉は、記述された数を含み、その後に上で述べたように部分範囲に分割され得る範囲に言及する。最後に、当業者によって理解されるように、範囲は、各個々のメンバを含む。したがって、たとえば、１〜３個のセルを有する群は、１個、２個、または３個のセルを有する群に言及する。同様に、１〜５個のセルを有する群は、１個、２個、３個、４個、または５個のセルを有する群に言及するなどである。
【００９７】
前述から、本開示のさまざまな実施形態が、本明細書で例示のために説明されたことと、さまざまな変更を、本開示の範囲および趣旨から逸脱せずに行うことができることとを了解されたい。したがって、本明細書で開示されるさまざまな実施形態は、限定的であることを意図されてはおらず、真の範囲および趣旨は、次の特許請求の範囲によって示される。
【背景技術】
【０００１】
多数のコンピューティングノードにまたがる分散大規模計算が、ますます人気のあるものになってきた。そのような大規模計算の分散化は、そうでなければ単一のコンピューティングシステムまたは少数のコンピューティングシステムの処理リソースを越える可能性がある複雑な問題を解くことを可能にする。一般に、中央コンピューティングシステムは、大規模計算の一部を各コンピューティングノードに供給する。そしてコンピューティングノードは、それに割り当てられた部分を実行し、結果を中央コンピューティングシステムに返す。その後、中央コンピューティングシステムは、コンピューティングノードからのさまざまな結果を処理して、大規模計算に対する全体的な解を判定する。
【０００２】
１つの一般的な手法は、大規模計算の諸部分を、一般大衆から採用されたボランティアに分配することである。ボランティアは、彼らのコンピュータが分散システムのコンピューティングノードとして働くことを可能にする。したがって、中央コンピューティングシステムは、ボランティアのコンピューティングノードのそれぞれに、大規模計算のうちの実行すべき部分を供給する。この手法は、ノードがボランティアによって使用中ではない時またはボランティアが彼らのコンピューティングノードの処理リソースのすべてを利用しているのではない時に、コンピューティングノードの処理リソースの利用を可能にする。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
公衆からのボランティアの使用は、処理リソースへの低コストアクセスを提供するが、複数の短所がある。第１に、大規模計算の一部を実行しつつあるコンピューティングノードは、ボランティアノードなので、中央コンピューティングシステムの視点からは信頼されないものである。したがって、コンピューティングノードが、解かれるべき問題のプログラムコード内にバグを導入すること、ユーザエラー、外部データの誤構成、または他の類似する情況の結果として、図らずも誤りを犯す可能性がある。あるいは、コンピューティングノードが、割り当てられた計算に対する誤った解を提供することによって、または別のコンピューティングノードから結果を盗み、これらの結果をそれ自体の結果として提供することによって、詐欺を試みることができる。
【０００４】
いくつかのシステムは、そのような詐欺を防ぐことを試みて、暗号化およびディジタル署名などのセキュリティ手段を提供する。しかし、そのような手段は、ある種の誤りまたは洗練された詐欺を検出することができない。たとえば、相手方が、進行中の計算に割り込み、いくつかの値を変更し、従来の暗号化およびディジタル署名が検出できない形で計算を継続することを可能にすることができる。
【課題を解決するための手段】
【０００５】
本明細書で開示される例示的実施形態は、中央コンピューティングシステムが中央コンピューティングシステムに結合された複数の信頼されないコンピューティングノードによって実行された作業を検証する方法およびコンピュータプログラム製品に関する。中央コンピューティングシステムは、第１の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき第１計算を決定する。中央コンピューティングシステムは、第２の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき同等の第２計算を作るために第１計算に適用される変換関数をも決定する。中央コンピューティングシステムは、第１の信頼されないコンピューティングノードによって実行されるために第１計算を割り当て、変換関数を秘密に保ちながら、第２の信頼されないコンピューティングノードによって実行されるために第２計算を割り当てる。中央コンピューティングシステムは、第１計算の第１結果を第１の信頼されないコンピューティングノードから、および第２計算の第２結果を第２の信頼されないコンピューティングノードから受け取る。中央コンピューティングシステムは、第１の信頼されないコンピューティングノードおよび第２の信頼されないコンピューティングノードによって実行された作業を検証するために第１結果および第２結果を分析する。
【０００６】
本明細書で開示される例示的実施形態は、コンピューティングシステムに関する。このコンピューティングシステムは、プロセッサと、データベースと、計算生成モジュールと、変換関数モジュールと、受取モジュールと、分析モジュールとを含む。計算生成モジュールは、第１の信頼されないコンピューティングノードによって実行されるべき第１計算を生成する。変換関数モジュールは、同等の第２計算を作るために第１計算に適用される変換関数を生成するか入手する。第２計算は、第２の信頼されないコンピューティングノードによって実行されるべきものである。割当てノードは、第１の信頼されないコンピューティングノードによって実行されるために第１計算を割り当て、変換関数を秘密に保ちながら、第２の信頼されないコンピューティングノードによって実行されるために第２計算を割り当てる。受取モジュールは、第１計算の第１結果を第１の信頼されないコンピューティングノードから、および第２計算の第２結果を第２の信頼されないコンピューティングノードから受け取る。分析モジュールは、第１の信頼されないコンピューティングノードおよび第２の信頼されないコンピューティングノードによって実行された作業を検証するために第１結果および第２結果を分析する。
【０００７】
前述の概要は、例示的であるのみであって、いかなる形でも限定的であることは意図されていない。上で説明された例示的態様、実施形態、および特徴に加えて、さらなる態様、実施形態、および特徴が、図面および次の詳細な説明を参照することによって明白になる。
【図面の簡単な説明】
【０００８】
【図１】分散コンピューティングシステムの例示的実施形態を示す概略図である。
【図２】図１の分散コンピューティングシステムの中央コンピューティングシステムの例示的実施形態を示す図である。
【図３】信頼されないコンピューティングノードによって実行された作業を検証する方法の例示的実施形態を示す流れ図である。
【図４】信頼されないコンピューティングノードによって実行された作業を検証する方法の代替実施形態を示す流れ図である。
【図５】本開示による信頼されないコンピューティングノードによって実行された作業を検証するための例のコンピューティングデバイスを示す図である。
【発明を実施するための形態】
【０００９】
次の詳細な説明では、次の詳細な説明の一部を形成する添付図面を参照する。図面では、文脈がそうではないと示さない限り、類似する記号が、通常は類似するコンポーネントを識別する。この詳細な説明、図面、および特許請求の範囲で説明される例示的実施形態は、限定的であることを意図されていない。本明細書で提示される主題の趣旨または範囲から逸脱せずに、他の実施形態を利用することができ、他の変更を行うことができる。本明細書で全体的に説明され図面に示された本開示の諸態様を、さまざまな異なる構成で配置し、置換し、組み合わせ、分離し、設計でき、そのすべてが本明細書で明示的に企図されることが、たやすく理解されるであろう。
【００１０】
本明細書で開示される実施形態は、分散コンピューティングシステムに関する。分散コンピューティングシステムは、中央コンピューティングシステムに動作可能に結合された複数の信頼されないコンピューティングノードを含む。中央コンピューティングシステムは、複数の信頼されないコンピューティングノードの処理リソースを利用して、一般に大量の処理リソースを必要とする大規模複雑計算を実行するのを助ける。
【００１１】
複数の信頼されないコンピューティングノードは、計算の少なくとも一部を実行できる処理リソースを有する任意のタイプのコンピューティングシステムとすることができる。例は、デスクトップコンピュータ、ラップトップコンピュータ、携帯電話機、およびＰＤＡを含むが、これらに限定はされない。複数の信頼されないコンピューティングノードは、中央コンピューティングシステムがそれらのコンピューティングノードの動作に対する直接制御を有しないので、中央コンピューティングシステムの視点からは信頼されない。
【００１２】
したがって、本明細書で開示される実施形態は、中央コンピューティングシステムが、複数の信頼されないコンピューティングノードによって実行された作業を検証する機構を提供する。本明細書で開示される実施形態は、偽造者またはたかり屋である信頼されないコンピューティングノードに対して防御する。偽造者とは、実際には割り当てられた作業を行わない時にそれを行うふりをするノードであり、たかり屋は、それ自体または別のノードによって以前に実行された作業をコピーすることを試みる。破壊者は、悪い結果を完全な計算に注入することを試みる、一種の偽造者である。したがって、偽造者およびたかり屋は、詐欺的な無効な情報を中央コンピューティングシステムに提供する場合がある。
【００１３】
さらに、本明細書で開示される実施形態は、複数の信頼されないコンピューティングノードによる共謀に対して防御する。より詳細に説明されるように、信頼されないコンピューティングノードによって実行されるべき異なるが同等の計算を提供することによって、詐欺的な無効な結果をもたらすために一緒に働く２つのノードの能力が、減らされる。
【００１４】
一実施形態によれば、中央コンピューティングシステムは、信頼されないコンピューティングノードが実行を助けなければならない第１計算を決定する。一般に、第１計算は、第１の信頼されないコンピューティングノードによって実行される。第１計算を、計算コンポーネントに分割することができ、各サブセットは、１つの信頼されないコンピューティングノードによって実行される。
【００１５】
共謀、たかり、または偽造に対して保護するために、中央コンピューティングシステムは、同等の第２計算を作るために第１計算に適用される変換関数をも決定する。変換関数は、第２計算を第１計算と同等にする任意の関数である。したがって、同等な計算は、変換関数が除去されるときに、第１計算と実質的に同一の計算である。変換関数の例に加えて、さらなる詳細を、下で提供する。一般に、同等の第２計算は、第２の信頼されないコンピューティングノードによって実行される。変換関数を、複数の変換関数コンポーネントを含む変換空間から選択することができる。
【００１６】
その後、中央コンピューティングシステムは、第１計算を第１の信頼されないコンピューティングノードに割り当て、第２計算を第２の信頼されないコンピューティングノードに割り当てることができ、その結果、両方の計算を実行できるようになる。詐欺または共謀に対して保護するために、第１および第２の信頼されないコンピューティングノードを、ランダムに選択し、割り当てることができる。さらに、同等の第２計算を作るのに使用される変換関数は、追加の保護手段として、第１および第２の信頼されないコンピューティングノードから秘密に保たれる。
【００１７】
計算が、信頼されないコンピューティングノードによって実行された後に、第１計算の第１結果を、第１の信頼されないコンピューティングノードから受け取ることができる。第２計算の第２結果も、第２の信頼されないコンピューティングノードから受け取ることができる。
【００１８】
第１および第２の結果を分析して、第１および第２の信頼されないコンピューティングノードによって実行された作業を検証することができる。すなわち、結果の分析は、ノードの一方または両方がたかり屋または偽造者であるかどうか、あるいは２つのノードが共謀して詐欺的な無効な結果を提供したかどうかを判定するのを助ける。この分析は、第２結果から変換関数を除去し、その後、第１結果と第２結果とを比較することができる。第２結果からの変換の除去が、通常は変換関数の逆関数を第２結果に適用することによって実行されることを了解されたい。第２結果への変換の逆のこの適用は、以下でより詳細に説明するように、２つの結果を実質的に同一にするので、結果は、結果が有効である場合には一般に同一であり、結果の一方または両方が無効である場合には一般に異なる。詐欺に対するさらなる保護手段として、信頼されないコンピューティングノードのヒストリカル信頼性を、ヒストリカルデータのデータベースを調べることによって分析することができる。さらに、１つまたは複数の確率関数を結果に適用して、結果が有効である確率を判定することができる。
【００１９】
本開示のそれぞれの態様の複数の例示的実施形態を、下で例として添付図面を参照して与える。図１は、中央コンピューティングシステム１１０ならびに複数の信頼されないコンピューティングノード１３０、１４０、１５０、および１６０を含む分散コンピューティングシステム１００の例示的実施形態の概略図である。図１は、任意の追加の個数の信頼されないコンピューティングノード１７０（省略記号によって示される）を分散コンピューティングシステム１００に含めることができることをも示す。当業者は、図１に示されたものとは異なる個数の信頼されないコンピューティングノードがあってもよいことを了解するであろう。多くの実施形態では、数千個または数百万個の信頼されないコンピューティングノードがあってもよい。
【００２０】
中央コンピューティングシステム１１０を、ネットワーク１２０によって、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０に結合することができる。図１に示されているように、中央コンピューティングシステム１１０および信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０は、ネットワーク１２０を介して互いに両方向で通信することができる。ネットワーク１２０は、中央コンピューティングシステム１１０または信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０と互換の任意のネットワークとすることができ、例として、衛星ネットワーク、８０２．１１ネットワーク、パーソナルコンピュータネットワーク（たとえば、ＬＡＮ、ＷＡＮ）、無線ネットワーク（たとえば、Ｂｌｕｅｔｏｏｔｈ、ＷｉＦｉ）、セルラネットワーク、電話網（たとえば、地上の通信線またはＰＳＴＮ）、データネットワーク、インターネット、または類似物、あるいはその任意の組合せを含むことができる。
【００２１】
１つの例示的実施形態では、中央コンピューティングシステム１１０は、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０によって少なくとも部分的に実行されるべき大規模で通常は複雑な計算を生成する。以下でより詳細に説明するように、中央コンピューティングシステム１１０は、第１計算を生成し、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０のうちのいくつかが実行するために、第１計算の一部をネットワーク１２０を介して供給することができる。中央コンピューティングシステム１１０は、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０のうちのいくつかが実行するために、秘密の変換関数に基づいて同等の第２計算をも生成することができる。
【００２２】
信頼されないコンピューティングノード１３０、１４０、１５０、および１６０は、それぞれ処理リソース１３５、１４５、１５５、および１６５を含む。処理リソース１３５、１４５、１５５、および１６５は、コンピューティングノード１３０、１４０、１５０、および１６０が第１計算もしくは第２計算またはこれらの計算の一部を実行することを可能にする、プロセッサと任意の他のコンピュータハードウェアおよび／またはソフトウェアとを表す。また、信頼されないコンピューティングノード１７０のいずれもが、第１計算または第２計算を実行するためにプロセッサおよび他の処理リソースを含むことに留意されたい。
【００２３】
図２に、中央コンピューティングシステム１１０の例示的実施形態ならびに分散コンピューティングシステム１００のより詳細な図を示す。図２では、ネットワーク１２０が省略され、その結果、この図の追加の特徴を、より明瞭に見られるようになっている。図示されているように、中央コンピューティングシステム１１０は、これからより詳細に説明される、さまざまな動作モジュールおよびデータベースを含む。本明細書で開示される実施形態から注意をそらさないようにするために、結合されるものとして図示されてはいないが、中央コンピューティングシステム１１０のさまざまな動作モジュールおよびデータベースを、コンピュータバス、他の配線、または環境が保証するときの無線接続など、任意の妥当な手段によって互いに結合できることを理解されたい。
【００２４】
図示されているように、中央コンピューティングシステム１１０は、プロセッサ２１０を含む。プロセッサ２１０は、任意の妥当なプロセッサとすることができ、動作中には、中央コンピューティングシステム１１０がさまざまな動作を実行することを可能にする。いくつかの実施形態では、プロセッサ２１０に、中央コンピューティングシステム１１０のさまざまな動作モジュールによってアクセスして、モジュールに処理リソースを与えることができる。他の実施形態では、動作モジュールは、代替プロセッサへのアクセスを有することができる。
【００２５】
中央コンピューティングシステム１１０は、データベース２２０をも含む。データベース２２０は、任意のタイプの妥当な不揮発性メモリまたは揮発性メモリとすることができる。１つの例示的実施形態では、データベース２２０は、ヒストリ２２５を含むことができる。ヒストリ２２５は、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０によって中央コンピューティングシステム１１０に供給された過去の結果を含むことができる。以下でより詳細に説明するように、ヒストリ１２５を中央コンピューティングシステム１１０によって使用して、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０の信頼性を判定することができる。データベース２２０は、中央コンピューティングシステム１１０内に含まれるものとして図示されているが、いくつかの実施形態では、データベース２２０を、中央コンピューティングシステム１１０からアクセス可能でありながら中央コンピューティングシステム１１０の外部とすることができる。
【００２６】
計算生成モジュール２３０も、中央コンピューティングシステム１１０に含まれる。計算生成モジュール２３０は、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０のうちの１つまたは複数などの、１つまたは複数の信頼されないコンピューティングノードによって実行されるべき第１計算２８０を生成することができる。第１計算２８０は、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０が実行を助けることを中央コンピューティングシステム１１０が望む任意の計算とすることができる。いくつかの例示的実施形態では、第１計算２８０を、１つまたは少数の信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０によって解くことができる単一の問題とすることができる。しかし、第１計算２８０は、一般に、複数の部分に分解され、計算のために多数の信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０に分配される、大規模で複雑な問題である。たとえば、第１計算２８０を、第１計算コンポーネント２８０ａ、２８０ｂ、および図２で省略記号によって示されているように潜在的に任意の個数の追加の第１計算コンポーネント２８０ｃに分割することができる。
【００２７】
中央コンピューティングシステム１１０は、変換関数モジュール２４０を含む。一実施形態では、変換関数モジュール２４０は、変換関数２４５を生成することができる。変換関数２４５は、一般に、変換関数２４５が第１計算２８０に適用される時に、第１計算２８０と同等の第２計算２９０が作られる形で第１計算２８０に関連する。したがって、変換関数２４５は、一般に、第１計算２８０に関連する問題のタイプに基づいて選択される。変換関数２４５が、変換自体および変換関数の逆関数を含むことを了解されたい。
【００２８】
もう１つの実施形態では、変換関数モジュール２４０は、中央コンピューティングシステム１１０のユーザまたは別のコンピューティングシステムから変換関数を入手することができる。そのような実施形態では、ユーザまたは他のコンピューティングシステムは、変換関数を変換関数モジュール２４０に供給することができる。代替案では、ユーザまたは他のコンピューティングシステムは、変換関数モジュール２４０に、使用できるさまざまな変換関数を含む、ある変換テンプレートを選択させ、検証させ、または調整させることができる。したがって、変換関数モジュール２４０が、変換関数を生成することができ、あるいは、変換関数モジュール２４０が、ユーザまたは別のコンピューティングシステムから変換関数を入手することができることを了解されたい。たとえば、第１計算２８０が、各次元が複雑、近似的に連続、または他の形で非常に可変である空間解釈を扱う問題に関連すると仮定する。そのような第１計算２８０は、線形の変換関数２４５を示唆する。たとえば、Ｘが３Ｄ形状の集合であり、第１計算２８０が、Ｘに含まれる形状の総体積を計算することであると仮定する。すると、変換関数２４５を、線形変換の空間から選択することができる。
【００２９】
述べたように、第１計算２８０への変換関数２４５の適用は、第１計算２８０と同等な第２計算２９０を作る。前に述べたように、同等な問題または同等な計算とは、変換関数２４５が除去された時に、第１の問題または第１の計算と実質的に同一の問題または計算である。単純な線形変換を使用して、この点を示すことができる。たとえば、第１計算２８０が、１＋１という単純な式であったと仮定する。さらに、変換関数２４５が、ｆ（ｘ）＝ｘ＊１００という線形変換であったと仮定する。式１＋１に適用されるときに、１００＋１００という同等の第２計算２９０が作られるはずである。すぐにわかるように、１＋１の結果は２であり、１００＋１００の結果は２００である。この線形変換の逆を結果２００に適用することは、第２計算２９０に２という結果を与え、これは、第１計算２８０の２という結果と実質的に同一である。単純な式および単純な線形変換が、例示を簡単にするために使用されたが、より複雑な変換をより複雑な問題に対して使用できることを了解されたい。前に述べたように、第１計算２８０のタイプは、一般に、どのタイプの変換関数２４５を同等の第２計算２９０を作るのに使用できるのかを規定する。
【００３０】
１つの例示的実施形態では、変換関数２４５を、複数の変換関数コンポーネント２４５ａ、２４５ｂ、および図２で省略記号によって示されように潜在的に任意の個数の追加の変換関数コンポーネント２４５ｃに分割できる変換空間とすることができる。そのような実施形態では、変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃのうちの任意の１つを第１計算２８０に適用して、同等の第２計算２９０を作ることができる。
【００３１】
第１計算２８０が複数の第１計算コンポーネント２８０ａ、２８０ｂ、および２８０ｃに分割される実施形態では、変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃのうちの任意の１つを特定の第１計算コンポーネントサブセット２８０ａ、２８０ｂ、および２８０ｃに適用して、第２計算２９０を作ることができる。たとえば、変換関数サブセット２４５ｂを第１計算コンポーネントサブセット２８０ａに適用して、同等の第２計算２９０を作ることができる。後の時に、変換関数サブセット２４５ｂを第１計算サブセット２８０ｂに適用して、同等の第２計算２９０を作ることができる。さらに後の時に、変換関数サブセット２４５ａを第１計算コンポーネントサブセット２８０ａに適用して、同等の第２計算２９０を作ることができる。したがって、変換関数空間の変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃのうちの任意の１つを使用して、同等の第２計算２９０を作ることができる。
【００３２】
中央コンピューティングシステム１００は、さらに、割当てモジュール２５０を含む。割当てモジュール２５０は、第１計算１８０および第２計算２９０を実行するために、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０のうちの２つをランダムに割り当てることができる。２つの信頼されないコンピューティングノード、このケースでは信頼されないコンピューティングノード１３０および１４０をランダムに選択しまたは割り当てることによって、２つの信頼されないコンピューティングノードが互いに共謀し、または一方のコンピューティングノードに他方のコンピューティングノードからの結果を盗ませる可能性が、減らされる。
【００３３】
図示の実施形態では、信頼されないコンピューティングノード１３０は、第１計算２８０を実行するために、割当てモジュール２５０によってランダムに割り当てられる。計算全体またはより大きくより複雑な計算のサブセットのいずれであれ、第１計算２８０を、図２に示されているように、信頼されないコンピューティングノード１３０に供給することができる。次に、信頼されないコンピューティングノード１３０は、処理リソース１３５を使用して、第１計算２８０を少なくとも部分的に実行することができる。
【００３４】
割当てモジュール２５０は、同等の第２計算２９０を実行するために、信頼されないコンピューティングノード１４０をランダムに割り当てることができる。第２計算２９０を、図２に示されているように信頼されないコンピューティングノード１４０に供給することができる。信頼されないコンピューティングノード１４０は、処理リソース１４５を使用して、第２計算２９０を少なくとも部分的に実行することができる。
【００３５】
追加の保護手段として、変換関数２４５を、信頼されないコンピューティングノード１３０および１４０から秘密に保つことができる。了解されるように、信頼されないコンピューティングノード１３０または１４０のいずれかが変換関数２４５のアイデンティティを知った場合には、信頼されないコンピューティングノード１３０または１４０の一方または両方が第１計算２８０および第２計算２９０の解が何であるべきなのかを推測することを試みることが、はるかに簡単になるはずである。変換関数２４５を秘密に保つことによって、無効な結果が信頼されないコンピューティングノード１３０または１４０によって返される可能性が、減らされる。
【００３６】
第１計算２８０が、前に述べたように複数の第１計算コンポーネント２８０ａ、２８０ｂ、および２８０ｃに分割される実施形態では、割当てモジュール２５０は、第１計算コンポーネント２８０ａ、２８０ｂ、および２８０ｃのうちのどれが、信頼されないコンピューティングノード１３０などのランダムに選択された信頼されないコンピューティングノードに割り当てられるのかを、ランダムに選択することができる。同様に、変換関数２４５が、複数の変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃを有する変換空間である実施形態では、割当てモジュール２５０または変換関数モジュール２４０は、変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃのうちのどれが、同等の第２計算２９０を生成するのに使用されるべきなのかをランダムに選択することができる。第１計算サブセット２８０ａ、２８０ｂ、または２８０ｃおよび変換関数サブセット２４５ａ、２４５ｂ、または２４５ｃのランダム選択は、この例では信頼されないコンピューティングノード１３０または１４０による共謀に対する追加のセキュリティを提供する。
【００３７】
受取モジュール２６０は、この例では、信頼されないコンピューティングノード１３０から第１計算２８０の第１結果２８５を受け取ることができ、信頼されないコンピューティングノード１４０から第２計算２９０の第２結果２９５をも受け取ることができる。
【００３８】
前に述べたように、信頼されないコンピューティングノード１３０および１４０（ならびに信頼されないコンピューティングノード１５０、１６０、および１７０）は、それらが中央コンピューティングシステム１１０によって制御されないので、信頼されない。したがって、中央コンピューティングシステム１１０は、信頼されないコンピューティングノード１３０および１４０によって返された結果が有効であるかどうかを知らない。無効な結果を返すことによる結果の偽造または別の信頼されないコンピューティングノードによって実行された作業をコピーすることによるたかりに備えるために、中央コンピューティングシステム１１０は、分析モジュール２７０を含む。分析モジュール２７０は、第１結果２８５および第２結果２９５を分析して、信頼されないコンピューティングノード１３０および１４０によって実行された作業を検証することができる。
【００３９】
１つの例示的実施形態では、分析モジュール２７０は、第２結果２９５から変換関数２４５を除去することによって、第１結果２８５および第２結果２９５を分析することができる。次に、分析モジュール２７０は、第１結果２８５および第２結果２９５をお互いと比較することができる。線形変換の例に関して前に上で説明したように、第２結果２９５からの変換関数２４５の除去は、信頼されないコンピューティングノード１３０および１４０によって、第１計算２８０および第２計算２９０が正しく実行され、有効な結果が供給されたときに、第２結果２９５が第１結果２８５と実質的に同一となるようにする。したがって、第１結果２８５と第２結果２９５とがお互いと一致する場合には、信頼されないコンピューティングノード１３０および１４０が有効な結果を提供した可能性が高い。信頼されないコンピューティングノード１３０と１４０との両方が無効な同等の結果を提供する形で共謀する可能性や、一方の信頼されないノードが他方の信頼されないノードの結果と一致する詐欺的結果を提供する可能性は、非常に低い。
【００４０】
その一方で、分析モジュール２７０が、比較の後に第１結果２８５と第２結果２９５との間の差を見つける場合には、信頼されないコンピューティングノード１３０および１４０のうちの少なくとも１つ、おそらく信頼されないコンピューティングノード１３０と１４０との両方が、無効な結果を提供したことを意味する可能性がある。その後、これらの結果を中央コンピューティングシステム１１０によって疑わしいと見なすことができる。
【００４１】
１つの例示的実施形態では、第１結果２８５および／または第２結果２９５が、一連の中間結果を含む場合がある。たとえば、第１結果２８５が、一連の第１中間結果２８５ａ、２８５ｂ、および図２で省略記号によって示されるように潜在的に任意の個数の追加の中間結果２８５ｃを含む場合がある。同様に、第２結果２９５が、一連の第２中間結果２９５ａ、２９５ｂ、および図２で省略記号によって示されるように潜在的に任意の個数の追加の中間結果２９５ｃを含む場合がある。そのような実施形態では、第１計算２８０および／または第２計算２９０を変更して、完全な第１結果２８５および第２結果２９５が判定され、中央コンピューティングシステム１１０に返される前に、中間結果を判定し、中央コンピューティングシステム１１０に返すことを可能にすることができる。
【００４２】
分析モジュール２７０は、第１中間結果２８５ａ、２８５ｂ、および２８５ｃならびに第２中間結果２９５ａ、２９５ｂ、および２９５ｃを、たとえばそれらを比較して信頼されないコンピューティングノード１３０および１４０が無効な結果を供給したかどうかを判定することによって、分析することができる。第１中間結果２８５ａ、２８５ｂ、および２８５ｃが第２中間結果２９５ａ、２９５ｂ、および２９５ｃと一致する場合には、それらの結果が有効である可能性が高い。第１中間結果２８５ａ、２８５ｂ、および２８５ｃが第２中間結果２９５ａ、２９５ｂ、および２９５ｃと一致しない場合には、それらの結果が無効である可能性が高い。中間結果の使用は、信頼されないコンピューティングノード１３０および１４０が、両方が同等の無効な中間結果を供給する形で共謀しまたは一方の信頼されないノードが他方の信頼されないノードの中間結果と一致する詐欺的中間結果を提供する可能性が非常に低いので、詐欺および共謀に対する追加の保護を提供する。
【００４３】
１つの例示的実施形態では、変換関数２４５の逆関数を、第２中間結果２９５ａ、２９５ｂ、および２９５ｃのそれぞれに適用することができる。そのような適用は、第２中間結果２９５ａ、２９５ｂ、および２９５ｃを対応する第１中間結果２８５ａ、２８５ｂ、および２８５ｃと同等にするはずである。そのような実施形態では、変換関数２４５が、単一の関数である必要がないことに留意されたい。たとえば、変換関数２４５を、それぞれ、第２計算２９０を作るために第１計算２８０に、第２中間結果２９５ａ、２９５ｂ、および２９５ｃに、ならびに第２結果２９５に適用される多重の全単射（multiple bijection）とすることができる。
【００４４】
述べたように、分析モジュール２７０は、第１計算２８０の第１結果２８５および第２計算２９０の第２結果２９５を分析して、それらがおそらく有効であるかどうかを判定する。しかし、分析モジュール２７０によって実行される分析が、個々の信頼されないコンピューティングノードの信頼性を判定できないことがあり得る。たとえば、信頼されないコンピューティングノード１３０からの第１結果２８５が、信頼されないコンピューティングノード１４０からの第２結果２９５と一致しない場合に、これは、必ずしも、信頼されないコンピューティングノード１３０が不正直に詐欺的結果を供給したことを意味しない。信頼されないコンピューティングノード１４０が詐欺的結果を供給したか、または、信頼されないコンピューティングノード１３０が、第１計算２８０を実行する時に本当に間違ったことがあり得る。
【００４５】
この例では信頼されないコンピューティングノード１３０または１４０のどれが、詐欺的結果または無効な結果を供給した可能性があるのかを判定するのを助けるために、第１結果２８５および第２結果２９５は、データベース２２０に供給され、ヒストリ２２５に含められる。前に述べたように、ヒストリ２２５は、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０によって供給された以前の計算からのすべてのヒストリカル結果を含むことができる。
【００４６】
分析モジュール２７０は、ヒストリ２２５にアクセスして、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０の信頼性を判定することができる。信頼されないコンピューティングノード１３０が、その結果が一致する信頼されないコンピューティングノードの対に含まれることのヒストリを有する場合には、現在の不一致が、信頼されないコンピューティングノード１４０によって引き起こされたか、本当の間違いであると仮定することができる。その一方で、信頼されないコンピューティングノード１３０が、その結果が一致しない信頼されないコンピューティングノードの多数の対に含まれることのヒストリを有する場合には、信頼されないコンピューティングノード１３０を、疑問視することができ、その結果を無視することができる。類似する分析を、信頼されないコンピューティングノード１４０および実際にすべての信頼されないコンピューティングノードによって供給された結果に対して実行することができる。したがって、ヒストリ２２５の使用は、特定の信頼されないコンピューティングノードを信頼すべきかどうかを、その信頼されないコンピューティングノードのヒストリカル動作に基づいて検証するための追加のチェックを提供する。了解されるように、信頼されないコンピューティングノードは、そのヒストリ２２５に格納された結果の過半数が有効である場合には信頼できる可能性が高く、そのヒストリ２２５に格納された結果の過半数またはそのかなりの割合が無効である場合には信頼できる可能性が低い。
【００４７】
いくつかの実施形態では、第１計算２８０および／または第２計算２９０を、暗号化、ディジタル署名、または難読化などのさまざまなテクノロジを用いて補強することもできる。これらのテクノロジは、信頼されないコンピューティングノードによる改竄に対する追加の障壁を提供するために含めることができる。
【００４８】
中央コンピューティングシステム１１０が変換関数２４５を秘密に保った場合であっても、信頼されないコンピューティングノード１３０が、変換関数２４５を学習しまたは推測することが可能である場合がある。その場合には、信頼されないコンピューティングノード１３０は、無効な第１結果２８５を悪意を持って供給できる可能性があり、あるいは、第２結果２９５をより簡単にコピーし、この結果をそれ自体の結果として渡すことができる可能性がある。
【００４９】
あるいは、第１計算２８０が、信頼されないコンピューティングノード１３０が５０％超の確率で正しい答えを推測することを可能にするタイプのものである場合がある。そのような場合には、信頼されないコンピューティングノード１３０は、第１計算２８０の実行を止めることができ、正しい結果となる大きい可能性のゆえに、毎回結果を単純に推測することができる。
【００５０】
そのような情況を検出するのを助けるために、分析モジュール２７０は、確率モジュール２７５を含むことができる。確率モジュールは、第１結果２８５および第２結果２９５に１つまたは複数の確率関数を適用して、これらの結果が有効であるかどうかならびに信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０が信頼できるものであるかどうかを判定することができる。したがって、第１結果２８５および第２結果２９５が正しく判定され、単に正しく推測されたのでも盗まれたのでもないことの確率の判定は、中央コンピューティングシステム１１０が、信頼されないコンピューティングノード１３０、１４０、１５０、１６０、および１７０の信頼性を検証する追加の形を提供する。いくつかの確率関数の例を、これから述べる。
【００５１】
ある大きいタスク（第１計算２８０など）が、多数のｘに関するｆ（ｘ）の計算を必要とすると仮定する。ｆ：Ｘ→Ｙであるものとする。ｘが一様に分布する確率変数であると考えられる場合に、ｆ（ｘ）の確率分布が狭過ぎ、その結果、正しい値の推測が妥当と思われるようになる場合には、ｆは、結果ｙに加えて、ある中間状態ｓを出力するように変更される。したがって、ｆ（ｘ）＝（ｓ，ｒ）である。未知の真の結果を、ｙ１＝（ｓ，ｒ）を用いて表す。
【００５２】
εが、ノードが所有する背景情報であるものとする。ノードが作業を実行しない確率を、Ｐ（Ｅ（ｎ））によって表す。Ｅ（ｎ））の場合には、ノードｎは、作業を偽造することを試みている。この場合に、ノードが推測していると言う。正しい答えを推測する確率を、Ｐ（ｙ＝ｙ１｜ε）によって表す。
【００５３】
作業要求ｆ（ｘ）は、ある計算ノードｎに与えられる。それと同時に、別の作業要求ｆ（ｘ’）が生成される。ｆ（ｘ’）＝（ｓ’，ｒ’）であるものとする。ｘ’を選択するために、まず、ｘ’＝ｇ（ｘ）である場合に限ってｇ（ｓ）＝ｓ’かつｇ（ｒ）＝ｒ’になる、変換関数ｇ：Ｘ→Ｘを見つける。作業要求ｆ（ｘ’）は、別のノードｎ２に与えられ、変換ｇ∈Ｇが、秘密として保たれる。
【００５４】
Ｐ（ｎｉ（ｇ）｜ε）は、ノードｎｉが秘密の変換ｇを学習するか推測する確率であるものとする。ｇが、大きい空間から選択され、その秘密がセキュアに保たれる場合には、Ｐ（ｎｉ（ｇ）｜ε）は、小さくなる。
【００５５】
次に、両方のノードは、それに割り当てられた作業を実行すると主張し、結果ｙ＝（ｓ，ｒ）およびｙ１＝（ｓ’，ｒ’）を報告する。下の表１に、可能である、ノードの異なる結果のさまざまな確率を示す。言い換えると、さまざまな情況に関してｙ＝ｙ１がどうなるかを示す。
【００５６】
【表１】
表１
【００５７】
したがって、ｙがｙ１と等しくない確率は
【００５８】
【数１】
である。
【００５９】
図３は、信頼されないコンピューティングノードによって実行された作業を検証する方法３００の例示的実施形態の流れ図である。図示の実施形態では、方法３００ならびに本明細書で説明する他の方法およびプロセスは、処理ステップ、機能動作、イベント、および／または行為などとして説明することができ、ハードウェア、ソフトウェア、および／またはファームウェアによって実行できる、さまざまな機能ブロックまたはアクションを示す。方法３００は、ブロック３０２、３０４、３０６、３０８、３１０、および／または３１２によって示されるように、１つまたは複数の動作を含む。ブロック３０２では、第１の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき第１計算を決定する。たとえば、１つの例示的実施形態では、計算生成モジュール２３０が、信頼されないコンピューティングノード１３０などの第１の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき第１計算２８０を生成することができる。いくつかの実施形態では、第１計算２８０を、第１計算コンポーネント２８０ａ、２８０ｂ、および２８０ｃに分割することができる。
【００６０】
ブロック３０４では、第２の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき同等の第２計算を作るために第１計算に適用されるべき変換関数を決定する。たとえば、１つの例示的実施形態では、変換関数モジュール２４０は、第１計算２８０のタイプに基づいて、変換関数２４５を生成することができる。もう１つの例示的実施形態では、変換関数モジュールは、コンピューティングシステム１１０のユーザまたは別のコンピューティングシステムから変換関数を入手することができる。変換関数２４５を、第１計算２８０に適用して、信頼されないコンピューティングノード１４０などの第２の信頼されないコンピューティングノードによって実行できる第２計算２９０を作ることができる。いくつかの実施形態では、変換関数２４５を、複数の変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃを含む変換空間とすることができる。
【００６１】
ブロック３０６では、第１計算を、第１の信頼されないコンピューティングノードに割り当て、ブロック３０８では、第２計算を、第２の信頼されないコンピューティングノードに割り当てる。第１の信頼されないコンピューティングノードおよび第２の信頼されないコンピューティングノードへの第１計算および第２計算の割当ては、それぞれ、第１および第２の信頼されないコンピューティングノードから変換関数を秘密に保ちながら行われる。たとえば、１つの例示的実施形態では、割当てモジュール２５０が、第１計算２８０を信頼されないコンピューティングノード１３０に割り当てることができ、第２計算２９０を信頼されないコンピューティングノード１４０に割り当てることができる。
【００６２】
ブロック３１０では、第１計算の第１結果を第１の信頼されないコンピューティングノードから受け取り、第２計算の第２結果を第２の信頼されないコンピューティングノードから受け取る。たとえば、１つの例示的実施形態では、受取モジュール２６０は、信頼されないコンピューティングノード１３０から第１結果２８５を受け取ることができ、信頼されないコンピューティングノード１４０から第２結果２９５を受け取ることができる。いくつかの実施形態では、第１結果２８５は、第１中間結果２８５ａ、２８５ｂ、および２８５ｃを含むことができる。第２結果２９５は、第２中間結果２９５ａ、２９５ｂ、および２９５ｃを含むことができる。
【００６３】
ブロック３１２では、第１結果および第２結果を分析して、信頼されないコンピューティングノードによって実行された作業を検証する。１つの例示的実施形態では、分析モジュール２７０は、第１結果２８５および第２結果２９５を分析して、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０によって実行された作業を検証することができる。この形で、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０の信頼性を判定することができる。
【００６４】
いくつかの実施形態では、分析モジュール２７０は、第２結果２９５から変換関数２４５を除去し、その後、第２結果２９５を第１結果２８５と比較する。結果が実施的に同一である場合には、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０が有効な結果を供給した可能性が高い。しかし、結果が異なる場合には、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０の一方または両方が無効な結果を供給した可能性が高い。
【００６５】
ヒストリカルデータベースにアクセスすることもでき、その結果、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０の実行の履歴を、以前に説明したように判定することができる。さらに、１つまたは複数の確率関数を結果に適用して、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０の信頼性を判定するのを助けることができる。
【００６６】
方法３００は、信頼されないコンピューティングノード１３０および信頼されないコンピューティングノード１４０が、結果の推測または無効な結果の供給などの詐欺にかかわったかどうかを中央コンピューティングシステム１１０が判定するための機構を提供する。さらに、方法３００は、中央コンピューティングシステム１１０が、無効な結果を提供するための信頼されないコンピューティングノード１３０と信頼されないコンピューティングノード１４０との間の共謀を判定することを可能にする。
【００６７】
当業者は、上記ならびに本明細書で開示される他のプロセスおよび方法について、それらのプロセスおよび方法で実行される機能を、異なる順序で実施できることを了解するであろう。さらに、概要を示されたステップおよび動作は、例としてのみ提供され、ステップおよび方法の一部を、開示される実施形態の本質から逸脱せずに、オプションとし、より少数のステップおよび動作に組み合わせ、あるいは追加のステップおよび動作に拡張することができる。
【００６８】
図４は、信頼されないコンピューティングノードによって実行された作業を検証する代替の方法４００の例示的実施形態の流れ図である。方法４００は、ブロック４０２、４０４、４０６、４０８、４１０、４１２、４１４、４１６、および／または４１８によって示される１つまたは複数の動作を含む。ブロック４０２では、第１計算および変換関数コンポーネントを含む変換空間を選択する。たとえば、第１計算２８０を、計算生成モジュール２３０によって選択することができる。変換関数コンポーネント２４５ａ、２４５ｂ、および２４５ｃを含む変換関数２４５を、第１計算２８０に基づいて変換関数モジュール２４０によって選択することができる。
【００６９】
ブロック４０４では、第１計算をコンポーネントに分割する。たとえば、第１計算２８０を、計算生成モジュール２３０によって第１計算コンポーネント２８０ａ、２８０ｂ、および２８０ｃに分割することができる。
【００７０】
ブロック４０６では、変換関数コンポーネントのうちの１つを、第１計算コンポーネントのうちの１つに適用するためにランダムに選択する。これが、第２計算を作る。たとえば、第１変換関数サブセット２４５ａをランダムに選択し、ランダムに選択された第１計算サブセット２８０ａに適用することができる。これは、第２計算２９０を作ることができる。
【００７１】
ブロック４０８では、第１計算サブセットおよび第２計算を実行するために、信頼されないコンピューティングノードの対をランダムに選択する。たとえば、割当てモジュール２５０は、第１計算サブセット２８０ａを実行するために信頼されないコンピューティングノード１３０を、第２計算２９０を実行するために信頼されないコンピューティングノード１４０をランダムに選択することができる。
【００７２】
ブロック４１０では、ランダムに選択された変換関数サブセットを秘密に保ちながら、第１計算サブセットが、第１の信頼されないコンピューティングノードに割り当てられ、第２計算が、第２の信頼されないコンピューティングノードに割り当てられる。たとえば、割当てモジュール２５０は、第１計算サブセット２８０ａを信頼されないコンピューティングノード１３０に割り当てることができ、第２計算２９０を信頼されないコンピューティングノード１４０に割り当てることができる。変換関数サブセット２４５ａは、信頼されないコンピューティングノードから秘密に保たれる。
【００７３】
ブロック４１２では、第１結果を第１の信頼されないコンピューティングノードから受け取り、第２結果を第２の信頼されないコンピューティングノードから受け取る。たとえば、受取モジュール２６０は、信頼されないコンピューティングノード１３０から第１結果２８５を受け取ることができ、信頼されないコンピューティングノード１４０から第２結果２９５を受け取ることができる。
【００７４】
ブロック４１４では、第１結果および第２結果を分析する。たとえば、分析モジュール２７０は、第１結果２８５および第２結果２９５を、前に説明した形のいずれかで分析することができる。
【００７５】
ブロック４１６では、第１結果および第２結果をデータベースに記録する。たとえば、第１結果２８５および第２結果２９５を、データベース２２０に記録することができる。結果を、ヒストリ２２５に追加することができ、前に説明したように信頼されないコンピューティングノードの信頼性を判定するのを助けるのに使用することができる。
【００７６】
判断ブロック４１８では、結果が有効であったかどうかを判定する。この判定は、前に説明したように、結果の比較、ヒストリカル分析、および確率関数の適用を使用して行うことができる。
【００７７】
結果が、有効である可能性が高いと判定される場合には（判断ブロック４１８のＹｅｓ）、この方法は、実行すべき他の計算がない場合に終了することができる。そうではなく、実行すべき他の計算がある場合には、この方法はブロック４０２に戻り、この方法が繰り返される。
【００７８】
結果が、有効である可能性が高くはないと判定される場合には（判断ブロック４１８のＮｏ）、この方法は、ブロック４０６に戻ることができ、ここで、第１および第２の信頼されないコンピューティングノードとは異なる、２つの新しい信頼されないコンピューティングノードを、ランダムに選択することができる。その後、方法４００の残りのブロックを実行して、新たに選択された信頼されないコンピューティングノードが有効な結果を供給するかどうかを判定することができる。たとえば、ブロック４０６に戻った後に、割当てモジュール２５０は、第１計算サブセット２８０ａを実行するために信頼されないコンピューティングノード１５０をランダムに選択することができ、第２計算２９０を実行するために信頼されないコンピューティングノード１６０をランダムに選択することができる。その後、方法４００の残りのブロックを実行することができる。
【００７９】
本開示は、さまざまな態様の例示として意図された、本願で説明される特定の実施形態に関して限定されてはならない。当業者が了解するように、その趣旨および範囲から逸脱せずに、多数の修正形態および変形形態を作ることができる。本明細書で列挙されるものに加えて、本開示の範囲に含まれる機能的に同等の方法および装置は、前述の説明から当業者には明白であろう。そのような修正形態および変形形態は、添付の特許請求の範囲の範囲に含まれることが意図されている。本開示は、添付の特許請求の範囲に与えられる同等物のすべての範囲に加えて、添付の特許請求の範囲の項目のみによって限定されなければならない。本開示が、もちろん変化することのできる特定の方法、試薬、化合物、合成物、または生体系に限定されてはならないことを理解されたい。本明細書で使用される用語法が、特定の実施形態を説明するためのみのものであって、限定的であることを意図されていないことをも理解されたい。
【００８０】
例示的実施形態では、本明細書で説明される動作、プロセスなどのいずれをも、コンピュータ可読媒体に格納されたコンピュータ可読命令として実施することができる。コンピュータ可読命令を、モバイルユニット、ネットワーク要素、および／または任意の他のコンピューティングデバイスのプロセッサによって実行することができる。
【００８１】
システムの諸態様のハードウェア実施態様とソフトウェア実施態様との間には、区別がほとんど残されておらず、ハードウェアまたはソフトウェアの使用は、一般に（ある文脈でハードウェアとソフトウェアとの間の選択が重要になり得るという点で、必ずではないが）、コスト対効率のトレードオフを表す設計選択である。本明細書で説明されるプロセスおよび／またはシステムおよび／または他のテクノロジを実施できるさまざまな手段（たとえば、ハードウェア、ソフトウェア、および／またはファームウェア）があり、その上、好ましい手段は、それらのプロセスおよび／またはシステムおよび／または他のテクノロジが展開される文脈に伴って変化する。たとえば、実装者が、速度および正確さが主要であると判定する場合に、実装者は、主にハードウェア手段および／またはファームウェア手段を選ぶことができ、柔軟性が主要である場合には、実装者は、主にソフトウェア実施態様を選ぶことができ、あるいは、やはりその代わりに、実装者は、ハードウェア、ソフトウェア、および／またはファームウェアのある組合せを選ぶことができる。
【００８２】
前述の詳細な説明は、ブロック図、流れ図、および／または例の使用を介してデバイスおよび／またはプロセスのさまざまな実施形態を示した。そのようなブロック図、流れ図、および／または例が、１つまたは複数の機能および／または動作を含む限り、そのようなブロック図、流れ図、または例に含まれる各機能および／または各動作を、個別におよび／または集合的に、広範囲のハードウェア、ソフトウェア、ファームウェア、または事実上すべてのその組合せによって実施できることが、当業者によって理解されるであろう。一実施形態では、本明細書で説明される主題の複数の部分を、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、ディジタル信号プロセッサ（ＤＳＰ）、または他の集積フォーマットを介して実施することができる。しかし、当業者は、本明細書で開示される実施形態のいくつかの態様を、全体的にまたは部分的に、集積回路内で、１つまたは複数のコンピュータ上で動作する１つまたは複数のコンピュータプログラムとして（たとえば、１つまたは複数のコンピュータシステム上で動作する１つまたは複数のプログラムとして）、１つまたは複数のプロセッサ上で動作する１つまたは複数のプログラムとして（たとえば、１つまたは複数のマイクロプロセッサ上で動作する１つまたは複数のプログラムとして）、ファームウェアとして、または事実上すべてのそれらの組合せとして同等に実施できることと、回路網の設計ならびに／あるいはソフトウェアおよびまたはファームウェアのコードの記述が、本開示を考慮すると当業者の技量に十分に含まれることとを認めるであろう。さらに、当業者は、本明細書で説明される主題の機構を、さまざまな形でプログラム製品として配布できることと、本明細書で説明される主題の例示的実施形態が、配布を実際に実行するのに使用される信号担持媒体の特定のタイプにかかわりなく適用されることとを了解するであろう。信号担持媒体の例は、フロッピディスク、ハードディスクドライブ、ＣＤ、ＤＶＤ、ディジタルテープ、コンピュータメモリ、その他などの記録可能型媒体と、ディジタル通信媒体および／またはアナログ通信媒体（たとえば、光ファイバケーブル、導波管、有線通信リンク、無線通信リンクなど）などの伝送型媒体とを含むが、これらに限定はされない。
【００８３】
当業者は、当技術分野で、デバイスおよび／またはプロセスを本明細書で示す形で記述し、その後、工学的実践を使用して、そのように記述されたデバイスおよび／またはプロセスをデータ処理システムに統合することが一般的であることを認めるであろう。すなわち、本明細書で説明されるデバイスおよび／またはプロセスの少なくとも一部を、妥当な量の実験を介してデータ処理システムに統合することができる。当業者は、通常のデータ処理システムが、一般に、システムユニットハウジング、ビデオディスプレイデバイス、揮発性メモリおよび不揮発性メモリなどのメモリ、マイクロプロセッサおよびディジタル信号プロセッサなどのプロセッサ、オペレーティングシステム、ドライバ、グラフィカルユーザインターフェース、およびアプリケーションプログラムなどの計算エンティティ、タッチパッドまたはタッチスクリーンなどの１つまたは複数の対話デバイス、ならびに／あるいはフィードバックループおよび制御モータ（たとえば、位置および／または速度を感知するフィードバック、コンポーネントおよび／または量を移動しかつ／または調整する制御モータ）を含む制御システムのうちの１つまたは複数を含むことを認めるであろう。通常のデータ処理システムを、一般にデータコンピューティング／通信および／またはネットワークコンピューティング／通信システムで見られるものなど、任意の適切な市販コンポーネントを利用して実施することができる。
【００８４】
本明細書で説明される主題は、時々、異なる他のコンポーネントに含まれるかこれに接続される異なるコンポーネントを示す。そのような図示のアーキテクチャが、単に例示であることと、実際に、同一の機能性を達成する多数の他のアーキテクチャを実施できることとを理解されたい。概念的な意味で、同一の機能性を達成するためのコンポーネントのすべての配置は、所望の機能性が達成されるように効果的に「関連付けられる」。したがって、特定の機能性を達成するために組み合わされる本明細書の任意の２つのコンポーネントを、アーキテクチャまたは中間コンポーネントにかかわりなく、所望の機能性が達成されるように互いに「関連付けられる」と見なすことができる。同様に、そのように関連付けられた任意の２つのコンポーネントを、所望の機能性を達成するために互いに「動作可能に接続される」または「動作可能に結合される」と見なすこともでき、そのように関連付けられ得る任意の２つのコンポーネントを、所望の機能性を達成するために互いに「動作可能に結合可能である」と見なすこともできる。動作可能に結合可能の特定の例は、物理的に嵌合可能なコンポーネントおよび／または物理的に相互作用するコンポーネント、ならびに／あるいは無線で相互作用可能なコンポーネントおよび／または無線で相互作用するコンポーネント、ならびに／あるいは論理的に相互作用するコンポーネントおよび／または論理的に相互作用可能なコンポーネントを含むが、これらに限定はされない。
【００８５】
図５に、本開示による分散コンピューティングシステム内の信頼されないコンピューティングノードによって実行された作業を検証するために配置された例のコンピューティングデバイス５００を示す。非常に基本的な構成５０２では、コンピューティングデバイス５００は、一般に、１つまたは複数のプロセッサ５０４およびシステムメモリ５０６を含む。メモリバス５０８を、プロセッサ５０４とシステムメモリ５０６との間で通信するのに使用することができる。
【００８６】
所望の構成に応じて、プロセッサ５０４を、マイクロプロセッサ（μＰ）、マイクロコントローラ（μＣ）、ディジタル信号プロセッサ（ＤＳＰ）、またはその任意の組合せを含むがこれらに限定はされない任意のタイプのプロセッサとすることができる。プロセッサ５０４は、レベル１キャッシュ５１０およびレベル２キャッシュ５１２などのキャッシングのもう１つのレベル、プロセッサコア５１４、およびレジスタ５１６を含むことができる。例のプロセッサコア５１４は、算術論理ユニット（ＡＬＵ）、浮動小数点ユニット（ＦＰＵ）、ディジタル信号処理コア（ＤＳＰコア）、またはその任意の組合せを含むことができる。例のメモリコントローラ５１８を、プロセッサ５０４と共に使用することもでき、あるいは、いくつかの実施態様では、メモリコントローラ５１８を、プロセッサ５０４の内部の部分とすることができる。
【００８７】
所望の構成に応じて、システムメモリ５０６を、揮発性メモリ（ＲＡＭなど）、不揮発性メモリ（ＲＯＭ、フラッシュメモリ、その他など）、またはその任意の組合せを含むがこれらに限定はされない任意のタイプのメモリとすることができる。システムメモリ５０６は、オペレーティングシステム５２０、１つまたは複数のアプリケーション５２２、およびプログラムデータ５２４を含むことができる。アプリケーション５２２は、図３の方法３００および図４の方法４００に関して説明されたものを含む本明細書で説明される機能を実行するように配置された検証アプリケーション５２６を含むことができる。プログラムデータ５２４は、信頼されないコンピューティングノードによって供給された結果を分析するのに有用である可能性がある分析情報５２８を含むことができる。いくつかの実施形態では、アプリケーション５２２を、本明細書で説明されるように信頼されないコンピューティングノードによって実行された作業を検証できるように、オペレーティングシステム５２０上でプログラムデータ５２４を用いて動作するように配置することができる。この説明された基本構成５０２は、図５では、内側の破線の中のコンポーネントによって示されている。
【００８８】
コンピューティングデバイス５００は、基本構成５０２と任意の必要なデバイスおよびインターフェースとの間の通信を容易にする追加の特徴または機能性ならびに追加のインターフェースを有することができる。たとえば、バス／インターフェースコントローラ５３０を使用して、基本構成５０２と１つまたは複数のデータストレージデバイス５３２との間のストレージインターフェースバス５３４を介する通信を容易にすることができる。データストレージデバイス５３２は、リムーバブルストレージデバイス５３６、ノンリムーバブルストレージデバイス５３８、またはその組合せとすることができる。リムーバブルストレージデバイスおよびノンリムーバブルストレージデバイスの例は、少数を挙げると、フレキシブルディスクドライブおよびハードディスクドライブ（ＨＤＤ）などの磁気ディスクデバイス、コンパクトディスク（ＣＤ）ドライブまたはディジタル多用途ディスク（ＤＶＤ）ドライブなどの光ディスクドライブ、ソリッドステートドライブ（ＳＳＤ）、およびテープドライブを含む。コンピュータ記憶媒体の例は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報のストレージのための任意の方法またはテクノロジで実施された、揮発性および不揮発性の、リムーバブルおよびノンリムーバブルの媒体を含むことができる。
【００８９】
システムメモリ５０６、リムーバブルストレージデバイス５３６、およびノンリムーバブルストレージデバイス５３８は、コンピュータ記憶媒体の例である。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、もしくは他のメモリテクノロジ、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）、もしくは他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、もしくは他の磁気ストレージデバイス、または所望の情報を格納するのに使用でき、コンピューティングデバイス５００によってアクセスできる任意の他の媒体を含むが、これらに限定はされない。すべてのそのようなコンピュータ記憶媒体を、コンピューティングデバイス５００の一部とすることができる。
【００９０】
コンピューティングデバイス５００は、さまざまなインターフェースデバイス（たとえば、出力デバイス５４２、周辺インターフェース５４４、および通信デバイス５４６）から基本構成５０２へのバス／インターフェースコントローラ５３０を介する通信を容易にするインターフェースバス５４０をも含むことができる。例の出力デバイス５４２は、グラフィックス処理ユニット５４８およびオーディオ処理ユニット５５０を含み、グラフィックス処理ユニット５４８およびオーディオ処理ユニット５５０は、１つまたは複数のＡ／Ｖポート５５２を介してディスプレイまたはスピーカなどのさまざまな外部デバイスと通信するように構成され得る。例の周辺インターフェース５４４は、シリアルインターフェースコントローラ５５４またはパラレルインターフェースコントローラ５５６を含み、シリアルインターフェースコントローラ５５４またはパラレルインターフェースコントローラ５５６は、入力デバイス（たとえば、キーボード、マウス、ペン、音声入力デバイス、タッチ入力デバイスなど）などの外部デバイスまたは他の周辺デバイス（たとえば、プリンタ、スキャナなど）と１つまたは複数のＩ／Ｏポート５５８を介して通信するように構成され得る。例の通信デバイス５４６は、ネットワークコントローラ５６０を含み、ネットワークコントローラ５６０は、ネットワーク通信リンクを介し、１つまたは複数の通信ポート５６４を介する１つまたは複数の他のコンピューティングデバイス５６２との通信を容易にするように配置され得る。
【００９１】
ネットワーク通信リンクを、通信媒体の１つの例とすることができる。通信媒体を、一般に、搬送波または他のトランスポート機構などの変調されたデータ信号内のコンピュータ可読命令、データ構造、プログラムモジュール、または他のデータによって実施することができ、通信媒体は、任意の情報配布媒体を含むことができる。「変調されたデータ信号」は、その特性のうちの１つまたは複数を、信号内で情報を符号化する形でセットされまたは変更された信号とすることができる。限定ではなく例として、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体と、音響、ラジオ周波数（ＲＦ）、マイクロ波、赤外線（ＩＲ）、および他の無線媒体などの無線媒体とを含むことができる。用語コンピュータ可読媒体は、本明細書で使用されるときに、記憶媒体と通信媒体との両方を含むことができる。
【００９２】
コンピューティングデバイス５００を、セル電話機、携帯情報端末（ＰＤＡ）、パーソナルメディアプレイヤデバイス、無線ウェブウォッチデバイス、パーソナルヘッドセットデバイス、特定用途向けデバイス、または上記の機能のいずれかを含むハイブリッドデバイスなどの小フォームファクタのポータブル（またはモバイル）電子デバイスの一部として実施することができる。コンピューティングデバイス５００を、ラップトップコンピュータ構成と非ラップトップコンピュータ構成との両方を含むパーソナルコンピュータとして実施することもできる。
【００９３】
本明細書での実質的にすべての複数形および／または単数形の用語の使用に関して、当業者は、文脈および／または応用例に適切に、複数形から単数形におよび／または単数形から複数形に変換することができる。さまざまな単数／複数の置換が、明瞭にするために本明細書で明示的に示される場合がある。
【００９４】
一般に、本明細書、特に添付の特許請求の範囲（たとえば、添付の特許請求の範囲の本体）で使用される用語は、一般に、「オープンな」用語として意図されていること（たとえば、用語「ｉｎｃｌｕｄｉｎｇ（含む）」は、「ｉｎｃｌｕｄｉｎｇ ｂｕｔ ｎｏｔ ｌｉｍｉｔｅｄ ｔｏ（を含むがこれに限定されない）」と解釈されなければならず、用語「ｈａｖｉｎｇ（有する）」は、「ｈａｖｉｎｇ ａｔ ｌｅａｓｔ（少なくとも〜を有する）」と解釈されなければならず、用語「ｉｎｃｌｕｄｅｓ（含む）」は、「ｉｎｃｌｕｄｅｓ ｂｕｔ ｉｓ ｎｏｔ ｌｉｍｉｔｅｄ ｔｏ（を含むがこれに限定されない）」と解釈されなければならないことなど）が、当業者によって理解されるであろう。さらに、特定の個数の導入される請求項の記述が意図される場合には、そのような意図が、特許請求の範囲で明示的に記述され、そのような記述がない場合には、そのような意図が存在しないことが、当業者によって理解されるであろう。たとえば、理解の助けとして、次の添付の特許請求の範囲は、請求項の記述を導入するために導入句「ａｔ ｌｅａｓｔ ｏｎｅ（少なくとも１つの）」および「ｏｎｅ ｏｒ ｍｏｒｅ（１つまたは複数の）」の使用を含む場合がある。しかし、そのような句の使用は、同一の請求項が導入句「ｏｎｅ ｏｒ ｍｏｒｅ」または「ａｔ ｌｅａｓｔ ｏｎｅ」および「ａ」または「ａｎ」などの不定冠詞を含むときであっても、不定冠詞「ａ」または「ａｎ」による請求項の記述の導入が、そのように導入された請求項の記述を含む任意の特定の請求項を１つのみのそのような記述を含む実施形態に限定することを暗示すると解釈されてはならず（たとえば、「ａ」および／または「ａｎ」は、「ａｔ ｌｅａｓｔ ｏｎｅ」または「ｏｎｅ ｏｒ ｍｏｒｅ」を意味すると解釈されなければならない）、同一のことが、請求項の記述を導入するのに使用される定冠詞の使用にもあてはまる。さらに、特定の個数の導入される請求項の記述が明示的に記述される場合であっても、当業者は、そのような記述を、少なくとも記述された数を意味する（たとえば、他の修飾成句を伴わない「２つの記述」という最低限の記述は、少なくとも２つの記述または複数の記述を意味する）と解釈しなければならないことを認めるであろう。さらに、「ａｔ ｌｅａｓｔ ｏｎｅ ｏｆ Ａ，Ｂ，ａｎｄ Ｃ，ｅｔｃ．（Ａ、Ｂ、およびＣのうちの少なくとも１つ、など）」に類似する慣例が使用される場合に、一般に、そのような構文は、当業者がその慣例を理解する意味であることが意図されている（たとえば、「ａ ｓｙｓｔｅｍ ｈａｖｉｎｇ ａｔ ｌｅａｓｔ ｏｎｅ ｏｆ Ａ，Ｂ，ａｎｄ Ｃ（Ａ、Ｂ、およびＣのうちの少なくとも１つを有するシステム）」は、Ａのみ、Ｂのみ、Ｃのみ、ＡとＢとを一緒に、ＡとＣとを一緒に、ＢとＣとを一緒に、ならびに／またはＡ、Ｂ、およびＣを一緒に有するシステムを含むが、これに限定はされないなど）。「ａｔ ｌｅａｓｔ ｏｎｅ ｏｆ Ａ，Ｂ，ｏｒ Ｃ，ｅｔｃ．（Ａ、Ｂ、またはＣのうちの少なくとも１つ、など）」に類似する慣例が使用される場合に、一般に、そのような構文は、当業者がその慣例を理解する意味であることが意図されている（たとえば、「ａ ｓｙｓｔｅｍ ｈａｖｉｎｇ ａｔ ｌｅａｓｔ ｏｎｅ ｏｆ Ａ，Ｂ，ｏｒ Ｃ（Ａ、Ｂ、またはＣのうちの少なくとも１つを有するシステム）」は、Ａのみ、Ｂのみ、Ｃのみ、ＡとＢとを一緒に、ＡとＣとを一緒に、ＢとＣとを一緒に、ならびに／またはＡ、Ｂ、およびＣを一緒に有するシステムを含むが、これに限定はされないなど）。さらに、複数の代替の項目を表す事実上すべての選言的単語および／または句は、明細書、特許請求の範囲、または図面のいずれに含まれるものであれ、項目のうちの１つ、項目のいずれか、または両方の項目を含む可能性を企図すると理解されなければならないことが、当業者によって理解されるであろう。たとえば、句「Ａ ｏｒ Ｂ（ＡまたはＢ）」は、「Ａ」または「Ｂ」または「ＡおよびＢ」の可能性を含むと理解される。
【００９５】
さらに、本開示の特徴または態様が、Ｍａｒｋｕｓｈ ｇｒｏｕｐに関して説明される場合に、当業者は、本開示が、これによってＭａｒｋｕｓｈ ｇｒｏｕｐの任意の個々のメンバまたはメンバのサブグループに関しても説明されることを認めるであろう。
【００９６】
当業者によって理解されるように、書面による説明を提供することに関してなど、すべてにおいて、本明細書で開示されるすべての範囲は、任意のすべての可能な部分範囲およびその部分範囲の組合せをも包含する。すべてのリストされた範囲を、少なくとも等しい半分、１／３、１／４、１／５、１／１０などに分割された同一の範囲を十分に記述し、可能にするものとしてたやすく認めることができる。非限定的な例として、本明細書で述べられる各範囲を、下側１／３、中央１／３、および上側１／３などにたやすく分解することができる。やはり当業者によって理解されるように、「ｕｐ ｔｏ（まで）」、「ａｔ ｌｅａｓｔ（少なくとも）」、および類似物などのすべての言葉は、記述された数を含み、その後に上で述べたように部分範囲に分割され得る範囲に言及する。最後に、当業者によって理解されるように、範囲は、各個々のメンバを含む。したがって、たとえば、１〜３個のセルを有する群は、１個、２個、または３個のセルを有する群に言及する。同様に、１〜５個のセルを有する群は、１個、２個、３個、４個、または５個のセルを有する群に言及するなどである。
【００９７】
前述から、本開示のさまざまな実施形態が、本明細書で例示のために説明されたことと、さまざまな変更を、本開示の範囲および趣旨から逸脱せずに行うことができることとを了解されたい。したがって、本明細書で開示されるさまざまな実施形態は、限定的であることを意図されてはおらず、真の範囲および趣旨は、次の特許請求の範囲によって示される。
【特許請求の範囲】
【請求項１】
中央コンピューティングシステムに動作可能に結合された複数の信頼されないコンピューティングノードを含むコンピューティングシステムにおいて、前記中央コンピューティングシステムが前記複数の信頼されないコンピューティングノードによって実行された作業を検証する方法であって、
第１の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき第１計算を前記中央コンピューティングシステムで決定することと、
第２計算を作るために前記第１計算に適用されるべき変換関数を前記中央コンピューティングシステムで決定することであって、前記変換関数は、前記第２計算を前記第１計算と同等にするように構成され、前記第２計算は、第２の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべきものである、決定することと、
前記第１の信頼されないコンピューティングノードによって実行されるために前記第１計算を前記中央コンピューティングシステムで割り当てることと、
前記変換関数を前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードから秘密に保ちながら、前記第２の信頼されないコンピューティングノードによって実行されるために前記第２計算を前記中央コンピューティングシステムで割り当てることと、
前記第１計算の第１結果を前記第１の信頼されないコンピューティングノードから、および前記第２計算の第２結果を前記第２の信頼されないコンピューティングノードから、前記中央コンピューティングシステムで受け取ることと、
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を前記中央コンピューティングシステムで分析することと
を含む方法。
【請求項２】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を分析することは、
前記第２結果から前記変換関数を除去することと、
前記第２結果を前記第１結果と比較することであって、前記変換関数を除去することは、前記第１計算および前記第２計算がそれぞれ正しく実行され、有効な結果が提供された時に、前記第２結果を前記第１結果と実質的に同一にする、比較することと
を含み、前記第１結果と前記第２結果との間の差は、前記第１の信頼されないコンピューティングノードもしくは前記第２の信頼されないコンピューティングノードのいずれかまたは両方のノードが無効な結果を提供したことを表わす、
請求項１に記載の方法。
【請求項３】
前記第１計算を複数の第１計算コンポーネントに分割することをさらに含む、請求項１に記載の方法。
【請求項４】
複数の変換関数コンポーネントを含む変換関数を決定することと、
前記第２計算を複数の第２計算コンポーネントに分割することと、
前記複数の変換関数コンポーネントの第１変換関数サブセットを選択することと、
前記第２計算を作るために前記複数の第１計算コンポーネントのうちの１つに前記第１変換関数サブセットを適用することと
をさらに含む、請求項３に記載の方法。
【請求項５】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードのそれぞれは、複数の信頼されないコンピューティングノードのうちの１つであり、前記方法は、
前記第１の信頼されないコンピューティングノードに前記第１計算を割り当てることは、前記中央コンピューティングシステムが、前記複数の信頼されないコンピューティングノードから前記第１の信頼されないコンピューティングノードをランダムに選択し、前記第１の信頼されないコンピューティングノードに前記第１計算サブセットをランダムに割り当てることを含み、
前記第２の信頼されないコンピューティングノードに前記第２計算を割り当てることは、前記中央コンピューティングシステムが、前記複数の信頼されないコンピューティングノードから前記第２の信頼されないコンピューティングノードをランダムに選択し、前記第２の信頼されないコンピューティングノードに前記第２計算をランダムに割り当てることを含む
をさらに含む、請求項４に記載の方法。
【請求項６】
前記第１結果および前記第２結果を、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードによって実行された過去の計算からの結果を含むデータベースに格納することと、
前記データベースに格納された前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードのそれぞれの結果全体に基づいて、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードが信頼できるかどうかを判定することであって、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードは、前記格納された結果の過半数が有効である場合には信頼できる可能性が高く、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードは、前記格納された結果の過半数が無効である場合には信頼できる可能性が高くはない、判定することと
をさらに含む、請求項１に記載の方法。
【請求項７】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を分析することは、前記第１結果および前記第２結果が有効であるかどうかを判定するために、前記第１結果および前記第２結果に１つまたは複数の確率関数を適用することを含む、請求項１に記載の方法。
【請求項８】
前記第１結果および前記第２結果が有効ではないと判定する時に、前記第１計算および前記第２計算を実行するために第３の信頼されないコンピューティングノードおよび第４の信頼されないコンピューティングノードをランダムに選択することをさらに含む、請求項７に記載の方法。
【請求項９】
中央コンピューティングシステムが前記中央コンピューティングシステムと通信する複数の信頼されないコンピューティングノードによって実行された作業を検証する方法を実施するために、前記中央コンピューティングシステムで使用されるコンピュータプログラム製品であって、プロセッサによって実行される時に、前記中央コンピューティングシステムに、
第１の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき第１計算を決定することと、
第２計算を作るために前記第１計算に適用されるべき変換関数を決定することであって、前記変換関数は、前記第２計算を前記第１計算と同等にするように構成され、前記第２計算は、第２の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべきものである、決定することと、
前記第１の信頼されないコンピューティングノードによって実行されるために前記第１計算を割り当てることと、
前記変換関数を前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードから秘密に保ちながら、前記第２の信頼されないコンピューティングノードによって実行されるために前記第２計算を割り当てることと、
前記第１計算の第１結果を前記第１の信頼されないコンピューティングノードから、および前記第２計算の第２結果を前記第２の信頼されないコンピューティングノードから、受け取ることと、
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を分析することと
を行わせるコンピュータ実行可能命令をその上に格納された１つまたは複数の有形のコンピュータ可読媒体を含む、コンピュータプログラム製品。
【請求項１０】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を分析することは、
前記第２結果から前記変換関数を除去することと、
前記第２結果を前記第１結果と比較することであって、前記変換関数を除去することは、前記第１計算および前記第２計算のそれぞれが正しく実行され、有効な結果が提供された時に、前記第２結果を前記第１結果と実質的に同一にする、比較することと
を含み、前記第１結果と前記第２結果との間の差は、前記第１の信頼されないコンピューティングノードもしくは前記第２の信頼されないコンピューティングノードのいずれかまたは両方の信頼されないコンピューティングノードが無効な結果を提供したことを表わす、
請求項９に記載のコンピュータプログラム製品。
【請求項１１】
前記コンピュータ実行可能命令は、プロセッサによって実行される時に、さらに、前記中央コンピューティングシステムに、前記第１計算を複数の第１計算コンポーネントに分割させる、請求項９に記載のコンピュータプログラム製品。
【請求項１２】
前記コンピュータ実行可能命令は、プロセッサによって実行される時に、さらに、前記中央コンピューティングシステムに、
複数の変換関数コンポーネントを含む変換関数を決定することと、
前記第２計算を複数の第２計算コンポーネントに分割することと、
前記複数の変換関数コンポーネントの第１変換サブセットを選択することと、
前記第２計算を作るために前記複数の第１計算コンポーネントのうちの１つに前記第１変換関数サブセットを適用することと
を行わせる請求項１１に記載のコンピュータプログラム製品。
【請求項１３】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードのそれぞれは、複数の信頼されないコンピューティングノードのうちの１つであり、
前記第１の信頼されないコンピューティングノードに前記第１計算を割り当てることは、前記複数の信頼されないコンピューティングノードから前記第１の信頼されないコンピューティングノードをランダムに選択し、前記第１の信頼されないコンピューティングノードに前記複数の第１計算コンポーネントのうちの前記１つをランダムに割り当てることを含み、
前記第２の信頼されないコンピューティングノードに前記第２計算を割り当てることは、前記中央コンピューティングシステムが、前記複数の信頼されないコンピューティングノードから前記第２の信頼されないコンピューティングノードをランダムに選択し、前記第２の信頼されないコンピューティングノードに前記第２計算をランダムに割り当てることを含む
請求項１２に記載のコンピュータプログラム製品。
【請求項１４】
前記コンピュータ実行可能命令は、プロセッサによって実行される時に、さらに、前記中央コンピューティングシステムに、
前記第１結果および前記第２結果を、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードによって実行された過去の計算からの結果を含むデータベースに格納することと、
前記データベースに格納された前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードのそれぞれの結果全体に基づいて、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードが信頼できるかどうかを判定することであって、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードは、前記格納された結果の過半数が有効である場合には信頼できる可能性が高く、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードは、前記格納された結果の過半数が無効である場合には信頼できる可能性が高くはない、判定することと
を行わせる請求項９に記載のコンピュータプログラム製品。
【請求項１５】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を分析することは、前記第１結果および前記第２結果が有効であるかどうかを判定するために、前記第１結果および前記第２結果に１つまたは複数の確率関数を適用することを含む、請求項９に記載のコンピュータプログラム製品。
【請求項１６】
前記第１結果および前記第２結果が有効ではないと判定する時に、第３の信頼されないコンピューティングノードおよび第４の信頼されないコンピューティングノードが、前記第１計算および前記第２計算を実行するためにランダムに選択される、請求項１５に記載のコンピュータプログラム製品。
【請求項１７】
コンピューティングシステムであって、
プロセッサと、
前記コンピューティングシステムに結合された第１の信頼されないコンピューティングノードによって実行されるべき第１計算を生成するように構成された計算生成モジュールと、
第２計算を作るために前記第１計算に適用されるべき変換関数を生成するように構成された変換関数モジュールであって、前記変換関数は、前記第２計算を前記第１計算と同等にするように構成され、前記第２計算は、第２の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべきものである、変換関数モジュールと、
前記第１の信頼されないコンピューティングノードによって実行されるために前記第１計算を割り当てるように構成され、前記変換関数を前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードから秘密に保ちながら、前記第２の信頼されないコンピューティングノードによって実行されるために前記第２計算を割り当てるように構成された割当てモジュールと、
前記第１計算の第１結果を前記第１の信頼されないコンピューティングノードから、および前記第２計算の第２結果を前記第２の信頼されないコンピューティングノードから、受け取るように構成された受取モジュールと、
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を分析するように構成された分析モジュールと
を含むコンピューティングシステム。
【請求項１８】
前記第１結果は、一連の第１中間結果を含み、
前記第２結果は、一連の第２中間結果を含み、
前記分析モジュールは、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードが無効な結果を提供したかどうかを判定するために、前記第１中間結果を前記第２中間結果と比較するようにさらに構成される
請求項１７に記載のコンピューティングシステム。
【請求項１９】
前記変換関数は、前記第２中間結果に適用される、請求項１８に記載のコンピューティングシステム。
【請求項２０】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって提供された前記結果の妥当性のヒストリを含むデータベースをさらに含み、前記ヒストリは、前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードの信頼性を判定するために前記コンピューティングシステムによって使用される、請求項１７に記載のコンピューティングシステム。
【請求項１】
中央コンピューティングシステムに動作可能に結合された複数の信頼されないコンピューティングノードを含むコンピューティングシステムにおいて、前記中央コンピューティングシステムが前記複数の信頼されないコンピューティングノードによって実行された作業を検証する方法であって、
第１の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき第１計算を前記中央コンピューティングシステムで決定することと、
第２計算を作るために前記第１計算に適用されるべき変換関数を前記中央コンピューティングシステムで決定することであって、前記変換関数は、前記第２計算を前記第１計算と同等にするように構成され、前記第２計算は、第２の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべきものである、決定することと、
前記第１の信頼されないコンピューティングノードによって実行されるために前記第１計算を前記中央コンピューティングシステムで割り当てることと、
前記変換関数を前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードから秘密に保ちながら、前記第２の信頼されないコンピューティングノードによって実行されるために前記第２計算を前記中央コンピューティングシステムで割り当てることと、
前記第１計算の第１結果を前記第１の信頼されないコンピューティングノードから、および前記第２計算の第２結果を前記第２の信頼されないコンピューティングノードから、前記中央コンピューティングシステムで受け取ることと、
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を前記中央コンピューティングシステムで分析することと
を含む方法。
【請求項２】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を分析することは、
前記第２結果から前記変換関数を除去することと、
前記第２結果を前記第１結果と比較することであって、前記変換関数を除去することは、前記第１計算および前記第２計算がそれぞれ正しく実行され、有効な結果が提供された時に、前記第２結果を前記第１結果と実質的に同一にする、比較することと
を含み、前記第１結果と前記第２結果との間の差は、前記第１の信頼されないコンピューティングノードもしくは前記第２の信頼されないコンピューティングノードのいずれかまたは両方のノードが無効な結果を提供したことを表わす、
請求項１に記載の方法。
【請求項３】
前記第１計算を複数の第１計算コンポーネントに分割することをさらに含む、請求項１に記載の方法。
【請求項４】
複数の変換関数コンポーネントを含む変換関数を決定することと、
前記第２計算を複数の第２計算コンポーネントに分割することと、
前記複数の変換関数コンポーネントの第１変換関数サブセットを選択することと、
前記第２計算を作るために前記複数の第１計算コンポーネントのうちの１つに前記第１変換関数サブセットを適用することと
をさらに含む、請求項３に記載の方法。
【請求項５】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードのそれぞれは、複数の信頼されないコンピューティングノードのうちの１つであり、前記方法は、
前記第１の信頼されないコンピューティングノードに前記第１計算を割り当てることは、前記中央コンピューティングシステムが、前記複数の信頼されないコンピューティングノードから前記第１の信頼されないコンピューティングノードをランダムに選択し、前記第１の信頼されないコンピューティングノードに前記第１計算サブセットをランダムに割り当てることを含み、
前記第２の信頼されないコンピューティングノードに前記第２計算を割り当てることは、前記中央コンピューティングシステムが、前記複数の信頼されないコンピューティングノードから前記第２の信頼されないコンピューティングノードをランダムに選択し、前記第２の信頼されないコンピューティングノードに前記第２計算をランダムに割り当てることを含む
をさらに含む、請求項４に記載の方法。
【請求項６】
前記第１結果および前記第２結果を、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードによって実行された過去の計算からの結果を含むデータベースに格納することと、
前記データベースに格納された前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードのそれぞれの結果全体に基づいて、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードが信頼できるかどうかを判定することであって、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードは、前記格納された結果の過半数が有効である場合には信頼できる可能性が高く、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードは、前記格納された結果の過半数が無効である場合には信頼できる可能性が高くはない、判定することと
をさらに含む、請求項１に記載の方法。
【請求項７】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を分析することは、前記第１結果および前記第２結果が有効であるかどうかを判定するために、前記第１結果および前記第２結果に１つまたは複数の確率関数を適用することを含む、請求項１に記載の方法。
【請求項８】
前記第１結果および前記第２結果が有効ではないと判定する時に、前記第１計算および前記第２計算を実行するために第３の信頼されないコンピューティングノードおよび第４の信頼されないコンピューティングノードをランダムに選択することをさらに含む、請求項７に記載の方法。
【請求項９】
中央コンピューティングシステムが前記中央コンピューティングシステムと通信する複数の信頼されないコンピューティングノードによって実行された作業を検証する方法を実施するために、前記中央コンピューティングシステムで使用されるコンピュータプログラム製品であって、プロセッサによって実行される時に、前記中央コンピューティングシステムに、
第１の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべき第１計算を決定することと、
第２計算を作るために前記第１計算に適用されるべき変換関数を決定することであって、前記変換関数は、前記第２計算を前記第１計算と同等にするように構成され、前記第２計算は、第２の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべきものである、決定することと、
前記第１の信頼されないコンピューティングノードによって実行されるために前記第１計算を割り当てることと、
前記変換関数を前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードから秘密に保ちながら、前記第２の信頼されないコンピューティングノードによって実行されるために前記第２計算を割り当てることと、
前記第１計算の第１結果を前記第１の信頼されないコンピューティングノードから、および前記第２計算の第２結果を前記第２の信頼されないコンピューティングノードから、受け取ることと、
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を分析することと
を行わせるコンピュータ実行可能命令をその上に格納された１つまたは複数の有形のコンピュータ可読媒体を含む、コンピュータプログラム製品。
【請求項１０】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を分析することは、
前記第２結果から前記変換関数を除去することと、
前記第２結果を前記第１結果と比較することであって、前記変換関数を除去することは、前記第１計算および前記第２計算のそれぞれが正しく実行され、有効な結果が提供された時に、前記第２結果を前記第１結果と実質的に同一にする、比較することと
を含み、前記第１結果と前記第２結果との間の差は、前記第１の信頼されないコンピューティングノードもしくは前記第２の信頼されないコンピューティングノードのいずれかまたは両方の信頼されないコンピューティングノードが無効な結果を提供したことを表わす、
請求項９に記載のコンピュータプログラム製品。
【請求項１１】
前記コンピュータ実行可能命令は、プロセッサによって実行される時に、さらに、前記中央コンピューティングシステムに、前記第１計算を複数の第１計算コンポーネントに分割させる、請求項９に記載のコンピュータプログラム製品。
【請求項１２】
前記コンピュータ実行可能命令は、プロセッサによって実行される時に、さらに、前記中央コンピューティングシステムに、
複数の変換関数コンポーネントを含む変換関数を決定することと、
前記第２計算を複数の第２計算コンポーネントに分割することと、
前記複数の変換関数コンポーネントの第１変換サブセットを選択することと、
前記第２計算を作るために前記複数の第１計算コンポーネントのうちの１つに前記第１変換関数サブセットを適用することと
を行わせる請求項１１に記載のコンピュータプログラム製品。
【請求項１３】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードのそれぞれは、複数の信頼されないコンピューティングノードのうちの１つであり、
前記第１の信頼されないコンピューティングノードに前記第１計算を割り当てることは、前記複数の信頼されないコンピューティングノードから前記第１の信頼されないコンピューティングノードをランダムに選択し、前記第１の信頼されないコンピューティングノードに前記複数の第１計算コンポーネントのうちの前記１つをランダムに割り当てることを含み、
前記第２の信頼されないコンピューティングノードに前記第２計算を割り当てることは、前記中央コンピューティングシステムが、前記複数の信頼されないコンピューティングノードから前記第２の信頼されないコンピューティングノードをランダムに選択し、前記第２の信頼されないコンピューティングノードに前記第２計算をランダムに割り当てることを含む
請求項１２に記載のコンピュータプログラム製品。
【請求項１４】
前記コンピュータ実行可能命令は、プロセッサによって実行される時に、さらに、前記中央コンピューティングシステムに、
前記第１結果および前記第２結果を、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードによって実行された過去の計算からの結果を含むデータベースに格納することと、
前記データベースに格納された前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードのそれぞれの結果全体に基づいて、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードが信頼できるかどうかを判定することであって、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードは、前記格納された結果の過半数が有効である場合には信頼できる可能性が高く、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードは、前記格納された結果の過半数が無効である場合には信頼できる可能性が高くはない、判定することと
を行わせる請求項９に記載のコンピュータプログラム製品。
【請求項１５】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を分析することは、前記第１結果および前記第２結果が有効であるかどうかを判定するために、前記第１結果および前記第２結果に１つまたは複数の確率関数を適用することを含む、請求項９に記載のコンピュータプログラム製品。
【請求項１６】
前記第１結果および前記第２結果が有効ではないと判定する時に、第３の信頼されないコンピューティングノードおよび第４の信頼されないコンピューティングノードが、前記第１計算および前記第２計算を実行するためにランダムに選択される、請求項１５に記載のコンピュータプログラム製品。
【請求項１７】
コンピューティングシステムであって、
プロセッサと、
前記コンピューティングシステムに結合された第１の信頼されないコンピューティングノードによって実行されるべき第１計算を生成するように構成された計算生成モジュールと、
第２計算を作るために前記第１計算に適用されるべき変換関数を生成するように構成された変換関数モジュールであって、前記変換関数は、前記第２計算を前記第１計算と同等にするように構成され、前記第２計算は、第２の信頼されないコンピューティングノードによって少なくとも部分的に実行されるべきものである、変換関数モジュールと、
前記第１の信頼されないコンピューティングノードによって実行されるために前記第１計算を割り当てるように構成され、前記変換関数を前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードから秘密に保ちながら、前記第２の信頼されないコンピューティングノードによって実行されるために前記第２計算を割り当てるように構成された割当てモジュールと、
前記第１計算の第１結果を前記第１の信頼されないコンピューティングノードから、および前記第２計算の第２結果を前記第２の信頼されないコンピューティングノードから、受け取るように構成された受取モジュールと、
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって実行された前記作業を検証するために前記第１結果および前記第２結果を分析するように構成された分析モジュールと
を含むコンピューティングシステム。
【請求項１８】
前記第１結果は、一連の第１中間結果を含み、
前記第２結果は、一連の第２中間結果を含み、
前記分析モジュールは、前記第１の信頼されないコンピューティングノードまたは前記第２の信頼されないコンピューティングノードが無効な結果を提供したかどうかを判定するために、前記第１中間結果を前記第２中間結果と比較するようにさらに構成される
請求項１７に記載のコンピューティングシステム。
【請求項１９】
前記変換関数は、前記第２中間結果に適用される、請求項１８に記載のコンピューティングシステム。
【請求項２０】
前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードによって提供された前記結果の妥当性のヒストリを含むデータベースをさらに含み、前記ヒストリは、前記第１の信頼されないコンピューティングノードおよび前記第２の信頼されないコンピューティングノードの信頼性を判定するために前記コンピューティングシステムによって使用される、請求項１７に記載のコンピューティングシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公表番号】特表２０１２−５３０３２８（Ｐ２０１２−５３０３２８Ａ）
【公表日】平成２４年１１月２９日（２０１２．１１．２９）
【国際特許分類】
【出願番号】特願２０１２−５２５５８３（Ｐ２０１２−５２５５８３）
【出願日】平成２２年７月２１日（２０１０．７．２１）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０４２７８２
【国際公開番号】ＷＯ２０１２／０１１９０２
【国際公開日】平成２４年１月２６日（２０１２．１．２６）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＢＬＵＥＴＯＯＴＨ
【出願人】（５０９３４８７８６）エンパイア テクノロジー ディベロップメント エルエルシー (117)
【Ｆターム（参考）】
【公表日】平成２４年１１月２９日（２０１２．１１．２９）
【国際特許分類】
【出願日】平成２２年７月２１日（２０１０．７．２１）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０４２７８２
【国際公開番号】ＷＯ２０１２／０１１９０２
【国際公開日】平成２４年１月２６日（２０１２．１．２６）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＢＬＵＥＴＯＯＴＨ
【出願人】（５０９３４８７８６）エンパイア テクノロジー ディベロップメント エルエルシー (117)
【Ｆターム（参考）】
[ Back to top ]