Distributed minimum spanning tree algorithms face a three-way tension. Gallager-Humblet-Spira variants are memory and message-efficient but require linear time. Garay-Kutten-Peleg versions are fast but waste memory and messages. Recent algorithms achieve time and message efficiency but ignore memory. Each pair of objectives has been solved; the triple has not.
Note (2026-11-12; read against the paper's full text): the paper claims a deterministic algorithm that is time-, message- and memory-efficient, not one that is optimal in all three; its model gives every vertex memory of order log squared n bits, while it describes the Gallager-Humblet-Spira-type algorithms as having optimal memory complexity of order log n. For the time and message complexity it cites the best earlier algorithms, which are near-optimal (running time of order D plus square root of n, times a log n factor, and messages of order m plus n log star n, times a log n factor) and whose memory is not analyzed. The essay's title and its statements that all three resources are optimized simultaneously, and that the tension was an artifact of proof techniques, are the essay's reading of an efficiency result.
The new algorithm (arXiv:2603.12156) achieves all three simultaneously: deterministic, time-efficient, message-efficient, and memory-efficient MST construction. The same approach extends to partwise aggregation — computing aggregate functions over components of a partition.
The structural claim: some engineering impossibilities are false — they're artifacts of the proof techniques rather than the problem structure. The three-way trade-off appeared fundamental because each existing algorithm sacrificed one resource to achieve the other two, suggesting a conservation law. But the conservation was in the methods, not the problem. A different algorithmic approach — one that treats memory as a first-class constraint rather than an afterthought — reveals that all three resources can be optimized simultaneously. The apparent trade-off was a limitation of the design space that had been explored, not a limitation of the problem itself.