Indeed, it is a tradeoff, and our solution doesn't require consistency across multiple keys.

More generally, any solution that doesn't require transactions across multiple keys, can use Bizur instead of classical Paxos, and achieve the same benefits (faster recovery from failures, higher concurrency, etc.)