NOCS Theorem
USENIX'20 で発表された論文
The NOCS Theorem. No read-only transaction algorithm satisfies all NOCS properties.
NOCS の4つの性質を同時に満たすアルゴリズムは存在しない，ということを定理立てて証明している．
N: Non-blocking.
O: One-round Communication.
C: Constant Metadata.
S: Strict Serializable.
ざっくり意図するところを考えると，「Snapshot IsolationやEventual Consistencyを仮定すればabort-free/non-blockingに実現できるread-only transactionが，Strict SerializableにするとConstant Metadataでは不可能」ということを言っていると思う．
メタデータが無限に（並行実行されるトランザクションの量に比例して）増大することを許容できれば，N+O+S として成立するかもしれない．それは Deterministic Database に帰結しそうな予感がする（最後の一文はポエム）．