読者です 読者をやめる 読者になる 読者になる

mrasu’s blog

読んだ物の内容など

Distributed Computing: Principles, Algorithms, and Systems (2章)

「Distributed Computing: Principles, Algorithms, and Systems」の2章
メッセージパッシングやイベント、現在状態の見方など分散プログラムが通常のプログラムと違う部分を紹介しています。

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems


Chapter2. A model of distributed computations

2.1 A distributed program

分散プログラムはn個の非同期プロセスでできている。
実行やプロセス間通信は非同期で、遅延は有限だが予測できない。
グローバルな状態はプロセスと、プロセス同士の通信(チャネル)の状態をもって表す。

  • プロセスの状態: プロセスが動くローカルのメモリや処理内容
  • チャネルの状態: チャネルが実行しているメッセージの集合

2.2 A model of distributed executions

プロセスの行うイベントは3種類

  1. 内部イベント
    プロセス内で行われる。他プロセスには影響を与えない
  2. 送信イベント
    メッセージを送信する。送信するときと、送信が完了したときに状態が変化する
  3. 受信イベント
    メッセージを受信する。受信するときと、受信が完了したときに状態が変化する

プロセスi上のイベントxがプロセスj上のイベントyに依存しているというときは、

  1. iとjが同じプロセスで、xの後にyが起きる
  2. xからyへのメッセージ送信
  3. 別のイベントzを通して、x→z→yへの依存関係がある

のどれか。
また、依存関係がない場合でも推移律は成立しない。

二つのイベントが発生の有無によって影響しないとき、「論理的」並列だといい、同時に実行されることを「物理的」並列だという。
論理的並列性があれば、同時に実行可能であり、同時でなくともよい

2.3 Models of communication networks

通信には、

  1. 因果順序
    因果関係による順序。 2つのメッセージに因果順序がある場合、2つのメッセージの送信順と、受信順は一致する
  2. FIFO
    送受信の順番で保存される
  3. non-FIFO
    順序は保存されないので、ランダム

2.4 Global state of a distributed system

グローバルの状態は各プロセスの状態と通信の状態に左右する
プロセスiがメッセージxを送信していない時に、プロセスjがメッセージxを受信しておらず、通信上にもメッセージxが存在しないとき、グローバルの状態がconsistentだという。
また、通信中のメッセージがない時をtransitlessという。
consistentかつtransitlessであるとき、strongly consistentという。

2.5 Cuts of a distributed computation

各プロセスのそれぞれの時点をもって、過去と未来に分割(cut)すると、
過去の全ての受信が過去に送信されている場合、consistent cutといい、
同時刻で区切っているわけではないので、過去に受信しているのに未来に送信するものが存在し得、そういうものはinconsistent

2.6 Past and future cones of an event

あるイベントeに対して

  1. 因果関係があり、事前に実行しなければならないもの
  2. 因果関係があり、事後に実行しなければならないもの
  3. 上のどちらでもなく、並列で実行できるもの

と分類できる。

2.7 Models of process communications

コミュニケーションの方法には、同期と非同期があるがどちらかが優れているわけではない

  1. 非同期は高い並列性を実現するが、実装やデザイン、検証が難しく、状態を保存するコミュニケーションに関するメモリも多く必要
  2. 同期は簡単に扱えるし、実装も楽