Performance · Distributed Computing

Waiting for the slowest

A search query, a map-reduce job, a read from replicated storage: many computations split into parallel pieces and finish only when the last piece does. How long do they take on average? For three or more parallel servers, no exact formula is known.

Born from the forecast

Singularity predicted that Kolmogorov-Arnold networks would reach distributed computing. We used one as an exploration tool on simulated queues, and it pointed at an unexpected shape: the dependence on the number of servers grows like the square root of its logarithm.

What we found

The approximation starts from a classical upper bound, which pretends that the parallel queues are independent, and shrinks it by a factor that accounts for how arrivals tie the servers together.

1.03%

maximum error, exponential service, up to 128 servers

3.2% · 11%

the two best-known approximations on the same test

1.2–2.4%

on three service distributions never seen in calibration

10% · 34%

where it fails: lognormal and uniform service

How we tested it

The formula was found and calibrated on one set of simulations, then tested once on new simulations, with targets written in advance. One target, under 5% error on every unseen family, was not met, and the paper says so in its abstract.

Why it matters

Capacity planning for parallel systems relies on quick estimates. A formula that is accurate well beyond the exponential case, and honest about where it breaks, is more useful than one that is only tested where it works.