この本は、コンピュータサイエンスおよびソフトウェアエンジニアリングに関連する専門分野の学部および大学院生向けの分散アルゴリズムに関するコース向けに設計されています。 また、これらの分野の研究者による参照としても使用できます。 この本は、分散コンピューティングの分野で得られた基本的なアルゴリズムと結果に焦点を当てています。 ここで検討されているアルゴリズムは主に「古典的な」ものであり、主に分散システムのアルゴリズム設計の観点から有益であるか、分散および並列プログラミングの重要な問題に光を当てるために選択されました。
本は2つの部分で構成されています。 最初の部分は、メッセージの送信によるプロセスの相互作用に専念します。 これは、もともとGerard Telの「分散アルゴリズムの紹介」という教科書に基づいて、Vrije University（Amsterdam）で教えられたコースに基づいて形成されました。 2番目の部分は、共有メモリアーキテクチャ専用です。
はじめに
アルゴリズムは、特定の問題をコンピューターで解決することを目的とした段階的な手順です。 資格のあるプログラマになるには、アルゴリズムを十分に理解している必要があります。 情報学の分野のすべての教育プログラムは、アルゴリズム化の基礎に関する1つまたは複数のコースを提供しています。 通常、彼らはグラフの検索とソート、パターン認識、最短経路の発見のためのアルゴリズムを検討します。 彼らは、生徒にコンピュータープログラムでそのようなサブタスクを特定し、それらを効果的に解決することを教えます。 さらに、学生はアルゴリズム的に考え、アルゴリズムの正確さを証明し、単純な複雑性分析を行うことを学びます。
分散コンピューティングは、ユニプロセッサのコンピューティングよりもはるかに複雑であり、分散システムのノードでのタスクの一部の実行が時間内にインターリーブされるため、ユニプロセッサとは非常に異なります。 2つのノードが特定のアクションを同時に実行すると、どちらのノードが時間的に早く実行されるかを予測することはできません。 これは、たとえば、いわゆるレーシング効果につながります。2つのメッセージがネットワーク上の同じノードに到着するとき、ノードの動作はどちらのメッセージが先に到着するかに依存する場合があります。 したがって、分散システムは本質的に非決定的です。同じ初期状態から同じ構成でシステムを2回起動すると、結果が異なる可能性があります。 さらに、ノードの数が増えると、到達可能な状態の数は指数関数的に増加する傾向があります。
分散コンピューティングとユニプロセッサコンピューティングのもう1つの重要な違いは、一般的な場合の分散システムのノードには、システムのグローバル状態に関する関連情報がないことです。 彼らは自身のローカル状態を知っていますが、送信中のその他のノードやメッセージのローカル状態を常に知っているわけではありません。 たとえば、実行がいつ完了するかを判断するのは問題になります。 システム内のすべてのノードが作業を完了したことを確認する必要がありますが、この場合でも、メッセージがまだ送信されていることが判明する可能性があり、これにより受信ノードがアクティブになります。
この本は、計算が完了したときやノードがシステムのグローバルな状態の共同図を構築したときを決定するなど、分散システムのこのような重要な問題を解決する幅広い基本アルゴリズムを提供します。 その主な目標は、分散コンピューティングの分野における基本的な問題を認識して解決できるように、学生のアルゴリズムの考え方を形成することです。 彼らは鳥瞰図からこれらの問題の包括的な概要に加えて、「指で」正確さの証拠と複雑さを評価するための近似方法に招待されます。
分散コンピューティングの2つの主な通信パラダイムは、ノードがチャネルを介して互いにメッセージを送信するメッセージングと、異なる実行可能スレッドがメモリの共通領域を読み書きできる共有メモリです。 この本は、これら2つのコミュニケーションパラダイム専用の2つの部分に分かれています。 導入部の残りの部分では、両方のアプローチに適用可能な予備情報を提供します。
多くの
通常どおり、S1∪S2、S1 \ S2、およびS1⊆S2は、集合の和集合、差、包含を示します。 s∈Sは、sが集合Sの要素であることを意味します。自然数と実数の集合はそれぞれandで示されます。 ブール（ブール）変数の値はtrue（true）およびfalse（false）です。 セットは{... | ...}の形式で記述でき、その要素は垂直バーの左側に示され、満たすべき条件は右側に設定されます。 たとえば、{n∈| n> 5}は5より大きい自然数のセットを表します。空のセットは記号Øで示されます。 有限集合Sの場合、その中の要素の数は| S |で示されます。
複雑さの尺度
複雑さの尺度は、入力データのサイズに対してリソース（メッセージ、時間、メモリ）の消費がどのように増加するかを示します。 たとえば、最悪の場合、アルゴリズムにO（n2）メッセージの複雑度がある場合、サイズnの入力データに対して、最悪の場合のアルゴリズムでは、n2メッセージのプラスまたはマイナスのオーダーの送信が必要です。
メッセージングパラダイムに関するパートIは、主にメッセージの複雑さを扱います。 ビットの複雑さは、メッセージが非常に長くなる可能性がある場合にのみ興味深いものです。 時間の複雑さを分析するとき、イベントの処理には時間が必要でなく、メッセージの受信には送信後最大で1単位の時間がかかると想定しています。 異なる起動は、異なるリソース消費につながる可能性があります。 最悪の場合の複雑さと平均的な複雑さを考慮し、後者の場合、すべての開始点にわたって特定の確率分布を与えます。
順序の関係
セットS の（厳密な）順序の関係は、その要素の非再帰的、非対称、および推移的なバイナリ関係です。 これは、a、b、c∈S、a <a; a <bの場合、b <a; a <bおよびb <cの場合、a <c。 異なるaについて、b∈Sに対してa <bまたはb <aの場合、順序は厳密と呼ばれます。 それ以外の場合、順序は部分的と呼ばれます。 2つのセットS1とS2がそれぞれ<1と<2の順序の関係で与えられるとします。 次に、辞書編集順序関係<S1×S2からのペアでは、a1 <1 b1またはa1 = b1およびa2 <2 b2の場合、（a1、a2）<（b1、b2）として定義されます。 <1および<2が厳密な順序関係である場合、対応する辞書式順序関係>は厳密な順序関係になります。
モジュラー演算
正の整数nを法とする整数環は、要素{0 ... n-1}で表されます。 すべての整数kには、nによる除算の代表的な剰余があり、k mod nで示されます。 これは、nに達すると、巡回リターンが発生することを意味します。nmod nは0、（n + 1）mod nは1などです。加算と減算はモジュラー演算に簡単な方法で転送されます。 n）=（j + k）mod nおよび（j mod n）・（k mod n）=（j・k）mod n。
演習
»本の詳細については、出版社のウェブサイトをご覧ください
» コンテンツ
» 抜粋
アルゴリズムのクーポンの25％割引- アルゴリズム
残念ながら、本は紙の形でのみ利用可能です。