Pith Number

pith:U4PRVX3T

pith:2026:U4PRVX3T7QCNG2FSMMUUZGS5HY

not attested not anchored not stored refs resolved

Optimal Oblivious Load-Balancing for Sparse Traffic in Large-Scale Satellite Networks

Eytan Modiano, Rudrapatna Vallabh Ramakanth

No oblivious routing scheme can achieve worst-case load lower than approximately √(2k)/4 on an N×N torus with at most k active pairs.

arxiv:2601.02537 v5 · 2026-01-05 · cs.NI · cs.DC

Open paper page JSON Open Graph Bundle Merged state What is a Pith Number?

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

no oblivious routing scheme can achieve a worst-case load lower than approximately √(2k)/4 when 1<k ≤ N²/2 and N/4 when N²/2≤k≤N². Moreover, we demonstrate that the celebrated Valiant Load Balancing scheme is suboptimal under sparse traffic and construct an optimal oblivious load-balancing scheme that achieves the lower bound.

C2weakest assumption

The network is exactly an N x N torus with uniform capacities and traffic consists of at most k active source-destination pairs whose locations are unknown in advance.

C3one line summary

For sparse traffic with k pairs in an N x N torus, the minimal worst-case load achievable by any oblivious routing is approximately sqrt(2k)/4, with a new scheme attaining this bound and outperforming Valiant load balancing.

References

28 extracted · 28 resolved · 0 Pith anchors

[1] Delay is Not an Option: Low Latency Routing in Space, 2018

[2] A dynamic routing concept for ATM-based satellite per- sonal communication networks, 1997

[3] A distributed routing algorithm for datagram traffic in LEO satellite networks, 2001

[4] Capacity provisioning and failure recovery for Low Earth Orbit satellite constellation, 2003

[5] Routing strategies for maximizing throughput in LEO satellite networks, 2004

Formal links

2 machine-checked theorem links

Cited by

1 paper in Pith

Capacity Scalability of LEO Constellations With Dynamic Link Failures

Receipt and verification

First computed	2026-05-18T03:09:32.281959Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

a71f1adf73fc04d368b263294c9a5d3e3b7eb6eb6e5aa8f4264019e4aac00756

Aliases

arxiv: 2601.02537 · arxiv_version: 2601.02537v5 · doi: 10.48550/arxiv.2601.02537 · pith_short_12: U4PRVX3T7QCN · pith_short_16: U4PRVX3T7QCNG2FS · pith_short_8: U4PRVX3T

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/U4PRVX3T7QCNG2FSMMUUZGS5HY \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: a71f1adf73fc04d368b263294c9a5d3e3b7eb6eb6e5aa8f4264019e4aac00756

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "af2d5141685e3acc49a412ea076c8c9c38b0d72224824f9b51cd2ae59a99eeda",
    "cross_cats_sorted": [
      "cs.DC"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.NI",
    "submitted_at": "2026-01-05T20:21:38Z",
    "title_canon_sha256": "2ad10b442f446b28e61c6d4d90d6adf3525a316cad4a69747a5ee4274d3f1dc1"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2601.02537",
    "kind": "arxiv",
    "version": 5
  }
}