分散コンピューティングは、コンピュータサイエンスの分野であり、相互通信コンポーネントが異なるネットワークコンピュータ上に配置されているコンピュータシステムとして定義される分散システムを研究する。[1] [2]

分散システムのコンポーネントは、共通の目標を達成するために、メッセージを互いに渡すことで通信し、アクションを調整します。 分散システムの 3 つの課題は、コンポーネントの同時実行性の維持、グローバル クロックの欠如の克服、コンポーネントの独立した障害の管理です。[1] 1 つのシステムのコンポーネントで障害が発生しても、システム全体に障害が発生することはありません。[3]分散システムの例は、SOA ベースのシステムからマイクロサービス、大規模マルチプレイヤー オンライン ゲーム、ピアツーピア アプリケーションまで多岐にわたります。 分散システムは、主に追加のハードウェア、サーバー、ゲートウェイ、ファイアウォール、新しいサブネット、プロキシなどの必要性が高まるため、モノリシック アーキテクチャよりもコストがかかります。[4]分散システムは、分散コンピューティングの誤解に悩まされることもあります。逆に、適切に設計された分散システムは、単一のマシンに展開されたモノリシック アプリケーションよりもスケーラブルで、耐久性があり、変更しやすく、微調整されています。[5]マーク・ブルッカーによれば、「システムは、追加のワークロードの限界費用がほぼ一定である範囲で拡張可能である」とのことです。サーバーレス技術はこの定義に当てはまりますが、インフラコストだけでなく、総所有コストも考慮する必要があります。[6]

分散システム内で実行されるコンピュータプログラムは分散プログラムと呼ばれ、[ 7 ]分散プログラミングとはそのようなプログラムを書くプロセスです。[8]メッセージパッシングメカニズムの実装には、純粋なHTTP、 RPCのようなコネクタ、メッセージキューなど、多くの種類があります。[9]

分散コンピューティングは、計算上の問題を解決するために分散システムを使用することも指します。分散コンピューティングでは、問題は多数のタスクに分割され、各タスクは1台以上のコンピュータ[10]によって解決されます。これらのコンピュータはメッセージパッシングを介して相互に通信します。[11]

導入

「分散システム」「分散プログラミング」「分散アルゴリズム」などの用語で使われる「分散」という言葉は、もともと個々のコンピュータが物理的に特定の地理的領域内に分散しているコンピュータネットワークを指していました。[12]現在では、この用語ははるかに広い意味で使用されており、物理的に同じコンピュータ上で実行され、メッセージの受け渡しによって相互にやり取りする自律的なプロセスを指すこともあります。[11]

分散システムには単一の定義はありませんが[13]、一般的に2つの共通する特性が挙げられます。

  • いくつかの自律的な計算エンティティ（コンピュータまたはノード）があり、それぞれが独自のローカルメモリを持っています。[14]
  • エンティティはメッセージパッシングによって互いに通信します。[15]

分散システムは、大規模な計算問題を解決するなど、共通の目標を持つ場合があります。[16]この場合、ユーザーは自律的なプロセッサの集合を一つのユニットとして認識します。一方、各コンピュータには個別のニーズを持つユーザーがおり、分散システムの目的は共有リソースの利用を調整したり、ユーザーに通信サービスを提供したりすることです。[17]

分散システムのその他の一般的な特性は次のとおりです。

  • システムは個々のコンピュータの障害を許容する必要がある。[18]
  • システムの構造 (ネットワーク トポロジ、ネットワーク遅延、コンピューターの数) は事前にわかりません。
  • システムは、さまざまな種類のコンピューターとネットワーク リンクで構成される場合があります。
  • 分散プログラムの実行中にシステムが変化する可能性がある。[19]
  • 各コンピューターは、システムに関して限定的で不完全なビューを持っています。
  • 各コンピュータは入力の一部しか認識できない。[20]

パターン

分散コンピューティングに使われる一般的なアーキテクチャパターンは以下のとおりです。 [21]

イベントとメッセージ

分散システムでは、イベントは事実または状態の変化（例：OrderPlaced）を表し、通常は複数のコンシューマーに非同期的にブロードキャストされるため、疎結合とスケーラビリティが促進されます。イベントは一般的に即時の応答を期待しませんが、確認応答メカニズムはイベントパターン自体に固有のものではなく、インフラストラクチャレベルで実装されることがよくあります（例：Kafkaコミットオフセット、SNS配信ステータス）。[22] [23]

対照的に、メッセージはより広範な役割を果たし、コマンド（例：ProcessPayment）、イベント（例：PaymentProcessed）、ドキュメント（例：DataPayload）を網羅します。イベントとメッセージはどちらも、技術スタックと実装に応じて、少なくとも1回、最大1回、正確に1回など、さまざまな配信保証をサポートできます。ただし、正確に1回の配信は、真のインフラストラクチャレベルの正確に1回だけのセマンティクスではなく、冪等性メカニズムによって実現されることがよくあります。[22] [23]

イベントとメッセージの配信パターンには、パブリッシュ/サブスクライブ（1対多）とポイントツーポイント（1対1）があります。リクエスト/リプライも技術的には可能ですが、純粋なイベント駆動型システムよりもメッセージングパターンと関連付けられることが一般的です。イベントは状態の伝播と分離された通知に優れており、メッセージはコマンド実行、ワークフローオーケストレーション、明示的な調整に適しています。[22] [23]

現代のアーキテクチャでは、一般的に両方のアプローチを組み合わせて、分散状態変更通知のためのイベントと、特定のタイミング、順序、配信要件に基づいたターゲットコマンド実行と構造化ワークフローのためのメッセージを活用しています。[22] [23]

並列および分散コンピューティング

