How to linearize your cluster

[sipa]

@stefanwouldgo

Assuming cubic runtime, we might expect 500 nodes to run in less than 50 \mu sμs\mu s.

I think that would be an incorrect assumption; the benchmarks in the paper seem to exhibit behavior very far from the proven complexity bound. I ran regression on its data set, and obtain runtimes that are approximated by t = 0.00098 \times n^{0.091} \times m^{0.77}.