PSPACE

P  ⊂ NP ⊂ PSPACE

Gadget

time t:
- 最初のstepを1,次に起こったstepを2,という風に順序付けていく全順序
- tはHistoryの開始~終了までのうちのどこかの時点を表す
  - もちろんassignするのはlegal versionである。
$P_t(s,V)$ :tが入ったポリグラフのこと
complition of :
- time tまでのfull scheduleが(s,V)と一致している
- tの時点でactiveなtransactionのなんらかの順序が決まる
legal version?:要復習

のArch(A,B)を作るルール
- (1)AがwriteしたxをBが持つ
- (2)Aがread,writeしたxをBがwriteする。Bがwriteしたxはtの時点で唯一の"available"である(?)
- (3)Aがxの初期値を読み、Bがxを上書きした場合
(2)と(3)の違いは？
- availableの意味は？
  - $\lambda$ にマップされない？
- 謎
?マーク付き無方向エッジ
- 同じentityをwriteしてconflictしているが、どちらが先かわからない状態
  - (A,B) or (B,A)
例:Figure 3.2のSchedulle sのがFigure 3.3になる
- 補足 $V_s$ =standard version functionを採用したVのこと
- Dがabortされた場合
  - (A,B)のarchが追加される
  - A,Bはxのwriteでconflictしていたが、が読むxはDが上書きしていたため順序を決める必要がなかった
    - Dがなくなったことによりこの順序を決める必要がある
  - (A,B)が追加された時により、(G,B,F)のチョイスは(G,B)が選ばれる
    - 消去法。(A,B,F)の循環を避けるため
  - (G,B)が選択されたことにより、?マーク付き無方向エッジは(E,C)が選ばれる
    - これも消去法で　(G,B)が選ばれたことによる(G,B,C,E)の循環を避けるため