(a)、(b): 分散システム。
(c): 並列システム。

分散システムとは、ネットワーク化されたコンピュータ群が共通の目標を持って動作するシステムです。「同時コンピューティング」「並列コンピューティング」「分散コンピューティング」という用語には多くの共通点があり、明確な区別はありません。[24]同じシステムが「並列」と「分散」の両方の特徴を持つ場合もあります。典型的な分散システムでは、プロセッサは同時に並列に動作します。[25]並列コンピューティングは、分散コンピューティングの中でも特に密結合した形態と捉えることができ、[26]分散コンピューティングは並列コンピューティングの中でも疎結合な形態と捉えることができます。[13]ただし、同時システムを以下の基準で大まかに「並列」または「分散」に分類することは可能です。

  • 並列コンピューティングでは、すべてのプロセッサが共有メモリにアクセスしてプロセッサ間で情報を交換することができます。[27]
  • 分散コンピューティングでは、各プロセッサは独自のプライベートメモリ（分散メモリ）を持ちます。情報はプロセッサ間でメッセージをやり取りすることで交換されます。[28]

右の図は、分散システムと並列システムの違いを示しています。図(a)は典型的な分散システムの概略図です。システムはネットワークトポロジとして表現され、各ノードはコンピュータであり、ノード間を接続する各線は通信リンクです。図(b)は、同じ分散システムをより詳細に示しています。各コンピュータは独自のローカルメモリを持ち、利用可能な通信リンクを使用してノード間でメッセージを渡すことによってのみ、情報を交換できます。図(c)は、各プロセッサが共有メモリに直接アクセスできる並列システムを示しています。

状況はさらに複雑化しており、並列アルゴリズムと分散アルゴリズムという用語の従来の用法は、上記の並列システムと分散システムの定義とは必ずしも一致していません（詳細は後述）。しかしながら、大まかに言えば、共有メモリ型マルチプロセッサにおける高性能並列計算には並列アルゴリズムが用いられ、大規模分散システムの調整には分散アルゴリズムが用いられます。[29]

歴史

メッセージパッシングを介して通信する並行プロセスの使用は、1960年代に研究されたオペレーティングシステムアーキテクチャにその起源があります。 [30]最初に広く普及した分散システムは、1970年代に発明されたイーサネットなどのローカルエリアネットワークでした。[31]

インターネットの前身の一つであるARPANETは1960年代後半に導入され、ARPANET電子メールは1970年代初頭に発明されました。電子メールはARPANETの最も成功したアプリケーションとなり[32]、おそらく大規模分散アプリケーションの最も初期の例と言えるでしょう。ARPANET（およびその後継であるグローバルインターネット）に加えて、初期の世界的なコンピュータネットワークには、 1980年代のUsenetとFidoNetがあり、どちらも分散型ディスカッションシステムをサポートするために使用されました[33] 。

分散コンピューティングの研究は、1970年代後半から1980年代初頭にかけて、コンピュータサイエンスの独立した分野として発展しました。この分野における最初の会議である「分散コンピューティングの原理に関するシンポジウム（PODC）」は1982年に開催され、その対極にある「分散コンピューティングに関する国際シンポジウム（DISC）」は、1985年にオタワで「グラフ上の分散アルゴリズムに関する国際ワークショップ」として初めて開催されました。[34]

分散コンピューティングアーキテクチャ

分散コンピューティングには、様々なハードウェアおよびソフトウェアアーキテクチャが用いられます。低レベルでは、複数のCPUを何らかのネットワークで相互接続する必要があります。このネットワークは、回路基板上にプリントされているか、疎結合されたデバイスとケーブルで構成されているかに関わらず、相互接続する必要があります。高レベルでは、これらのCPU上で実行されるプロセスを何らかの通信システムで相互接続する必要があります。[35]

これらの CPU がリソースを共有するかどうかによって、3 種類のアーキテクチャの最初の区別が決まります。

分散プログラミングは、通常、クライアントサーバー、3層、n層、ピアツーピアなどの基本的なアーキテクチャ、または疎結合、密結合のいずれかに分類されます。[36]

分散コンピューティング・アーキテクチャのもう一つの基本的な側面は、同時実行プロセス間の通信と作業調整の方法である。様々なメッセージパッシング・プロトコルを介して、プロセスは互いに直接通信することができ、通常はメイン／サブの関係となる。一方、「データベース中心」アーキテクチャでは、共有データベースを利用することで、直接的なプロセス間通信を一切行わずに分散コンピューティングを実行できる。[39]特にデータベース中心アーキテクチャは、ライブ環境のリレーを可能にする図式的なアーキテクチャにおいて、リレーショナル処理分析を提供する。これにより、ネットワーク・データベースのパラメータ内外を問わず、分散コンピューティング機能を実現できる。[40]

セルベースアーキテクチャ

セルベースアーキテクチャは、計算リソースをセルと呼ばれる自己完結的なユニットに編成する分散コンピューティングアプローチです。各セルは独立して動作し、スケーラビリティ、障害分離、可用性を維持しながらリクエストを処理します。[41] [42] [43]

セルは通常、複数のサービスまたはアプリケーションコンポーネントで構成され、自律的なユニットとして機能します。実装によっては、サービスセット全体を複数のセルに複製するものもありますが、ワークロードをセル間で分割するものもあります。複製モデルでは、別のセルに障害が発生した場合、リクエストは稼働中のセルに再ルーティングされることがあります。この設計は、局所的な障害の影響を軽減することで、システムの回復力を高めることを目的としています。[44] [45] [46]

一部の実装では、セル内およびセル間にサーキットブレーカーが採用されています。セル内では、サーキットブレーカーはサービス間の連鎖的な障害を防ぐために使用され、セル間のサーキットブレーカーは障害が発生したセルを分離し、稼働中のセルにトラフィックをリダイレクトします。[47] [48] [49]

