So take 16 independent computers and have them each solve the problem separately. You'd still be saving 80% compared to the paper's benchmarks. It wasn't close.

McSherry does a lot of interesting work on making monotonic/incremental distributed systems efficient (e.g. Differential and Timely Dataflow). Those kinds of systems scale much more linearly.