PaperlayerView exact revision on arXiv

Source-linked AI summary

Undirected Network Coding and Faster External-Memory Integer Sorting

Baochun Li, Zongpeng Li, Sirui Liu

arXiv:2610.20079v1cs.DScs.CCcs.ITmath.IT

TL;DR

Whether integer sorting can beat the external-memory comparison bound has been a central open problem since Aggarwal and Vitter posed it. This paper converts a finite coding advantage into recursive address interchange and a deterministic sorting algorithm. Its bound asymptotically improves on comparison sorting in some parameter regimes, and the paper also establishes a strict coding advantage over routing.

  • Problem

    Since 1988, whether integer keys' bits can improve external-memory sorting beyond the comparison bound has remained a central open problem.

    Source: §1 · p. 2

  • Method

    A finite binary linear coding construction is adapted into recursive address-field interchange and combined with Columnsort and MSD radix sorting.

    Source: §1 · p. 2

  • Results

    For N integers of Θ(log N) bits and 2B ≤ M ≤ N, the I/O bound asymptotically improves on classical comparison sorting in some parameter regimes.

    Source: §1 · p. 2, §8 · p. 28

  • Takeaways & Limitations

    The finite construction supports both a strict coding advantage in an undirected network and fewer block transfers for sorting in some parameter regimes.

    Source: §8 · p. 28

    The sorting result is stated for N integers of Θ(log N) bits, with memory and block parameters satisfying 2B ≤ M ≤ N.

    Source: §2.1 · p. 4

Abstract