セルベースアーキテクチャは、特にクラウドネイティブ環境や高可用性環境において、障害分離と冗長性が設計上の重要な考慮事項となる大規模分散システムの一部に採用されています。その実装は、システム要件、インフラストラクチャの制約、運用目標によって異なります。[50] [51] [52]

アプリケーション

分散システムと分散コンピューティングを使用する理由としては、次のようなものが挙げられます。

  • アプリケーションの性質上、複数のコンピューターを接続する通信ネットワークの使用が必要になる場合があります。たとえば、ある物理的な場所で生成されたデータが別の場所で必要になる場合などです。
  • 原理的には単一のコンピュータで実行可能なケースも数多くありますが、実用上は分散システムの使用が有利です。例えば、
    • 単一のマシンよりもはるかに大きなストレージとメモリ、より高速なコンピューティング、より高い帯域幅を実現できます。
    • 単一障害点が存在しないため、非分散システムよりも高い信頼性を提供できます。さらに、分散システムはモノリシックなユニプロセッサシステムよりも拡張性と管理性に優れている場合があります。[53]
    • 単一のハイエンド コンピュータと比較すると、複数のローエンド コンピュータのクラスターを使用して必要なレベルのパフォーマンスを実現する方がコスト効率が高くなる可能性があります。

例

分散システムと分散コンピューティングのアプリケーションの例としては、次のようなものがある。[54]

リアクティブ分散システム

リアクティブ宣言によれば、リアクティブ分散システムは、応答性、回復力、弾力性、そしてメッセージ駆動性に優れています。したがって、リアクティブシステムはより柔軟で、疎結合かつスケーラブルです。システムをリアクティブにするには、リアクティブ原則を実装することをお勧めします。リアクティブ原則とは、クラウドネイティブアプリケーションだけでなく、エッジネイティブアプリケーションのリアクティブ性を高めるのに役立つ一連の原則とパターンです。[56]

理論的基礎

モデル

コンピュータを用いて自動化したいタスクの多くは、質問と回答の型です。つまり、私たちが質問を投げかけ、コンピュータが答えを導き出すことを期待するのです。理論計算機科学では、このようなタスクは計算問題と呼ばれます。正式には、計算問題はインスタンスと、各インスタンスに対する解から構成されます。インスタンスとは、私たちが尋ねることができる質問であり、解とは、これらの質問に対する望ましい答えです。

理論計算機科学は、どのような計算問題が計算機を用いて解けるのか（計算可能性理論）、またどの程度効率的に解けるのか（計算複雑性理論）を理解しようとするものである。伝統的に、与えられたインスタンスに対して正しい解を生成するアルゴリズムを設計できれば、その問題は計算機を用いて解けると言われている。このようなアルゴリズムは、汎用計算機上で動作する計算機プログラムとして実装することができる。すなわち、プログラムは入力から問題のインスタンスを読み取り、何らかの計算を実行し、解を出力として生成する。ランダムアクセスマシンや汎用チューリングマシンなどの形式主義は、このようなアルゴリズムを実行する逐次型汎用計算機の抽象モデルとして用いることができる。[57] [58]

並行コンピューティングと分散コンピューティングの分野では、複数のコンピュータ、あるいは相互作用するプロセスのネットワークを実行するコンピュータにおいて、同様の問いが研究されています。そのようなネットワークでは、どのような計算問題が、そしてどれほど効率的に解決できるのでしょうか？しかし、並行システムや分散システムにおける「問題を解決する」とは一体何を意味するのか、全く明らかではありません。例えば、アルゴリズム設計者の仕事は何なのか、そして、逐次型汎用コンピュータの並行システムや分散システムに相当するものは何なのか？[要出典]

以下の説明は複数のコンピューターの場合に焦点を当てていますが、多くの問題は単一のコンピューターで実行される同時プロセスでも同じです。

一般的に使用される 3 つの視点は次のとおりです。

共有メモリモデルにおける並列アルゴリズム
  • すべてのプロセッサは共有メモリにアクセスできます。アルゴリズム設計者は、各プロセッサで実行するプログラムを選択します。
  • 理論的なモデルの一つとして、並列ランダムアクセスマシン（PRAM）が用いられる。[59]しかし、古典的なPRAMモデルは、共有メモリへの同期アクセスを前提としている。
  • 基盤となるオペレーティング システムがノード間の通信をカプセル化し、すべての個別システムにわたってメモリを仮想的に統合する場合、共有メモリ プログラムを分散システムに拡張できます。
  • 現実世界のマルチプロセッサマシンの挙動により近く、比較・スワップ（CAS）などの機械語命令の使用を考慮したモデルとして、非同期共有メモリモデルがあります。このモデルに関する幅広い研究が行われており、その概要は文献に記載されています。[60] [61]
メッセージパッシングモデルにおける並列アルゴリズム
  • アルゴリズム設計者は、ネットワークの構造と、各コンピューターで実行されるプログラムを選択します。
  • ブール回路やソーティングネットワークなどのモデルが用いられる。[62]ブール回路はコンピュータネットワークとして捉えることができ、各ゲートは非常に単純なコンピュータプログラムを実行するコンピュータである。同様に、ソーティングネットワークもコンピュータネットワークとして捉えることができ、各コンパレータはコンピュータである。
メッセージパッシングモデルにおける分散アルゴリズム
  • アルゴリズム設計者はコンピュータプログラムを選択するだけです。すべてのコンピュータは同じプログラムを実行します。システムはネットワークの構造に関わらず正しく動作する必要があります。
  • 一般的に使用されるモデルは、ノードごとに1 つの有限状態マシンを持つグラフです。

