The FIDS Theorems: Tensions between Multinode and Multicore Performance in Transactional Systems
summary
Paper proves a concrete incompatibility: no sharded, asynchronous transactional system can simultaneously provide serializability, invisible reads and disjoint‑access parallelism, weak nontrivial progress, and the fast decision (one round after a process “knows” its data set). Model uses nodes with multiple processes, cache‑coherent shared memory, and epistemic knowledge to define the one‑round bound. Proof builds two simple conditional transactions on X and Y that must not both commit; result is tight (two rounds avoids the impossibility) and implemented constructions trade correctness for high abort rates.
AI-written summary · about
chapters (14)
- 0:00FIDS Theorems intro
- 1:04Transactional systems
- 6:53Serializability guarantee
- 7:18Distributed transactions
- 9:43Parallel distributed systems
- 12:34Problem in parallel settings
- 13:39Parallelism properties
- 17:13Tensions in properties
- 19:21Fast decision property
- 25:23FIDS impossibility theorem
- 27:10Proof intuition
- 30:32Implications of FIDS
- 33:28Open questions
- 33:50Q&A
related talks
31mSharded & Distributed Are Not the Same:
01h 00mDistributed transactions implementation trade-offs
47mBeing transactional in 2019 - what does this actually mean?
01h 12mScaling distributed ledgers: Achieving arbitrary throughput and sub-second latency
16mFORD: Fast One-sided RDMA-based Distributed Transactions for Disaggregated Persistent...
52mSecrets of High Performance in Multicore Systems ☠️
41mConcurrency, Scalability and Transactions -- Myths and Surprises
52mSecrets of high performance in multicore systems ☠️