from arXiv · show

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 $\Theta(\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.

1 Introduction

The Li–Li conjecture [LL04] links whether network coding can outperform routing in undirected multiple-unicast networks to the open question of improving external-memory integer sorting beyond comparison bounds [FHLS19]. This paper turns a finite coding advantage into recursive address-field interchange and a deterministic sorting algorithm with an asymptotic improvement in some parameter regimes.

1 Introduction

  • Aggarwal and Vitter posed the question in 1988 of whether integer keys' bits can improve external-memory sorting beyond the comparison bound.Farhadi et al. showed that if the Li–Li conjecture holds, arbitrary bit operations cannot asymptotically improve sorting in parameter ranges including B ≥ log N [FHLS19].Source: §1 · p. 2
  • A finite binary linear network construction yields a coding advantage that the paper adapts to recursive address-field interchange, then combines with Columnsort and MSD radix sorting.The address-interchange method builds on recursive field-exchange techniques.Source: §1 · p. 2
  • For every 2B ≤ M ≤ N, the paper gives a deterministic sorter for N integers of Θ(log N) bits, asymptotically improving on comparison sorting in some regimes.The stated bound uses ε = 1.8 × 10^-11; the algorithm handles repeated values, uses at most M words, and has polynomial disk space.Source: §1 · p. 2

1.1 Related work

  • The paper places its sorting method alongside prior external-memory integer techniques, while noting those results address different operations or retain comparison-sorting I/O bounds.Examples include dictionary updates [IP12], priority queues [JL19], and Columnsort-based sorting.Source: §1.1 · p. 3
  • Earlier counterexamples refute the Li–Li conjecture [ZLL26] [BH26], but do not by themselves yield a faster sorting algorithm.This paper uses a finite construction both for a coding-rate separation and to support recursive address permutations that reduce data movement.Source: §1.1 · p. 4

2 Main Results

The main results establish a deterministic external-memory integer sorter with an asymptotic advantage in some parameter regimes and a finite undirected network where binary linear coding strictly outperforms fractional routing. The sorting algorithm is stated for all 2B ≤ M ≤ N and is correct on every input.

2.1 The external-memory model and sorting bound

  • In the external-memory model, memory holds M words, blocks contain B consecutive words, and each block read or write counts as one transfer.The algorithm may perform arbitrary bit operations after data are read into memory, and buffers and mutable workspace count toward M.Source: §2.1 · pp. 4–5
  • For every 2B ≤ M ≤ N, deterministic sorting uses at most M words and polynomial disk space, is correct on every input, and asymptotically improves on comparison sorting in some regimes.The bound's logarithmic factor depends on both log(M/B) and log M; ε is an absolute constant.Source: §2.1 · p. 5
  • When the input fits in memory, reading, sorting, and writing it takes the optimal O(N/B) block transfers.The theorem's input consists of N integers of Θ(log N) bits.Source: §2.1 · pp. 4–5

2.2 The communication model and coding counterexample

  • The coding comparison uses finite-round binary linear protocols: edge transmissions are XORs, with fixed times and directions, and common rate is delivered bits per round.Routing is fractional path flow subject to shared edge capacities; coding requires each sink to recover its message with zero error.Source: §2.2 · pp. 5–6
  • A finite undirected unit-capacity network with independent source messages admits a binary linear block-code rate strictly above the fractional-routing upper bound.The network can be chosen as a simple graph.Source: §2.2 · p. 6

3 Proof Overview

The overview connects coding’s advantage over routing to faster data rearrangement, then uses that operation within a recursive sorting framework. The construction preserves values while changing positions, and its recursive savings reduce the data handled by later exchanges.

3.1 Rearrangement in sorting

  • Columnsort’s position-determined rearrangements preserve values and bring elements from different original columns together for later comparison.The required movements reduce to a constant number of address-field exchanges and sequential scans.Source: §3.1 · p. 6, Figure 1 · p. 7

3.2 Circuits and the coding counterexample

  • A coding circuit yields an undirected network where coding approaches rate one while routing is bounded strictly below one.Matrix labels make every source–sink path at least m long, giving r ≤ S/(Wm) < 1; the construction uses nested subspaces to control rank costs.Source: §3.2 · pp. 7–8

3.3 Using coding to accelerate address interchange

  • For address-field exchange, a three-step modular update performs the swap, with within-column shifts handled by scans and the intercolumn move accelerated.The address radix supports matrix coefficients while data bits are combined by XOR.Source: §3.3 · p. 9
  • At each circuit node, a shared permutation keeps stream bits aligned for XOR; the output displacement exchanges the fields while restoring each original value.The node matrix label specifies the permutation, and the sink-minus-source matrix is I_m.Source: §3.3 · pp. 9–10, Figure 4 · p. 10
  • Coding reduces recursive exchange volume from mV to SV/W, with S/W < m^(1−ε); once fields reach Θ(log(M/B)) bits, buffers fit in memory for direct processing.Each recursive level shrinks field width by a factor of m and data volume by a factor of W.Source: §3.3 · p. 10

3.4 From rearrangement to sorting

  • Recursive Columnsort and most-significant-digit radix sorting combine local sorting bounds across levels to obtain the overall block-transfer bound.For N ≤ M^2, the local bound also implies the overall bound.Source: §3.4 · pp. 10–11

4 A Counterexample to the Undirected Multiple-Unicast Conjecture

The section constructs an undirected multiple-unicast network from a finite binary linear circuit and uses a strict total-rank saving, certified through matrix labels, to establish that coding achieves a higher rate than routing. It also gives fixed parameters for the saving and shows the advantage on a simple network.

4.1 The Coding Scheme

  • Three rounds of basic blocks implement (X, Y) → (Y, X), restoring every auxiliary register to its initial value.Each block implements one of the XOR updates Y ← Y + X or X ← X + Y, and the construction works for arbitrary auxiliary initial values.Source: §4.1 · pp. 12–14

4 A Counterexample to the Undirected Multiple-Unicast Conjecture

  • r ≤ S/(Wm) < 1: every routing scheme has common rate below the circuit’s achievable coding rate on the constructed network.The edge lengths sum to S < Wm, while every paired source-to-sink path has length at least m.Source: §4 · p. 11, §4.2 · pp. 14, 17

4.2 Matrix Labels

  • The endpoint labels save one unit of length per data-path pair; controlled decreases on central paths keep their added cost below that saving.The endpoint saving totals v^3, and the constructed labels have just one decrease on each central path.Source: §4.2 · pp. 15, 17
  • Matrix labels assign edge uw length rank_Q(Mw − Mu); if each paired source and sink differs by I_m, rank subadditivity gives every connecting path length at least m.The lemma’s total rank is S = Wm − v^3 + 6v^2d^2 < Wm.Source: §4.2 · pp. 14, 17

4.3 A Strict Saving in Total Rank

  • The construction has total path length S = Wm − n0 + 2∆ < Wm, yielding a strict total-rank saving.The data paths save n0 relative to 2n0m, while dimension losses on central paths add 2∆ to auxiliary-path length.Source: §4.3 · pp. 17–18
  • With d = 46, m = 463, ε = 1.8 × 10^-11, and τ = 1 − ε, the construction satisfies η = 9/43518487588 > 0 and S/W < m^τ.These constants meet the recursion requirement for a field-width exponent τ < 1.Source: §4.3 · p. 18

4.4 Proof of the Coding Advantage

  • Coding achieves a finite-round common rate strictly above the routing bound, while its rate approaches 1 and is at most 1 by a source-leaf cut.Pipelining circuit executions gives rates at least k/(k + D); letting k grow yields coding rate at least 1.Source: §4.4 · pp. 18–19
  • The coding advantage persists when the network is made simple by subdividing parallel edges with private forwarding vertices.The subdivision preserves the routing bound and gives coding only a constant startup delay.Source: §4.4 · p. 19

5 Address-Field Interchange

The section turns a finite coding advantage into a deterministic address-field interchange, recursively reducing long-field exchanges to short-field exchanges. Its recursion has a buffered base case and a cost governed by the coding construction’s saving.

5.1 The interchange operation

  • An address-field interchange moves each bit from (p, t, g, d, z) to (p, d, g, t, z), preserving its value and the other coordinates.The permutation depends on addresses, not key values; intermediate coding steps must restore each bit’s value.Source: §5.1 · p. 19

5.2 The Coding Recursion

  • A complete coding-recursion level replaces an interchange by S width-f interchanges, each on V/W bits, plus O(1 + V/(Bw)) transfers and a fixed number of block buffers.The two fields each have e = mf base-q digits, and the recursive calls use width f.Source: §5.2 · p. 20
  • The recursion accelerates the middle update H ← H + D; the first and last updates can be performed sequentially using cyclic shifts and reversals.Three updates interchange the paired short fields, and hence the full fields.Source: §5.2 · p. 20

5.3 The Recursion Bound

  • When the fields fit in memory, buffering and scans cost O(1 + V/(Bw)); otherwise, normalized recursive cost obeys F_k ≤ λF_{k−1} + O(1) and F_k = O(m^(kτ)).The base case buffers field-value streams, while λ = S/W captures the recursive cost multiplier.Source: §5.3 · p. 23
  • The general-width bound is Q(e, V) = O(1 + V/(Bw)[1 + (e/t₀)^τ]); padding and memory simulation preserve the stated bound for the actual binary addresses.The schedule is deterministic and dimension-dependent, with at most M words of memory and polynomial disk space.Source: §5.3 · p. 23

6 Local Sorting

The section reduces local sorting to Columnsort’s fixed rearrangements, implemented through address-field interchanges and scans. It then recursively sorts the columns while respecting the memory and disk-space limits.

6.1 The Columnsort Reduction

  • Columnsort sorts s contiguous columns of r records using four rounds of column sorting, six width-t address-field interchanges, and sequential scans.Here s = 2t and r = s^3; the procedure is correct whenever the column sorts are correct.Source: §6.1 · p. 24
  • After the zero–one rearrangement steps, possible disorder lies in an interval of length at most r/2, which a half-column sentinel shift brings into one column for sorting.The zero–one argument extends correctness to general ordered records, and removing sentinels by multiplicity preserves the input multiset.Source: §6.1 · p. 25

6.2 The Local Sorting Bound

  • For 1 ≤ n ≤ M², the local algorithm sorts n records using at most M words of memory and polynomial disk space.It recursively applies Columnsort and sorts in memory once a call is small enough.Source: §6.2 · p. 25
  • Each nonterminal recursive call reduces column length to less than 8z^(3/4), yielding constant depth for the stated local range; its interchanges use fields of width O(log M).Short-column rounds share sequential streams, and the total cost follows by summing the levels.Source: §6.2 · p. 26

7 Sorting Arbitrary Input Sizes

The section sorts arbitrary input sizes by recursively partitioning on high-order bit groups and sorting within buckets. It also gives an individual-record-access alternative and combines the bounds into a deterministic theorem for the stated memory range.

7.1 The Cost of One Partition

  • One bit-group partition of an array of length n > H² forms contiguous buckets in increasing bit-group order, with the stated transfer bound; interval concatenation alone costs O(n/B).The method locally sorts subarrays by the current bit group, then concatenates their intervals using a fixed number of buffers.Source: §7.1 · pp. 26–27

7.2 The Cost of High-Order Recursion

  • For N ≥ M², high-order recursion partitions integers by successive bit groups, processes nonempty buckets in increasing order, and sorts each bucket recursively.If no bit groups remain, all integers in that subproblem are equal and can be output directly.Source: §7.2 · p. 27
  • Processing Θ(log M) bits per recursion level gives depth O(log N/log M); the per-level cost and this depth yield the stated large-input bound.For N ≥ M², p = log(N/M) ≥ log M and log N ≤ 2p.Source: §7.2 · p. 27

7.3 An Alternative Using Individual Record Accesses

  • The alternative least-significant-digit radix method sorts N integers of w = Θ(log N) bits in O(N) block transfers for every M ≥ 2B.It handles ⌊log N⌋ bits per pass, using a constant number of passes and individual record accesses.Source: §7.3 · p. 28

7.4 Proof of the Main Sorting Theorem

  • The deterministic algorithms are correct on every input, satisfy the memory and polynomial disk-space requirements, and establish the theorem for every memory-to-block-size ratio, including bounded-B cases.For M below the fixed threshold, B is bounded, so Lemma 7.3’s O(N) cost is O(N/B); the proof takes fixed ε = 1.8 × 10−11 > 0.Source: §7.4 · p. 28

8 Conclusion

The conclusion presents the coding construction as a bridge from communication savings to recursive address-field interchange and deterministic external-memory sorting. The resulting sorting bound asymptotically improves on classical comparison sorting in some parameter ranges.

8 Conclusion

  • The paper turns communication savings from a finite linear circuit into recursive address-field interchange.It combines the interchange with Columnsort and most-significant-digit radix sorting to obtain deterministic external-memory integer sorting.Source: §8 · p. 28
  • The sorting algorithm asymptotically improves on classical comparison sorting in some parameter ranges.The conclusion also reports a strict coding advantage in an undirected multiple-unicast network.Source: §8 · p. 28
  • Further work includes increasing the finite construction’s saving exponent, simplifying implementations, and testing whether coding can accelerate other data-movement tasks.Source: §8 · p. 28

A Buffered I/O and Memory Simulation

A buffered simulation turns sequential tape work into block transfers by keeping a small window around each tape head. Its cost scales with tape steps and separately activated phases, and the paper states that its stream transformations satisfy the required access pattern.

A.1 Simulating sequential tape access

  • The tape model permits only single-bit reads or changes and head movements of at most one position per step, not arbitrary jumps.A fixed alphabet and track count affect packing density only by a constant factor.Source: §A.1 · p. 29
  • A phase of T tape steps uses O(B) resident words and O(1+T/(Bw)) block transfers; J separately activated phases cost O(J+T/(Bw)).Source: §A.1 · p. 29
  • Keeping the current block and its two neighbors buffered lets the head move locally without transfers until it exits the window.On exit, dirty blocks are written back and a new window is loaded; each exit requires at least b head movements.Source: §A.1 · p. 29
  • The Section 5 stream transformations meet the phase bound because prefix-fiber work is concatenated, with local reversals, returns, and erasures included in linear tape-step counts.Each recursion node uses only a fixed number of these procedures.Source: §A.1 · p. 29

A.2 Suspending and restoring recursive calls

Recursive calls keep suspended streams on disk and reuse the active call’s windows and control workspace. The resulting boundary costs add O(1+V/(Bw)) transfers per parent without changing the recursive volume multiplier.

A.2 Suspending and restoring recursive calls

  • Each active call has disjoint, packed disk regions for its role streams and temporary tapes, while suspended calls have no resident buffers.Only the active call owns the tape windows; fresh work regions are initialized within the O(V) local work budget.Source: §A.2 · p. 29
  • Suspending a call flushes its dirty windows and writes a fixed-size frame containing the parent descriptor and continuation; the child reuses the windows and workspace.Frames occupy a fixed number of block-aligned blocks, so stack reads and writes cost O(1) transfers even when B=1.Source: §A.2 · pp. 29–30
  • On return, the child writes back its windows, places output in the parent role, and restores the parent from the top stack frame without scanning ancestor data.Output copying costs O(1+V/(WBw)) per child, while flushing, stack access, and window reactivation cost O(1) per child.Source: §A.2 · p. 30
  • Across the fixed number S of children, call-boundary work adds O(1+V/(Bw)) transfers per parent and does not alter the recursive volume multiplier S/W.Together with the buffered tape lemma, this yields the node recurrence and accounts for constant overhead at the memory cutoff.Source: §A.2 · p. 30
  • The active windows, stack-transfer buffer, and descriptor fit in c1B+c2 words, and depth-first execution uses polynomial disk space.The execution depth is O(log(2+e)); stored addresses fit in a fixed number of global words.Source: §A.2 · p. 30

A.3 Constant-factor block simulation

A constant-factor block simulation adapts algorithms to the original memory and block parameters while preserving their asymptotic bounds. The parameter transfer yields the main sorting bound, including the cases below the large-input threshold and for small memory.

A.3 Constant-factor block simulation

  • Input and output layout conversion costs O(1+L/B) transfers for L words, while the adjusted memory and block sizes preserve logarithmic parameter scales.The simulation preserves polynomial disk space and changes block size only by a fixed factor.Source: §A.3 · pp. 30–31
  • Logical blocks are stored within physical blocks and transferred through one physical block buffer, so each logical transfer costs a constant number of physical transfers.The simulated algorithm uses at most M/4 words for state, B≤M/2 words for the transfer buffer, and the remaining memory for control.Source: §A.3 · p. 30
  • The simulation preserves the main bound (2) in the original parameters and applies each sorting bound for every 2B≤M under its input-size condition.The address-field interchange needs only an increased absolute memory threshold.Source: §A.3 · p. 31
  • Ordinary local sorting transfers to the original parameters by dividing inputs up to M^2 into at most 64 subarrays, sorting them, and using a constant number of merge rounds when needed.Each merge round costs O(1+n/B) transfers; the construction uses only local sorting and merging, not general sorting.Source: §A.3 · p. 31
  • For N≥M^2, the large-input bound is preserved; combining it with local sorting for M≤N≤M^2 gives the main bound (2).When M<C*, bounded B makes the O(N) cost of Lemma 7.3 also O(N/B), while bounded local inputs can use direct comparison sorting.Source: §A.3 · p. 31

B Exact Verification of the Fixed Parameters

The appendix verifies a strict gap in the exponent using rational comparisons and gives explicit finite protocols for the network. The stated protocol rates exceed 1−η for both the original network and its simple graph.

B Exact Verification of the Fixed Parameters

  • For d=46, m=463, ε=1.8×10^-11, and η=9/43518487588, the verified inequality is ε ln m<η.The proof reduces the comparison to rational bounds on ln m.Source: B Exact Verification of the Fixed… · p. 32
  • With D=25 and k=120884687720, the network protocol has common rate k/(k+D)>1−η.The schedule uses 25 rounds for the circuit’s three rounds and 24 gate layers.Source: B Exact Verification of the Fixed… · p. 32
  • For the simple graph obtained by removing parallel edges, D=50 and k=241769375439 also give common rate k/(k+D)>1−η.The schedule expands each round of the original network protocol into two rounds after inserting a private relay into every edge.Source: B Exact Verification of the Fixed… · p. 32

C Interchange for Arbitrary Address Shapes

The lemma implements the interchange of two fields for arbitrary positive address dimensions, including arbitrary intervening-coordinate cardinality. Its recursive construction pads the array by less than a factor of two while preserving the stated memory and polynomial disk-space guarantees.

C Interchange for Arbitrary Address Shapes

  • Padding the prefix count to a multiple of W^k yields a rectangular array of volume V′ < 2V and requires one scan.High-order digits first create enough segments; padding is applied after that count is sufficient.Source: C Interchange for Arbitrary Address… · pp. 32–33
  • For arbitrary positive P, G, ℓ, and e, the construction implements the exact interchange of the two fields, with recursive padding increasing each call’s volume by less than a factor of two.The swaps fix the prefix and intervening coordinate; the memory and polynomial disk-space guarantees are preserved.Source: C Interchange for Arbitrary Address… · pp. 32, 34
  • Taking high-order digits creates enough prefixes for the recursive depth; fields too short to supply them are handled by a constant number of base interchanges.When enough digits are available, the high and low parts are separated, the low parts interchanged, and the high parts restored.Source: C Interchange for Arbitrary Address… · pp. 32–33
  • Moving one base-q digit across intervening coordinates costs O(1 + V/(Bw)) transfers, even when the crossed coordinate has arbitrary cardinality G.The digit is distributed into q streams and read sequentially; applying the move digit by digit implements E and F in O(ρ) scans.Source: C Interchange for Arbitrary Address… · p. 33
  • The remaining field width is partitioned into corresponding equal-width chunks, whose swaps preserve the prefix and satisfy the recursive divisibility condition.A residual pair, if present, requires at most one base interchange.Source: C Interchange for Arbitrary Address… · p. 34
  • After the complete swaps, removing the still-zero padded segments restores the original volume before the high digits are moved back.Removal is delayed until all swaps finish because intermediate coded states need not keep discarded segments zero.Source: C Interchange for Arbitrary Address… · p. 34

D Formal Verification and Reproducibility

Lean 4 and Mathlib formalize the sorting and network results, including sorting’s correctness and resource bounds and the strict coding advantage on one network. The appendix also states verification conventions, reproduction checks, and the authors’ use of AI tools.

D Formal Verification and Reproducibility

  • For every 2B ≤ M ≤ N, the formalized sorting algorithm terminates, preserves multiplicities, outputs sorted integers, and meets its stated resource bounds with ε = 1.8 × 10^-11.The bounds cover memory, disk space, and block transfers.Source: D Formal Verification and… · pp. 34–35
  • The network formalization verifies a finite binary linear code whose common rate strictly exceeds the routing bound on the same finite simple undirected network.The messages are independent and edge capacity is shared by both directions.Source: D Formal Verification and… · p. 35
  • The sorting formalization counts each read or write of a B-word block as one I/O and charges data buffers and mutable workspace to the M-word limit.In-memory computation is modeled as transformations of data already read into memory, not as machine instructions or computation time.Source: D Formal Verification and… · p. 35
  • For very small memory, a predetermined execution-step index is stored outside the M words, so the verification does not establish that this control information fits within the same limit.The narrow-word construction uses two data buffers.Source: D Formal Verification and… · p. 35
  • The archived Lean proofs passed a complete build and axiom-dependency check, with no unfinished proofs or additional mathematical axioms.Reproduction requires the Lean and Mathlib versions specified by the project.Source: D Formal Verification and… · p. 35

AI methodology

  • ChatGPT, including Codex, assisted with network-coding and sorting exploration, mathematical arguments, Lean proofs, and manuscript preparation.The authors retain responsibility for the content’s correctness, originality, and integrity.Source: AI methodology · p. 38

Related papers

Loading 2610.20079v1…