Equal Opportunity: A Correctness Condition for Ordered Consensus
Talkat 20th USENIX Symposium on Operating Systems Design and Implementation (OSDI '26) · 2026-07-13..07-15·
summary
Defines a formal fairness condition called ordering equality (and a separation parameter delta) and shows randomness is necessary and sufficient to bound bias; builds a reusable Secret Random Oracle abstraction with two implementations (trusted hardware and threshold VRF) and uses it to implement Pompē-SRO that mitigates front‑running and sandwich attacks. Evaluation across regions shows deterministic baselines are heavily biased, Pompē‑SRO reduces bias to within 5% with a noise budget of 5× max network delay, and adds about +1,000 ms median and +2,000 ms tail latency.
AI-written summary · about
chapters (8)
- 0:00Fair state machine replication
- 1:20Ordered consensus fairness
- 3:30Fairness in transaction ordering
- 6:22Ordering equality and separation
- 8:30Fairness with randomness
- 12:04Secret random oracle
- 12:46Evaluating fairness and overhead
- 16:59Takeaways and future work
related talks
19mOrdering So Fair It Ain't Fair Ordering
01h 00mDecentralized Randomness Protocols
56mConsensus Through Herding
42mStochastic reasoning in decentralised systems
29mEquality, Revisited
28mPrivacy versus Robustness in Federated Learning: Limits and Algorithms
24mVerifying Almost-Sure Termination for Randomized Distributed Algorithms
52mGame-Theoretically Secure Protocols Inspired by Blockchains