1970年代後半に生まれた:
- 研究者/実践者が物理分散システムに固有の性質に取り組み始めた
- ネットワーキング/OS/平行計算の調査領域から分離
分散コンピューティング(or 分散計算):
- 分散エンティティ群に纏わる問題を解く際に必要となる
- 分散エンティティ群: processors, nodes, processes, actors, agents, sensors, peers, etc
- 各エンティティは部分的な知識しか保有しない
- 分散アルゴリズムをデザインする際の困難の主要な原因
- 共通のゴールを達成するためにはエンティティ群は協調する必要がある
- ただし、他のエンティティの現在の状態を即座に知ることは不可能
- (メッセージパッシングを通して)過去のローカル状態のみを知ることが可能
- 平行コンピューティングとの対比:
- 平行: 効率とオンタイム計算が特徴
- 分散: 不確かさが特徴
- 非同期性、制御フローの多様性、共有メモリとグローバル時間の不在、失敗、ダイナミック性、流動性、etc、に由来
分散アルゴリズムの記述行数は短い(a few lines)ことが多い:
- ただしその振る舞いを理解したり、特性の説明・証明を行うのは困難に成り得る
- 分散計算は基礎的なだけではなく、チャレンジングなトピック
- 簡潔さ・優雅さ・美しさ、は第一級市民
分散計算分野の基礎的な書籍が少ない:
- 逐次計算用の基礎的なアルゴリズム・データ構造を扱った本は沢山ある
- 分散計算向けのほとんどの本はよりアドバンスドなトピックに焦点を当てている
- 分散計算に本質的に付随する不確実さをどう扱うかが主関心
- 学部生というよりは、院生向け
この本の目的:
- 以下を包括的な方法で提供する:
- 基礎的な観念やコンセプト
- 分散計算のアルゴリズム
- 分散エンティティ同士はメッセージを(ネットワークを通して)送受信すること協調する
- 主要な難しさの源泉:
- エンティティ群の物理的な分散
- 環境の非同期性
分散系のトピックやコンセプトに馴染のない人向けに書かれている。具体的には主に、
- 分散計算の原理と基礎に興味がある情報系の(senior-levelな)学部生ないし院生
- 分散計算に纏わる最先端のコンセプト、基礎原理、メカニズム、技術を知りたいと思っている実践者やエンジニア
必要条件:
- 学部レベルのアルゴリズムへの理解
- オペレーティングシステムに関する基礎的な知識
扱う内容:
- メッセージパッシングプログラミングのアルゴリズム、基本原理、基礎
- 世界は分散で、分散アプリケーションも増えてきているから、分散計算の理解の重要性は増してきている、的な話
本書は六つの部分から構成されている:
六章で構成:
- 分散アルゴリズムの性質を感じて貰うのが目的
- i.e. 逐次や並列アルゴリズムとは何が異なるか
- 主に分散グラフアルゴリズムを扱う
- グラフの各ノードがプロセスに対応
- プロセスはグラフの全体象に依存する結果を計算しなければならない
- 最初は、基礎的な分散アルゴリズムを取り上げる:
- network traversals, shortest-path algorithms, vertex coloring, knot detection, etc
- その後に、分散グラフアルゴリズム用の汎用的なフレームワークが導入される
- 以下のトピックにそれぞれ一章が割かれている:
- リングネットワーク上でのリーダ選出アルゴリズム
- モバイルオブジェクト群によるネットワークのナビゲーション
四章で構成:
- 分散実行の性質を扱っており、ある意味でこの本の核心部分
- 以下を説明している:
- 分散実行とは何か
- 一貫したグローバル状態の基礎概念
- 以下を知ることの不可能性 (計算を止めることなくしては達成できない)
- 計算された一貫したグローバル状態が、その計算を通して渡されたものかどうか
- 次に、分散計算での重要な問題である論理時間の概念に取り組む:
- スカラ(線形)時間, ベクトル時間, マトリックス時間
- それぞれの時間の解析と使用例が与えられる
- 一つ章は非同期分散チェックポインティングに捧げられている
- 一貫グローバル状態の概念の拡張も行われる
- 最後の章は、非同期システムの上で同期システムをシミューレートする方法を示す
二章で構成:
- 分散相互排他と分散リソース割当を扱う:
- いくつかの種類の、許可に基づく相互排他アルゴリズム
- 適応アルゴリズムの概念
- 複数エンティティによるクリティカルセクションの概念
- 単一ないし複数インスタンスのリソース
- デッドロック防止テクニック
二章で構成:
- コミュニケーション操作の定義及び実装を行う:
- 単純なメッセージ送受信よりも抽象度が高い
- メッセージ配送に順番制約を課する
- 各章で扱う話題:
- 因果(causal)メッセージ配送と全順序ブロードキャスト
- 同期コミュニケーション
二章で構成:
- 安定特性(stable property)の検出を扱う:
- 安定特性: 一度trueになったら、その後はtrueであり続ける
- 以下で使われる:
- 分散計算の終端の検出
- 分散デッドロックの検出
- この部は、第二部(グローバル状態の概念を扱っている)と強く関係している
二章で構成:
- 分散共有メモリの概念を扱う
- エンティティ(プロセス)に、メッセージよりも適切な抽象レベルで協調するためのオブジェクト群を提供するのが目的
- それらのオブジェクト群に関わる二つの一貫性状態が定義・調査される:
- アトミック性 (a.k.a. 線形化可能性)
- 逐次一貫性
この本の目的を理解するにはafterwordの"The Aim of This Book"も参考になる。
省略
省略 (必要に応じて見返せば良さそう)
逐次計算の実践は理論から恩恵を受けている:
- formal languages and automata theory
- 皆が、何が計算可能か(computability)と何が効率的に計算可能か(complexity)を知っている
- これらは逐次計算の基礎となり、科学となっている
- 理論的な成果やアルゴリズムは、いろいろな本で説明されている
分散計算は？
- Lamportの"Time, clocks, and the ordering of events in a distributed system"(1978)を起点に計算科学の一分野となった
- 独自の概念、方法論、アプリケーション、を備えている
- 世界は分散しており、現在の主要な部分のアプリケーションは分散している
- これはメッセージパッシングアルゴリズムが、いずれの計算科学や計算エンジニアリングカリキュラムの重要な部分となっていることを意味する
良書と良いカリキュラムのおかげで、学生は逐次計算の理論と実践に関して良いバックグランドを保持している:
- この本の目的は、分散計算問題に対して、同様のバックグラウンドを提供すること
- 技術は毎日の生活を容易にする
- 科学はそれを超越することを許し、私達が操縦しているオブジェクトの深い性質を捉える
- この目的のために、それは正しいコンセプトとともに私達が何しているかをマスターし、理解する手段を提供する
- この本の野望である、failure-free非同期分散計算を考えることは、この方向に進む一つのステップである
省略 (単なるキーワードの列挙)
省略 (大学の授業で使う場合の構成の例)
この本の主題は、failure-freeな非同期分散アプリケーション(およびシステム)用のアルゴリズム・基礎概念・コンセプト:
- これらをマスターした後は、failure-proneな分散システムのより特定のトピックに焦点を当てることが可能となる
- failure-proneシステムの文脈では、非同期性と失敗が組み合わさった影響により、アルゴリズムは不確かさに対処する必要がある
- 興味のある読者は次節を参照
この本は、以下の四冊からなるシリーズの中の一つ:
- 本書:
- failure-free非同期システム用の初等の分散計算を扱う
- Concurrent Programming: Algorithms, Principles, and Foundations:
- 非同期共有メモリシステム用のアルゴリズム
- プロセスクラッシュ(crash-failure)に対処可能な信頼並列オブジェクトにフォーカスが当てられている
- ! ただの並列アルゴリズム本かと思っていたけど、意外と面白そう？
- Communication and Agreement Abstractions for Fault-Tolerant Distributed Systems:
- 非同期メッセージパッシングシステム
- プロセスはcrash-failureするかも
- 耐障害性のある非同期分散システム用の通信および合意抽象が提示される
- 失敗検出器は、純粋非同期システムで遭遇する不可避の結果を迂回するために使われる
- 非同期メッセージパッシングシステム
- Fault-Tolerant Agreement in Synchronous Message-Passing Systems:
- 同期メッセージパッシングシステム
- プロセスは"prone to crash-faiures", "omission failures", "Byzantine failures"
- 以下の分散合意問題に焦点を当てている:
- 合意、インタラクティブ一貫性、ノンブロッキングアトミックコミット
- 同期メッセージパッシングシステム