# 朝輪メモ: Regular Sequential Serializability and Regular Sequential Consistency (SOSP '21)

* Paper: [doi:10.1145/3477132.3483566](https://doi.org/10.1145/3477132.3483566)
* Extended: [doi:10.48550/arXiv.2109.08930](https://doi.org/10.48550/arXiv.2109.08930)
* Presentation: [youtu.be/GauK7QhaAEQ](https://youtu.be/GauK7QhaAEQ)

## 進め方

1. (sync) 進め方の説明: 2 min
2. (sync) 概要を読んで理解する: 3 min
3. (async) 各自で気になる節を読みながら要点や疑問をメモ: 15 min
4. (sync) Introduction を読みながら議論: 10 min

## 進め方の反省

* 4\. の議論フェーズでは内容をざっくりおさらいする程度にして，すぐに質問がないかを聞いた方がいい．

## 概要

厳密な直列化可能性と線形化可能性について，それらとアプリケーション不変量が等価，かつ因果関係のないトランザクションや操作のリアルタイム保証を緩和したRegular Sequential Serializability / Consistencyを提案．Spannerにおける読み取りトランザクションの遅延を低減した．


以下，読書メモや疑問点を記載．

## 1. Introduction

## 2. Background and Motivation

* 2.3 Consistency Models
* > The correctness of an application is determined by its
invariants, which are logical predicates that hold for all states of an application (i.e., the combined states of all application processes).
* （この論文では）まず第一にinvariant を correctness と定義していて，serializabilityなどの性質ではない
* invariantをユーザが定義するのが難しいから， serializabilityなどの性質がDBからユーザに提供されているのだと思っていたけど．
* Strict serializability の望ましい性質は維持しつつその制限を緩めることで、性能を稼ぐ余地を生み出そうという話。
* "2.4 Strict Serializability is Too Strong"
* "2.5 Process-Ordered Serializability is Too Weak"

## 3. Regular Sequential Consistency Model

* 3.1
* 「アプリケーションは $n$ プロセスの集まり ($= \{ P_1, \dots, P_n \}$)」とモデル化
* アプリケーションのプロセスは execution の prefix-closed set を定義する
* "Prefix-closed" とはなんぞ
* ある集合の要素の任意の prefix もまた、その集合の要素になるってことかな。
* ステートとアクションの交互の列で，ステートで始まってステートで終わるもの
* $s_0, \pi_1, s_1 \dots$
* アプリケーションステートは長さ $n$ のベクトル
* アプリケーションアクションは 1 つのプロセスによって実行されるステップで internal / input / output の 3 種類がある
* Internal: local computation
* Input/output: interaction with other processes
* $P_i$ と $P_j$ は双方向チャネルでメッセージをやりとりする
* $\alpha | P_i$ は execution $\alpha$ のうち $P_i$ のステートとアクションを取り出したもの

* > While they do allow more anomalies, prior work suggests
anomalies with much weaker models (...) are rare in practice (e.g., at most six anomalies per million operations [57]).
* [57] はこれ https://research.facebook.com/publications/existential-consistency-measuring-and-understanding-consistency-at-facebook/
* 面白そう．

* RSS は Serializable だけど、Stale read をちょっぴりだけ許すという理解で OK？
* ちょっぴりだけというなら、もっと緩めても良いかも知れないが……
* Serializable の部分は Conflict serializable？ --> Invariant equivalence という概念を使って濁している。ある意味最も一般的な Serializability の定義といえるかも知れない。

## 4. Practical Implications

## 5. Spanner-RSS
* it requires 𝑇RO to observe 𝑇RW even before 𝑡ee if there is some other RO transaction that finishes before 𝑇RO and includes any of 𝑇RW’s write
* これってどういうケースですか？⇦後から始めたやつが先に終わったらこうなりそう？

## 6. Spanner-RSS Evaluation

## 7. Gryff-RSC

## 8. Related Work

## 9. Conclusion