- Byzantine Fault Tolerantなトランザクショナル[[KVS]
- Correctnessとして、Byzantine Isolationを保証
- 具体的な保証レベルとしてByzantine Serializabilityを保証
- Progressとして、Byzantine Independenceを保証
- Leader-followerモデルのコンセンサスアルゴリズムでは、リーダーが不正を働いたら簡単に覆るので、Basilではリーダーベースモデルを採用していない
- Client-drivenなアーキテクチャ
Concurrency Control
実行の流れ
Withdraw(Bob, x)を考える
Begin(T, TS): タイムスタンプをつける- システムの仮定として、時刻がゆるく同期されている、というのがある
balance = Read(bob): レプリカからOptimisticに値を読み取る- read(key, TS), reply(key, version, value)
- f+1個のレプリカから値を読み取り、最もバージョン番号が高いものを選択する
- Write(Bob, bal - x)
- Commit(T)
Commit Protocol
- 2PCベース
- 異なる順序で競合するトランザクションのコミットを受け取りうるし、レプリカはウソを付くかもしれない
- Replicas perform CC-Check + Quorum validation = Byzantine Serializability
Fallback protocol
- Byzantine Independenceを保証するFallback protocol
参考
メモ
- Byzantineなクライアントが、意図的にAbortして、他のトランザクションもそれに引きづられてどんどんAbortせざるを得ない…みたいなカスケード障害は、どのように防がれている?