Network coding enables faster external-memory integer sorting algorithms

Undirected Network Coding and Faster External-Memory Integer Sorting

Data Structures and AlgorithmsComputational ComplexityInformation Theory

Summary

The paper tackles the problem of sorting large lists of numbers stored mostly on slow external memory like hard drives. Normally, sorting is limited by how often data must be moved in and out of memory. The authors show a new way to combine messages during data transfer that breaks this limit, making sorting faster in some cases. They also prove that combining messages (network coding) can be more powerful than just forwarding data (routing) in certain network setups. To ensure their method is correct, they used a formal verification tool called Lean 4.

What this means in practice

  • For database system developers: Design external-memory sort algorithms that reduce data transfer costs by exploiting network coding to achieve faster sorting.
  • For network schedulers: Implement network coding strategies to improve data transfer efficiency in undirected communication networks beyond traditional routing limits.

Authors

Baochun Li, Zongpeng Li, Sirui Liu

Abstract

Network coding allows intermediate nodes to combine messages, whereas routing only forwards them. The Li-Li conjecture asserts that network coding and fractional routing have the same capacity region in undirected multiple-unicast networks. We give a counterexample to this conjecture and apply it to external-memory integer sorting. Since Aggarwal and Vitter posed the question in 1988, whether integer sorting can beat the external-memory comparison bound has remained a central and extensively studied open problem. We give a deterministic sorting algorithm: for $N$ integers of $Θ(\log N)$ bits, a memory holding $M$ integers, and block transfers of $B$ integers, where $2B\le M\le N$, the number of block transfers is $O\left(\frac{N}{B}\left[1+\frac{\log N}{(\log(M/B))^{1-\varepsilon}(\log M)^\varepsilon}\right]\right)$, where $\varepsilon>0$ is an absolute constant. In a range of parameter regimes, this bound is asymptotically smaller than the classical comparison-sorting bound. We also use Lean 4 to verify the sorting algorithm's correctness and complexity bounds, and the strict advantage of coding over routing.