Online Codes¶
Rateless erasure codes with locally generated check blocks and staged probabilistic message recovery.
Core Idea¶
Online codes, in Maymounkov's named construction, are a particular rateless erasure-code family. A finite message is divided into blocks and processed by an outer code into a slightly larger composite set. The encoder can then create successive check blocks on demand, each formed from a randomized sparse XOR of composite blocks. There is no fixed total codeword length in advance, and generating one check need not require generating previous checks. These are defining differences from a conventional fixed-rate erasure code; ratelessness alone does not identify this construction.
The receiver uses checks whose unknown-neighbor count has fallen to one, then propagates recovered blocks through the sparse graph. The inner process may leave a small residual; the outer code makes full message recovery possible under the model. The original paper proves parameter-dependent near-linear overhead and probabilistic recovery; no arbitrary tiny fraction of checks can reconstruct a larger unknown message. Its reported Java experiments are an attested implementation of the code, whereas peer-to-peer file dispersal is presented in the paper as a motivation and proposed use, not evidence of deployment.
Scope of Application¶
These comparisons require the original two-stage code and its stated recovery assumptions.
- Unknown-loss communication. Generate additional checks without precommitting to one erasure rate.
- Multi-source file research. Reason about combining independently generated checks under the paper's assumptions.
- Coding-theory comparison. Separate local generation, outer completion, and overhead from generic ratelessness.
- Implementation evaluation. Compare actual test overhead and runtime with theorem limits without treating them as channel-universal.
Clarity¶
An online code uses outer auxiliary blocks plus locally generated rateless XOR checks; after enough are received, inner peeling and outer completion recover the source with a stated probability. LT codes are the closest named rateless neighbor but need not share this construction. Fixed-rate codes preselect a finite expansion, and an arbitrarily small fraction of checks cannot determine an n-block message. The 2002 Java tests support a research implementation, not a documented peer-to-peer deployment.
Manages Complexity¶
The name compresses a sparse random graph, unbounded check generation, inner peeling, and outer completion into one code family. That simplifies analysis of unknown erasure rates, but conceals the assumptions behind probability of recovery and the difference between asymptotic overhead, one implementation's measurements, and real-channel performance. Those layers must be reopened before transfer.
Abstract Reasoning¶
- Specify source-block count and the loss model.
- Identify the outer composite-block transformation.
- Check how each on-demand XOR block chooses degree and neighbors independently.
- Trace when a received check becomes solvable and how recovery propagates.
- State the received-check threshold, failure probability, and whether evidence is theorem, experiment, or deployment.
Knowledge Transfer¶
The on-demand-check idea can inform file dispersal and unknown-loss channels, but Maymounkov's exact degree distribution, overhead bound, and outer-code guarantee transfer only under their assumptions. An LT or Raptor code shares fountain behavior without thereby becoming this online-code construction, and an observed Java test does not certify an untested network.
Neighborhood in Abstraction Space¶
Online Codes sits in a moderately populated region (43rd percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Memory Storage, Retrieval & Encoding (9 abstractions)
Nearest neighbors
- Error-Correcting Code — 0.91
- Reachability analysis — 0.88
- Data Format — 0.87
- Logic Circuit — 0.86
- Higher-Order Message — 0.86
Computed from structural-signature embeddings · 2026-10-08