分散アルゴリズムの場合、計算上の問題は典型的にはグラフと関連しています。多くの場合、コンピュータネットワークの構造を記述するグラフが問題のインスタンスとなります。これは次の例で示されています。[63]

例

与えられたグラフGの彩色を求める計算問題を考えてみましょう。分野によっては、以下のようなアプローチが考えられます。

集中型アルゴリズム[63]
  • グラフGは文字列としてエンコードされ、その文字列がコンピュータに入力として与えられます。コンピュータプログラムはグラフの色付けを求め、その色付けを文字列としてエンコードし、結果を出力します。
並列アルゴリズム
  • グラフGは文字列としてエンコードされていますが、複数のコンピュータが同じ文字列に並列にアクセスすることができます。各コンピュータはグラフの一部に焦点を絞り、その部分の色付けを行う可能性があります。
  • 主な焦点は、複数のコンピューターの処理能力を並列に活用する高性能計算にあります。
分散アルゴリズム
  • グラフGはコンピュータネットワークの構造です。Gの各ノードには1台のコンピュータがあり、 Gの各エッジには1つの通信リンクがあります。初期状態では、各コンピュータはグラフG内の直近のコンピュータの情報しか持ちません。コンピュータは互いにメッセージを交換することで、 Gの構造をより深く理解する必要があります。各コンピュータは、出力として独自の色を生成する必要があります。
  • 主な焦点は、任意の分散システムの運用を調整することにあります。[63]

並列アルゴリズムの分野は分散アルゴリズムの分野とは異なる焦点を当てていますが、両分野の間には多くの相互作用があります。例えば、グラフ彩色のためのコール・ビシュキンアルゴリズム[64]は、もともと並列アルゴリズムとして提示されましたが、同じ手法を分散アルゴリズムとしても直接使用することができます。

さらに、並列アルゴリズムは、並列システム（共有メモリを使用）または分散システム（メッセージパッシングを使用）のいずれかで実装できます。[65]並列アルゴリズムと分散アルゴリズムの従来の境界（適切なネットワークを選択する vs. 任意のネットワークで実行する）は、並列システムと分散システム（共有メモリ vs. メッセージパッシング）の境界と同じではありません。

複雑さの尺度

並列アルゴリズムでは、時間と空間に加えて、コンピュータの数もリソースとして必要となる。実際、実行時間とコンピュータの数の間にはトレードオフの関係があることが多い。並列に動作するコンピュータの数が多いほど、問題をより速く解くことができる（「スピードアップ」を参照）。ある決定問題が多項式数のプロセッサを用いて多対数時間で解ける場合、その問題はNCクラスに属すると言われる。[66] NCクラスは、PRAM形式やブール回路を用いて同様に定義することができる。PRAMマシンはブール回路を効率的にシミュレートでき、その逆もまた同様である。[67]

分散アルゴリズムの分析では、通常、計算ステップよりも通信操作に重点が置かれます。分散コンピューティングの最も単純なモデルは、おそらくすべてのノードが同期的に動作する同期システムです。このモデルは一般にLOCALモデルとして知られています。各通信ラウンドにおいて、すべてのノードは並列に(1)隣接ノードから最新のメッセージを受信し、(2)任意のローカル計算を実行し、(3)隣接ノードに新しいメッセージを送信します。このようなシステムでは、タスクを完了するために必要な同期通信ラウンドの数を複雑さの指標として捉えるのが一般的です。[68]

この複雑性の尺度は、ネットワークの直径と密接に関連しています。ネットワークの直径をDとします。一方で、同期分散システムでは、あらゆる計算可能な問題は、約2Dの通信ラウンドで自明に解決できます。つまり、すべての情報を1か所に集め（Dラウンド）、問題を解決し、各ノードに解を通知するだけです（Dラウンド）。

一方、アルゴリズムの実行時間がD回の通信ラウンドよりもはるかに短い場合、ネットワーク内のノードは、ネットワークの遠隔部分に関する情報を取得する可能性がないまま出力を生成しなければなりません。言い換えれば、ノードはローカルなD近傍で利用可能な情報に基づいて、グローバルに一貫性のある決定を下す必要があります。多くの分散アルゴリズムは実行時間がDラウンドよりもはるかに短いことが知られており、そのようなアルゴリズムでどのような問題を解くことができるかを理解することは、この分野の中心的な研究課題の1つです。[69]通常、ネットワークサイズで多重対数時間で問題を解決するアルゴリズムは、このモデルでは効率的であると見なされます。

もう一つのよく使われる指標は、ネットワークで送信されるビットの総数です（通信複雑性を参照）。[70]この概念の特徴は、通常、CONGEST(B)モデルで捉えられます。このモデルはLOCALモデルと同様に定義されますが、単一のメッセージにはBビットしか含めることができません。

その他の問題

従来の計算問題は、ユーザーが質問を投げかけ、コンピュータ（または分散システム）が質問を処理し、答えを生成して停止するという考え方に基づいています。しかし、食事哲学者問題や類似の排他制御問題など、システムが停止しないことが求められる問題もあります。これらの問題では、分散システムは共有リソースの使用を継続的に調整し、競合やデッドロックが発生しないようにする必要があります。

分散コンピューティングに特有の根本的な課題も存在します。例えば、フォールトトレランスに関連する課題などです。関連する問題の例としては、コンセンサス問題[71] 、 ビザンチンフォールトトレランス[72]、自己安定化[73]などが挙げられます。

分散システムの 非同期性を理解することにも多くの研究が焦点を当てています。

分散システムでは、 「中央値」や「平均」では誤解を招く可能性があるため、レイテンシは「99パーセンタイル」で測定する必要があることに注意してください。[77]

