Yabu.log

ITなどの雑記

分散処理本第38回に参加

Distributed Computing: Principles, Algorithms, and Systemsを読む勉強会です。やはり難しいので少し予習していきました。アルゴリズムの分類までは一応軽く読んで概要をつかんでから臨みました

予習をしてブログの下書きを作っておくと、感想のポストがサクッとかけて良いですね。

Distributed Computing: Principles, Algorithms, and Systems

Distributed Computing: Principles, Algorithms, and Systems

分散システムに置けるデッドロックの検出アルゴリズムの分類

  • path-pushing
  • edge-chasing
  • diffusion computation
  • global state detection.

出典:E. Knapp, Deadlock detection in distributed databases, ACM Computing Surveys, 19(4), 1987, 303–328.

※詳しい方が概要を知っているがその分類名を知らない、ということが発生していたので、一般的な分類ではないのかもしれない。

path-pushing

各サイトがWFGを送り合いグローバルなWFGを構築する。 送信しながらどんどんWFGを更新してデッドロックの発生、検知を明らかにして行く

edge-chasing

グラフのエッジに剃ってprobesと呼ばれる特殊なメッセージを送信して行く。 以前送信したprobeと同じものを送信した場合、それでcycleを検出できる

diffusion computation

deadlockが発生していれば帰ってくるようなエコーメッセージを送る。

よく解らん?という話になった

参考にしてある論文は以下のもの

    1. Chandy, J. Misra, and L. M. Haas, Distributed deadlock detection, ACM Transactions on Computer Systems, 1(2), 1983, 144–156.
  1. Herman and K. M. Chandy, A Distributed Procedure to Detect AND/OR Deadlock, Technical Report TR LCS-8301, Department of Computer Sciences, University of Texas, Austin, TX, 1983.

本書記載のアルゴリズム例は2つあり、

  • Chandy–Misra–Haas algorithm for one OR model
  • Chandy–Herman algorithm

前者はWikipediaの記事があった

https://en.wikipedia.org/wiki/Chandy-Misra-Haas_algorithm_resource_model

CMHアルゴリズムとしても有名らしい

global state detection.

分散システムの各スナップショットからデッドロック有無を確認する。しかし以下の条件が必要である

  • (i) a consistent snapshot of a distributed system can be obtained without freezing the underlying computation.

  • (ii) a consistent snapshot may not represent the system state at any moment in time, but if a stable property holds in the system before the snapshot collection is initiated, this property will still hold in the snapshot.

10.6  Mitchell and Merritt’s algorithm for the single-resource model

アルゴリズムとしてはpublic/privateなlabelを使う 文章化するのがちょっと難しいが一言で表すなら

  • 待ち状態に対して2種類(private/public)のラベル作成し値zを与える
    • 下の例はu->v間の待ちを表しているこのzはu+vより大きな値かつユニークでなければならない
    • この操作を待ちの連鎖が終わるところまで続けて行く

f:id:yuyubu:20180918234652j:plain

2週することで図のDetectの状態が発生が把握できる(1週しただけだとDeadlockかどうかわからない)

p360の図は誤植

  • Figure 10.2 The four possible state transitions [22]

という図があるが元ネタが「E. Knapp, Deadlock detection in distributed databases, ACM Computing Surveys, 19(4), 1987, 303–328.」という論文の図であり、引用するときに一部記号が間違っている。

また10.6は本書中の記載のみだと理解が辛く、引用元の論文をよく読み込まないと何を行っているかわからない。

余談:ACM Degital Libaryは高い

500ドルくらいするらしい。。。

次回は「10.7  Chandy–Misra–Haas algorithm for the AND model」から!