Distributed Algorithms for Message-Passing System: 第十二章

damps-12.md

第四部 ハイレベル通信抽象

第四部の内容:

• メッセージの非同期送受信に基づく分散システムに、ハイレベルな通信抽象を付与する
• 12章:
  • メッセージ配送順序が特定の性質を満たすようにするための抽象群を扱う
  • 因果メッセージ配送、が一番重要
• 13章:
  • ランデブー通信抽象、および、論理的に即時な通信、を扱う
  • 同期通信、とも呼ばれる
• これらの通信抽象の利点:
  • システムの非同期性を削減し、分散アプリケーションのデザインを容易にする

第十二章 メッセージ配送時の順序制約

ハイレベル通信抽象は、メッセージ配信順序に特定の性質を保証するための通信操作を提供する。

配送順序に関連する主要な性質:

• FIFO　（本章の対象外)
• 因果メッセージ配送:
  • P2P
  • ブロードキャスト
• 全順序ブロードキャスト

本章では上述の（システム単位の)性質を扱った後に、チャンネル単位で個別に適用可能な四つの順序性質を取り上げる。

12.1 因果メッセージ配送抽象

12.1.1 因果メッセージ配送の定義

問題

定義

幾何学的な注記

12.1.2 因果メッセージ配送の因果に基づく特徴

12.1.3 他のメッセージ配送制約を考慮した因果順序

12.2 P2P因果メッセージ配送のための基本的なアルゴリズム

12.2.1 簡単なアルゴリズム

基礎原理

配送条件

アルゴリズム

注記

12.2.2 アルゴリズムの証明

補助定理8

補助定理9

補助定理10

定理17

12.2.3 メッセージに付与される制御情報のサイズ削減

基礎原理

最初の解法

より良い解法: データ構造

より良い解法: アルゴリズム

適用的な解法

12.3 因果ブロードキャスト

12.3.1 定義と簡単なアルゴリズム

定義

簡単な因果ブロードキャストアルゴリズム

broadcast[i]ベクタに関する注記

例

12.3.2 因果バリアの概念

メッセージ因果グラフ

因果バリア及びローカルデータ構造

アルゴリズム

12.3.3 有限のライフタイムを有するメッセージによる因果ブロードキャスト

グローバルクロックを持つ非同期システム

ライフタイムが有限なメッセージ

△-因果ブロードキャスト

メッセージ配送条件

アルゴリズム

12.4 全順序配送抽象

12.4.1 強い全順序、対、弱い全順序

強い全順序ブロードキャスト抽象

弱い全順序ブロードキャスト抽象

因果順序、対、全順序

12.4.2 調停プロセス、あるいは、循環トークン、に基づくアルゴリズム

調停プロセスを用いた場合

調停プロセスをトークンで置き換える

相互排他、対、全順序

12.4.3 問い合わせベースのアルゴリズム

構造分解: クライアント、サーバ、ステートマシン

基礎原理

通信グラフ

クライアントプロセスのローカル変数

サーバプロセスのローカル変数

配送条件

全順序ブロードキャストアルゴリズム

12.4.4 同期システムのためのアルゴリズム

同期システム

アルゴリズム

同期・非同期システムにおける全順序

12.5 単一のチャンネルの場合

12.5.1 チャンネルにおける四つの順序性質

定義

12.5.2 上記の性質を備えるための汎用的なアルゴリズム

簡単なアルゴリズム

本物のアルゴリズム

配送条件

12.6 要約

12.7 解題

省略

12.8 演習問題

省略