分散処理本第38回に参加
Distributed Computing: Principles, Algorithms, and Systemsを読む勉強会です。やはり難しいので少し予習していきました。アルゴリズムの分類までは一応軽く読んで概要をつかんでから臨みました
- 分散システムに置けるデッドロックの検出アルゴリズムの分類
- path-pushing
- edge-chasing
- diffusion computation
- global state detection.
- 10.6 Mitchell and Merritt’s algorithm for the single-resource model
- 余談:ACM Degital Libaryは高い
予習をしてブログの下書きを作っておくと、感想のポストがサクッとかけて良いですね。
Distributed Computing: Principles, Algorithms, and Systems
- 作者: Ajay D. Kshemkalyani,Mukesh Singhal
- 出版社/メーカー: Cambridge University Press
- 発売日: 2011/03/03
- メディア: ペーパーバック
- この商品を含むブログを見る
分散システムに置けるデッドロックの検出アルゴリズムの分類
- 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が発生していれば帰ってくるようなエコーメッセージを送る。
よく解らん?という話になった
参考にしてある論文は以下のもの
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
- WFGの逆向きにprobを飛ばす
- edge-chasingアルゴリズムのうちの一つ
アルゴリズムとしてはpublic/privateなlabelを使う 文章化するのがちょっと難しいが一言で表すなら
- 待ち状態に対して2種類(private/public)のラベル作成し値zを与える
- 下の例はu->v間の待ちを表しているこのzはu+vより大きな値かつユニークでなければならない
- この操作を待ちの連鎖が終わるところまで続けて行く
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」から!