集中型アルゴリズムを分散アルゴリズムに変換する方法

Question

集中アルゴリズムを分散アルゴリズムに変換するためのアルゴリズムまたは手順はありますか？理論的結果または関連する複雑さ分析はありますか？

Answer 1

必ず。 Nマシンを使用して分散システムがある場合は、マシン1で集中型アルゴリズムを実行し、マシン2..Nに静止している。

すべての順次アルゴリズムを並列化できるかどうかを尋ねる場合、それは開いている質問ですが、その答えはNo： NC複雑度クラス。ウィキペディアの州として、

おそらく「本質的に順次」されているいくつかの扱いやすい問題があり、並列処理を使用することによって大きくスピードアップすることはできません。

P-Completeの問題は、並列処理によってスピードアップすることができない可能性が高い問題に対する優れた候補です。

あなたがすべてのアルゴリズムを分散システムで信頼できるものであるかどうかを尋ねるなら、それはあなたが検討しているどんな種類の障害にかかっている微妙な質問です。あなたはコンセンサスプロトコル、状態マシンレプリケーション、およびキャップ定理