選挙

コーディネータ選出（またはリーダー選出）とは、複数のコンピュータ（ノード）に分散されたタスクのオーガナイザとして単一のプロセスを選出するプロセスです。タスクが開始される前は、ネットワーク上のすべてのノードは、どのノードがタスクの「コーディネータ」（またはリーダー）となるかを認識していないか、現在のコーディネータと通信できません。しかし、コーディネータ選出アルゴリズムが実行されると、ネットワーク全体の各ノードは、特定のノードをタスクコーディネータとして認識します。[78]

ネットワークノードは、どのノードが「コーディネーター」状態になるかを決定するために、相互に通信を行います。そのためには、ノード間の対称性を破る何らかの方法が必要です。例えば、各ノードが固有かつ比較可能なIDを持っている場合、ノードは自身のIDを比較し、最も高いIDを持つノードをコーディネーターとして決定することができます。[78]

この問題の定義は、トークンが失われたトークンリングネットワークで新しいトークンを作成する方法として定式化したLeLannによるものとされることが多い。 [79]

コーディネータ選出アルゴリズムは、転送バイト数と時間の点で経済性を重視して設計されています。Gallager、Humblet、Spira [80]が一般無向グラフ向けに提案したアルゴリズムは、分散アルゴリズムの設計全般に大きな影響を与え、分散コンピューティングにおける影響力のある論文として ダイクストラ賞を受賞しました。

他にも、無向リング、単向リング、完全グラフ、グリッド、有向オイラーグラフなど、様々な種類のネットワークグラフに対して多くのアルゴリズムが提案されました。グラフ族の問題とコーディネータ選出アルゴリズムの設計を切り離す一般的な手法は、Korach、Kutten、Moranによって提案されました。[81]

分散システムでは、調整を行うためにコーディネータの概念が用いられます。コーディネータ選出問題とは、分散システム内の異なるプロセッサ上のプロセス群の中から、中央コーディネータとして機能するプロセスを選択することです。中央コーディネータ選出アルゴリズムはいくつか存在します。[82]

分散システムの特性

これまでの焦点は、与えられた問題を解決する分散システムの設計に置かれてきました。補完的な研究課題として、与えられた分散システムの特性を研究することが挙げられます。 [83] [84]

停止問題は、集中計算分野における類似の例です。コンピュータプログラムが与えられ、それが停止するか永久に実行されるかを決定するという課題があります。停止問題は一般的な場合には決定不可能であり、当然ながらコンピュータネットワークの挙動を理解することは、1台のコンピュータの挙動を理解することと少なくとも同程度に困難です。[85]

しかし、決定可能な興味深い特殊なケースも数多く存在します。特に、有限状態機械のネットワークの挙動について推論することが可能です。一例として、相互作用する（非同期かつ非決定的な）有限状態機械のネットワークがデッドロックに陥るかどうかを判定することが挙げられます。この問題はPSPACE完全[86]、すなわち決定可能ですが、大規模ネットワークの場合にこの問題を解決する効率的な（集中型、並列型、分散型の）アルゴリズムが存在する可能性は低いと考えられます。

その他のトピック

線形化可能性

参照

