本書の概要

CHAPTER 10 Deadlock detection in distributed systems

から

10.5 Knapp’s classification of distributed deadlock detection algorithms

までを読みました

広く浅く学べる大学院の教科書的な本らしいです。
これを手引きに論文を引いて実装するのが良い。
余談ですが、読書会の参加人数は対数線形で減っていくらしい

感想

「待ちグラフ」って名前はDBスペシャリスト試験などで何度も出てくるから知っていますが、具体的にどのようなものか知りませんでした。DBの実装経験があるような方々もおられたため、実際に実装するならこういうアルゴリズムでやる、など会話をしているうちに、机上の理論だったものが実際のイメージに落ちていく感覚がとても面白かったです。

研究職やミドルウェアを作っておられるような本物の技術者のような方が中心なので、レベルの差を感じるものがありました。強い

勉強会ノート

雑でまとめきれていませんが。一応書いたのでブログに乗せます。

分散システムではデットロックの検出は基本的にできない、という結論になりそう？

There is only one copy of each resource.

それぞれのコピーは一個しかない、的な慣用句

Wait-for graph

待ちグラフの実装は面倒
グラフ処理は行列処理でやる。
待ちグラフは効率が悪い
deadlockの対処
- prevention:非効率
- avoidance:(分散システムでは)実用的ではない
- detection:これが良い(本書ではここを掘り下げる)

This is the main reason why many deadlock detection algorithms reported in the literature are incorrect.

とあるが、分散システム界隈では論文記載のデッドロック検出アルゴリズムが不完全というのは一般的な認識なのか？
論文が不完全というのは常識ではない。
想定が甘い、というのはある。
10.4.2のANDモデルの例が適切ではない？
- デッドロックを起こしているものがAndモデルの例として適切でない(複数のリソースを要求しておらずどのプロセスも一つの要求しか出していない)
Orモデルの場合のデッドロックの検出条件
- 1.Each of the processes in the set S is blocked.
- 2.The dependent set for each process in S is a subset of S.
- 3.No grant message is in transit between any two processes in set S.
knotの定義がわからない？
- 分散システムでも一般的な概念ではない
- サイクルとの違いがわからない
  - サイクルよりも強い
    - サイクルとの違いは

In the OR model, the presence of a knot indicates a deadlock [19]. In a WFG, a vertex v is in a knot if for all u :: u is reachable from v: v is reachable from u. No paths originating from a knot shall have dead ends.