DistOptimize finds 4× throughput gains—but its CAS write path exposes the objective-function trap

The headline gain is real—and narrowly measured

DistOptimize applies two formally verified rewrites, decoupling and partitioning, to distributed protocols written in Hydro. In the paper’s Paxos implementation, three optimization steps raise throughput from 180,000 to 570,000 operations per second. A read-only compare-and-swap workload rises from 140,000 to 620,000 ops/s. The authors summarize the cross-protocol range as 1.5–4× throughput, with added latency capped at 0.3 ms in their reported runs.

The test protocol is unusually explicit. Public-protocol experiments use AWS m5.2xlarge instances; two AWS-derived protocols use m8i.2xlarge. Both configurations have eight vCPUs and 32 GB of RAM. Each measurement runs for 90 seconds after a 30-second warm-up and is averaged across three runs. The ILP search returns a solution within 0.01% of its modeled optimum in at most 30 seconds, although end-to-end calibration and benchmarking take hours.

One workload moves backward

The most useful result is the failure case. CAS writes are sequential and latency-bound. When the optimizer is allowed to pursue throughput without a latency constraint, it adds network hops to machines that are not bottlenecks. Write throughput then falls from 1,500 to 500 ops/s at the third optimization step—a 66.7% regression.

The paper does not hide the mismatch. Adding an explicit network-hop constraint restores the write workload to roughly 1,500 ops/s while retaining much of the read-side gain: one constrained configuration reaches 440,000 read ops/s, and two hops match the unconstrained optimizer’s read throughput without its avoidable latency overhead.

That makes DistOptimize a useful benchmark for optimizer evaluation, not just a new optimizer. “Optimal” means optimal for the modeled objective. The exhaustive encrypted-counter test confirms that DistOptimize selects the highest-throughput rewrite at each tested machine budget, but the CAS result shows that this guarantee does not extend to an omitted latency-sensitive workload.

The AWS evidence has a reproduction boundary

The paper also evaluates two protocols reconstructed from AWS specifications. AWS Chain Replication rises from 65,000 to 90,000 ops/s on an internal CI workload, but its throughput-per-machine declines after optimization. The AWS Index Consistency experiment tests a roughly even operation mix and stops after two partitions per machine.

Those results are informative, but they are not independently runnable as reported: the authors release DistOptimize and its proofs, while omitting the internal AWS protocol implementations and workloads. They also caution that the reconstructed implementations do not contain every feature or optimization in deployed services.

The practical lesson is sharper than “4× faster.” A verified rewrite can preserve protocol semantics and still damage an important service-level objective. Any production evaluation should therefore report throughput, latency, machine cost and every workload class the optimizer is expected to protect—not only the metric it was asked to maximize.