Database Concurrency Control Papadimitriou 読会29回ノート:reliabilityとQSATの帰着

主にreliability保証がPSPACE完全であることを示すためにQSATをreliability gameに帰着させる手順の解説を読んだ。QSATの用語とreliability gameの用語とgadgetの用語が混ざっている上に図がほとんどないのでかなり分かりにくい。加えて私はgadgetの理解がいまいちなので読んでて非常に混乱した。

• p80 The Reductionからp83　Finally let us spcecify(4)~の段落最後まで読んだ。次回はp83 We will describe~から

connpass.com

The Reduction

• F=true ↔︎ (s(F),V's(F)) is reliable

  • 上記を満たす変換(reduction)を考える

• 各EXISTENSIAL(偶数変数)、UNIVERSAL(奇数変数)のごとにトランザクションを作成する

  • UNIVERSAL(EVIL player)は奇数iのどちらかを一つのみをabortできるようにDを作る
  • EXISTENSIAL(Good palyer)は偶数iのは他のトランザクションがwriteしないentityをread-writeしている
    • このwriteは(もちろん他のtransactionがwriteしないので)最終値を決定している。
  • EVILが奇数iのトランザクションをabortした時、Goodはのread writeの順序を変更することができる
    • xi=trueのときの順序に対応し、xi=falseの場合逆順になる。

Reductionの手順

• Reductionはscheduleを構成するパートとpolygraphを構成するパートに分かれる。手順は以下になる

  • (1).(EVIL側に)奇数iのDi,D'iどちらか一方をabortするように強制する
  • (2).QSATの各clause中のすべてのlilteralがfalseのとき、cycleが発生するように構成する
  • (3).clause中に出現した各xiに対して、Di,D'iに”Fan-out” gadgetsを使って真理値を配る
  • (4)."Precedence" gadgetを使って正しい順序を強制する

• 上記のパートについて詳しく説明する

• 前提としてarc=directed edgeであることに注意

(1)

• 奇数番目iに対応したトランザクションT1,T3,...Tn-1を用意する

• 追加でTn+1のトランザクションを用意する

• T1からTn+1への潜在的なpathを用意する
  • T1がy1,y'1をwriteする。
  • T3がy1,y'1,y3,y'3をwriteする　
    • 同様に後続のtransactionでyi-1, y'i-1, yi, y'iのentityにwriteし、隣り合った順序のトランザクションをwrite-write conflictで接続する
      • この接続で作ったarcはpolygraphに出現しない。
        • yi,y'iの最終値はDi,D'iで決定されるため
          • Di,D'iどちらかをabortしないとT1 to Tn+1のpathが構成されない(EVIL側が必ず負ける)*1
            • 故にEVIL playerはDi,D'iどちらかをabortする必要がある

(2)

• 各clauseはTn+1からT1への潜在的なback pathを持つ
  • 潜在的なback pathは4つのarcと3つのundirected edgeから構成される
    • 3つのundirected edgeはclause中のliteralに対応する

一応(4)まで読んだが仕事が忙しいのでとりあえずここまででで一旦投稿。

英語

• occurrence:出来事
• Precedence:優先

Theory of Database Concurrency Control

*1:ここからよくわからない？