Bodega: Localized Linearizable Reads at Anywhere Anytime via Roster Leases
Talkat 20th USENIX Symposium on Operating Systems Design and Implementation (OSDI '26) · 2026-07-13..07-15·
summary
Bodega introduces roster leases: an all-to-all leasing layer that decouples lease participants from the protected metadata (the roster) so any responder holding a majority of grants can serve linearizable reads locally. It implements optimistic holding and early-accept notifications to avoid stalls from concurrent writes, requires a responder-covering quorum for commits, and runs in async Rust inside the Summerset codebase. Evaluation on five geo-distributed CloudLab nodes (10% writes, 90% reads) shows 5.6x–13.1x average read speedups in WAN vs prior protocols and supports proactive roster changes in about two RTTs.
AI-written summary · about
chapters (10)
- 0:00Bodega and roster leases
- 1:43Localized linearizable reads goals
- 3:07Decoupling leases from consensus
- 8:45Roster leases in three steps
- 14:02Bodega protocol details
- 17:54Handling failures and roster changes
- 18:38Implementation and evaluation
- 19:20Read latency and configurability
- 21:29Comparison with etcd
- 22:31Conclusion and Bodega's goals
related talks
01h 11mFearless global transactions with
41mResource Fairness: Implementing (and Deprecating) a Lease Broker
15mTreebeard: A Scalable and Fault Tolerant ORAM Datastore
32mHave a SQL and Eat it Too!
01h 12mScaling distributed ledgers: Achieving arbitrary throughput and sub-second latency
15mROLEX: A Scalable RDMA-oriented Learned Key-Value Store for Disaggregated Memory Systems
19mA zone-aware cache system for distributed databases
32mLow Latency Serving of Offline Data: Efficient, Safe, and Reliable Data...