注記

  1. ^ ab Tanenbaum, Andrew S.; Steen, Maarten van (2002). 分散システム：原理とパラダイム. Upper Saddle River, NJ: Pearson Prentice Hall. ISBN 0-13-088893-1. 2020年8月12日時点のオリジナルよりアーカイブ。2020年8月28日閲覧。
  2. ^ 「分散プログラム」. Texts in Computer Science . ロンドン: Springer London. 2010. pp.  373– 406. doi :10.1007/978-1-84882-745-5_11. ISBN 978-1-84882-744-8. ISSN  1868-0941。システムは、物理的に分散された複数のコンポーネントで構成され、各コンポーネントはそれぞれ独自のストレージを使用して独立して動作しますが、明示的なメッセージパッシングによって随時通信も行います。このようなシステムは分散システムと呼ばれます。
  3. ^ Dusseau & Dusseau 2016、p.1-2。
  4. ^ フォード、ニール（2020年3月3日）。『ソフトウェアアーキテクチャの基礎：エンジニアリングアプローチ』（第1版）。オライリーメディア。146  ～ 147ページ。ISBN 978-1-4920-4345-4。
  5. ^ モノリスからマイクロサービスへ：モノリスを変革する進化的パターン。オライリーメディア。ISBN 978-1-4920-4781-0。
  6. ^ Knativeでのサーバーレスアプリケーションの構築。O'Reilly Media。ISBN 978-1-0981-4204-9。
  7. ^ 「分散プログラム」. Texts in Computer Science . ロンドン: Springer London. 2010. pp.  373– 406. doi :10.1007/978-1-84882-745-5_11. ISBN 978-1-84882-744-8. ISSN  1868-0941。分散プログラムは、分散システムの抽象的な記述です。分散プログラムは、並行して動作し、明示的なメッセージパッシングによって通信する複数のプロセスで構成されます。各プロセスは、他のプロセスによって変更可能な変数とは互いに独立している変数の集合にアクセスできます。
  8. ^ Andrews (2000). Dolev (2000). Ghosh (2007), p. 10.
  9. ^ Magnoni, L. (2015). 「分散システムのための最新メッセージング (sic)」. Journal of Physics: Conference Series . 608 (1) 012038. Bibcode :2015JPhCS.608a2038M. doi : 10.1088/1742-6596/608/1/012038 . ISSN  1742-6596.
  10. ^ ゴッドフリー（2002年）。
  11. ^ ab Andrews (2000)、p. 291–292. Dolev (2000)、p. 5.
  12. ^ リンチ（1996）、1ページ。
  13. ^ ab Ghosh (2007)、10ページ。
  14. ^ Andrews (2000)、8～9頁、291頁。Dolev (2000)、5頁。Ghosh (2007)、3頁。Lynch (1996)、xix頁、1頁。Peleg (2000)、xv頁。
  15. ^ Andrews (2000)、p. 291。Ghosh (2007)、p. 3。Peleg (2000)、p. 4。
  16. ^ Ghosh (2007)、3～4頁。Peleg (2000)、1頁。
  17. ^ Ghosh (2007)、p.4。Peleg (2000)、p.2。
  18. ^ Ghosh (2007), p. 4, 8. Lynch (1996), p. 2–3. Peleg (2000), p. 4.
  19. ^ リンチ（1996）、p.2。ペレグ（2000）、p.1。
  20. ^ Ghosh (2007)、7ページ。Lynch (1996)、xix、2ページ。Peleg (2000)、4ページ。
  21. ^ ソフトウェアアーキテクチャの基礎：エンジニアリングアプローチ. O'Reilly Media. 2020. ISBN 978-1-4920-4345-4。
  22. ^ abcd Kleppmann, Martin (2017).データ集約型アプリケーションの設計：信頼性、拡張性、保守性に優れたシステムの背後にある重要なアイデア. O'Reilly Media. ISBN 978-1-4493-7332-0。
  23. ^ abcd イベント駆動型マイクロサービスの構築：大規模な組織データの活用. ISBN 978-1-4920-5789-5。
  24. ^ ゴーシュ (2007)、p. 10. ケイダール (2008)。
  25. ^ リンチ（1996）、p. xix、1-2。ペレグ（2000）、p. 1。
  26. ^ ペレグ（2000）、1ページ。
  27. ^ Papadimitriou (1994)、第 15 章。Keidar (2008)。
  28. ^ はじめにの参考文献を参照してください。
  29. ^ Bentaleb, A.; Yifan, L.; Xin, J.; et al. (2016). 「並列および分散アルゴリズム」(PDF) . シンガポール国立大学. 2017年3月26日時点のオリジナルよりアーカイブ(PDF) . 2018年7月20日閲覧。
  30. ^ アンドリュース（2000）、348ページ。
  31. ^ アンドリュース（2000）、32ページ。
  32. ^ Peter (2004)「電子メールの歴史」Wayback Machineで2009年4月15日にアーカイブ。
  33. ^ バンクス、M. (2012). 『ウェブへの道：インターネットとその創始者たちの秘められた歴史』Apress. pp.  44–5 . ISBN 978-1-4302-5074-6. 2023年1月20日時点のオリジナルよりアーカイブ。2018年7月20日閲覧。
  34. ^ Tel, G. (2000). 分散アルゴリズム入門. ケンブリッジ大学出版局. pp.  35– 36. ISBN 978-0-521-79483-1. 2023年1月20日時点のオリジナルよりアーカイブ。2018年7月20日閲覧。
  35. ^ Ohlídal, M.; Jaroš, J.; Schwarz, J.; et al. (2006). 「相互接続ネットワークにおけるOABおよびAAB通信スケジュールの進化的設計」 Rothlauf, F.; Branke, J.; Cagnoni, S. (編).進化的コンピューティングの応用Springer Science & Business Media. pp.  267– 78. ISBN 978-3-540-33237-4。
  36. ^ 「リアルタイムおよび分散コンピューティングシステム」（PDF） . ISSN 2278-0661. 2017年1月10日時点 のオリジナル（PDF）からアーカイブ。 2017年1月9日閲覧。 {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
  37. ^ Vigna P、Casey MJ.暗号通貨の時代：ビットコインとブロックチェーンが世界経済秩序に挑む セント・マーチンズ・プレス 2015年1月27日ISBN 9781250065636
  38. ^ Quang Hieu Vu; Mihai Lupu; Beng Chin Ooi (2010).ピアツーピアコンピューティング：原理と応用. ハイデルベルク: シュプリンガー. p. 16. ISBN 978-3-642-03513-5. OCLC  663093862。
  39. ^ Lind P, Alm M (2006)、「データベース中心の仮想化学システム」、J Chem Inf Model、46 (3): 1034– 9、doi :10.1021/ci050360b、PMID  16711722。
  40. ^ Chiu, G (1990). 「分散コンピューティングシステムにおける最適なデータベース割り当てモデル」.議事録. IEEE INFOCOM'90: IEEEコンピュータ通信学会第9回年次合同会議.
  41. ^ ニューマン、サム (2015-02-20).マイクロサービスの構築. O'Reilly Media. ISBN 978-1-4919-5035-7。
  42. ^ リチャードソン、クリス (2019). 『マイクロサービスパターン：Javaの例付き』 シェルターアイランド、ニューヨーク州: マニング・パブリケーションズ. ISBN 978-1-61729-454-9。
  43. ^ Christudas, Binildas (2019). 『実践的マイクロサービスアーキテクチャパターン：Spring BootとSpring CloudによるイベントベースJavaマイクロサービス』 カリフォルニア州バークレー：Apress LP ISBN 978-1-4842-4501-9。
  44. ^ ニューマン、サム (2015-02-20).マイクロサービスの構築. O'Reilly Media. ISBN 978-1-4919-5035-7。
  45. ^ リチャードソン、クリス (2019). 『マイクロサービスパターン：Javaの例付き』 シェルターアイランド、ニューヨーク州: マニング・パブリケーションズ. ISBN 978-1-61729-454-9。
  46. ^ Christudas, Binildas (2019). 『実践的マイクロサービスアーキテクチャパターン：Spring BootとSpring CloudによるイベントベースJavaマイクロサービス』 カリフォルニア州バークレー：Apress LP ISBN 978-1-4842-4501-9。
  47. ^ ニューマン、サム (2015-02-20).マイクロサービスの構築. O'Reilly Media. ISBN 978-1-4919-5035-7。
  48. ^ リチャードソン、クリス (2019). 『マイクロサービスパターン：Javaの例付き』 シェルターアイランド、ニューヨーク州: マニング・パブリケーションズ. ISBN 978-1-61729-454-9。
  49. ^ Christudas, Binildas (2019). 『実践的マイクロサービスアーキテクチャパターン：Spring BootとSpring CloudによるイベントベースJavaマイクロサービス』 カリフォルニア州バークレー：Apress LP ISBN 978-1-4842-4501-9。
  50. ^ ニューマン、サム (2015-02-20).マイクロサービスの構築. O'Reilly Media. ISBN 978-1-4919-5035-7。
  51. ^ リチャードソン、クリス (2019). 『マイクロサービスパターン：Javaの例付き』 シェルターアイランド、ニューヨーク州: マニング・パブリケーションズ. ISBN 978-1-61729-454-9。
  52. ^ Christudas, Binildas (2019). 『実践的マイクロサービスアーキテクチャパターン：Spring BootとSpring CloudによるイベントベースJavaマイクロサービス』 カリフォルニア州バークレー：Apress LP ISBN 978-1-4842-4501-9。
  53. ^ Elmasri & Navathe (2000)、セクション 24.1.2。
  54. ^ アンドリュース (2000)、p. 10-11。ゴーシュ (2007)、p. 4～6。リンチ (1996)、p. xix、1. Peleg (2000)、p. 15. Elmasri & Navathe (2000)、セクション 24。
  55. ^ Haussmann, J. (2019). 「クラウドコンピューティング環境における不規則構造の問題に対するコスト効率の高い並列処理」. Journal of Cluster Computing . 22 (3): 887– 909. doi :10.1007/s10586-018-2879-3. S2CID  54447518.
  56. ^ リアクティブアプリケーション開発。マニング。2018年。ISBN 978-1-63835-581-6。
  57. ^ Toomarian, NB; Barhen, J.; Gulati, S. (1992). 「リアルタイムロボットアプリケーションのためのニューラルネットワーク」. Fijany, A.; Bejczy, A. (編). 『ロボット工学のための並列計算システム：アルゴリズムとアーキテクチャ』 . World Scientific. p. 214. ISBN 978-981-4506-17-5. 2020年8月1日時点のオリジナルよりアーカイブ。2018年7月20日閲覧。
  58. ^ サベージ、JE (1998). 『計算モデル：コンピューティングの力を探る』 アディソン・ウェスレー. p. 209. ISBN 978-0-201-89539-1。
  59. ^ コーメン、ライザーソン、リベスト (1990)、セクション 30。
  60. ^ Herlihy & Shavit (2008)、第2章～第6章。
  61. ^ リンチ（1996）
  62. ^ Cormen、Leiserson、Rivest (1990)、セクション 28 および 29。
  63. ^ abc TULSIRAMJI GAIKWAD-PATIL ナグプール工科大学 情報技術学科 分散システム入門[1]
  64. ^ Cole & Vishkin (1986). Cormen, Leiserson & Rivest (1990), 第30.5節.
  65. ^ アンドリュース（2000）、p.ix。
  66. ^ Arora & Barak (2009)、セクション 6.7。パパディミトリウ (1994)、セクション 15.3。
  67. ^ パパディミトリウ (1994)、セクション 15.2。
  68. ^ リンチ（1996年）、17–23ページ。
  69. ^ Peleg (2000)、セクション 2.3 および 7。Linial (1992)。ナオールとストックマイヤー (1995)。
  70. ^ Schneider, J.; Wattenhofer, R. (2011). 「分散アルゴリズムの取引ビット数、メッセージ数、および時間計算量」. Peleg, D. (編).分散コンピューティング. Springer Science & Business Media. pp.  51– 65. ISBN 978-3-642-24099-7. 2020年8月1日時点のオリジナルよりアーカイブ。2018年7月20日閲覧。
  71. ^ リンチ（1996）、第5～7節。ゴーシュ（2007）、第13章。
  72. ^ リンチ（1996）、99–102頁。ゴーシュ（2007）、192–193頁。
  73. ^ Dolev (2000). Ghosh (2007), 第17章。
  74. ^ リンチ（1996）、第16節。ペレグ（2000）、第6節。
  75. ^ Lynch（1996）、第18節。Ghosh（2007）、第6.2～6.3節。
  76. ^ Ghosh（2007）、セクション6.4。
  77. ^ Kamburugamuve, Supun; Ekanayake, Saliya (2021).データ集約型アプリケーションの基礎 大規模データ分析の裏側. John Wiley & Sons. ISBN 978-1-119-71301-2。
  78. ^ ab ハロイ、S. (2015). Apache ZooKeeper の必需品。 Packt Publishing Ltd. pp.  100–101 . ISBN 978-1-78439-832-3. 2023年1月20日時点のオリジナルよりアーカイブ。2018年7月20日閲覧。
  79. ^ LeLann, G. (1977). 「分散システム - 形式的アプローチに向けて」.情報処理. 77 : 155·160 – Elsevier経由.
  80. ^ RG Gallager、P.A. Humblet、P.M. Spira (1983年1月). 「最小重みスパニングツリーのための分散アルゴリズム」(PDF) . ACM Transactions on Programming Languages and Systems . 5 (1): 66– 77. doi :10.1145/357195.357200. S2CID 2758285. 2017年9月26日時点のオリジナルより アーカイブ(PDF) 。{{cite journal}}: CS1 maint: 複数の名前: 著者リスト (リンク)
  81. ^ Korach, Ephraim; Kutten, Shay ; Moran, Shlomo (1990). 「効率的な分散型リーダー探索アルゴリズムの設計のためのモジュール式手法」(PDF) . ACM Transactions on Programming Languages and Systems . 12 (1): 84– 101. CiteSeerX 10.1.1.139.7342 . doi :10.1145/77606.77610. S2CID  9175968. 2007年4月18日時点のオリジナルよりアーカイブ(PDF) . 
  82. ^ ハミルトン、ハワード. 「分散アルゴリズム」. 2012年11月24日時点のオリジナルよりアーカイブ。2013年3月3日閲覧。
  83. ^ 「分散システムにおける主要な未解決問題？」cstheory.stackexchange.com . 2023年1月20日時点のオリジナルよりアーカイブ。2018年3月16日閲覧。
  84. ^ 「ビッグデータと分散システムが従来のスケーラビリティ問題を解決する方法」theserverside.com . 2018年3月17日時点のオリジナルよりアーカイブ。 2018年3月16日閲覧。
  85. ^ Svozil, K. (2011). 「物理学における不確定性とランダム性」. Hector, Z. (編). 『計算によるランダム性：いくつかの答えとさらなる疑問』. World Scientific. pp.  112–3 . ISBN 978-981-4462-63-1. 2020年8月1日時点のオリジナルよりアーカイブ。2018年7月20日閲覧。
  86. ^ パパディミトリウ (1994)、セクション 19.3。

参考文献

本
記事
  • コール、リチャード;ヴィシュキン、ウジ(1986)、「決定論的コイン投げと最適並列リストランキングへの応用」、情報制御、70 (1): 32– 53、doi : 10.1016/S0019-9958(86)80023-7。
  • Keidar, Idit (2008)、「分散コンピューティングコラム32 – 年次レビュー」、ACM SIGACT News、39 (4): 53– 54、CiteSeerX  10.1.1.116.1285、doi :10.1145/1466390.1466402、S2CID  7607391、2014年1月16日時点のオリジナルよりアーカイブ、2009年8月20日取得。
  • Linial, Nathan (1992)、「分散グラフアルゴリズムにおける局所性」、SIAM Journal on Computing、21 (1): 193– 201、CiteSeerX  10.1.1.471.6378、doi :10.1137/0221015。
  • Naor, Moni ; Stockmeyer, Larry (1995)、「何が局所的に計算できるか？」(PDF)、SIAM Journal on Computing、24 (6): 1259– 1277、CiteSeerX  10.1.1.29.669、doi :10.1137/S0097539793254571、 2013年1月8日時点のオリジナルよりアーカイブ(PDF)。
ウェブサイト
  • ビル・ゴッドフリー (2002). 「分散コンピューティング入門」. 2021年5月13日時点のオリジナルよりアーカイブ。2021年5月13日閲覧。
  • ピーター、イアン (2004). 「イアン・ピーターのインターネットの歴史」. 2010年1月20日時点のオリジナルよりアーカイブ。2009年8月4日閲覧。

さらに読む

本
  • Attiya、Hagit、Jennifer Welch (2004)、『分散コンピューティング：基礎、シミュレーション、高度なトピック』、Wiley-Interscience ISBN 0-471-45324-2。
  • クリスチャン・カチン。ラシッド・ゲラウィ。 Luís Rodrigues (2011)、信頼性が高く安全な分散プログラミング入門(第 2 版)、Springer、Bibcode :2011itra.book....C、ISBN 978-3-642-15259-7
  • Coulouris, George; et al. (2011),分散システム：概念と設計（第5版）、Addison-Wesley ISBN 0-132-14301-1。
  • Faber, Jim (1998), Java Distributed Computing, O'Reilly, 2010年8月24日アーカイブ, 2010年9月29日取得: Java Distributed Computing by Jim Faber, 1998 2010年8月24日アーカイブ、Wayback Machine
  • Garg, Vijay K. (2002)、『分散コンピューティングの要素』、Wiley-IEEE Press ISBN 0-471-03600-5。
  • テル、ジェラード（1994）、分散アルゴリズム入門、ケンブリッジ大学出版局
  • Chandy, Mani ; et al. (1988), Parallel Program Design , Addison-Wesley ISBN 0201058669
  • Dusseau, Remzi H.; Dusseau, Andrea (2016). オペレーティングシステム：3つの簡単なピース、第48章 分散システム(PDF) . 2021年8月31日時点のオリジナル(PDF)からアーカイブ。 2021年10月8日閲覧。
記事
  • Keidar, Idit; Rajsbaum, Sergio, eds. (2000–2009)、「Distributed computing column」、ACM SIGACT News、2014年1月16日時点のオリジナルよりアーカイブ、2009年8月16日取得。
  • Birrell, AD; Levin, R.; Schroeder, MD; Needham, RM (1982年4月). 「Grapevine: 分散コンピューティングの実践」(PDF) . Communications of the ACM . 25 (4): 260– 274. doi :10.1145/358468.358487. S2CID 16066616. 2016年7月30日時点のオリジナルより アーカイブ(PDF) .
会議論文
  • ロドリゲス, カルロス; ヴィラグラ, マルコス; バラン, ベンジャミン (2007). 「ブール充足可能性のための非同期チームアルゴリズム」. 2007 第2回バイオインスパイアード・モデルズ・オブ・ネットワーク、情報、コンピューティングシステム. pp.  66– 69. doi :10.1109/BIMNICS.2007.4610083. S2CID  15185219.
Wikiquote には分散コンピューティングに関する引用があります。
  • ウィキメディア・コモンズの分散コンピューティング関連メディア