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.
Structural Signature¶
Sig role-phrases:
- message block set — Partitions a finite original message into fixed-size blocks under one code instance. It is constitutive. Counterfactual: An unrelated stream of random bits does not encode a recoverable message.
- outer composite encoding — Adds auxiliary redundancy so partial recovery of composite blocks can close to the original message. It is constitutive. Counterfactual: Peeling a fraction of check-block neighbors alone need not recover every original block.
- rateless local check generator — Produces independently addressable random-degree XOR checks without fixing the total encoded length. It is constitutive. Counterfactual: A fixed finite codeword or check that depends on generating earlier checks lacks this online-code combination.
- received-check peeling — Recovers a composite block when a check's other incident blocks are already known, propagating further recovery. It is constitutive. Counterfactual: An arbitrary pile of checks without a solvable dependency structure has no stated decoding mechanism.
- probabilistic overhead bound — Limits recovery to sufficient received checks and declared epsilon/size/failure assumptions. It is boundary. Counterfactual: A few arbitrary checks cannot reconstruct an n-block message merely because the code is rateless.
What It Is Not¶
- Any rateless code. LT and other fountain codes can emit indefinitely but use different constructions and guarantees.
- Fixed-rate parity code. A finite preselected expansion lacks on-demand unbounded checks.
- Recovery from any tiny fraction. The receiver needs enough independent checks relative to message size and the failure model.
- Network deployment. The published experiments test an implementation; proposed peer-to-peer use is not an observed installation.
- Closest near-miss. An LT code is the closest named rateless neighbor: it generates many checks, but the original online-code construction adds its own outer preprocessing, local-encoding guarantee, and distinct recovery tradeoff.
Scope of Application¶
- 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¶
A positive online-code case has finite source blocks, outer auxiliary preprocessing, on-demand random-degree XOR checks, and a receiver that peels checks then closes the residual with the outer code. An LT code is the near miss: also rateless, but not automatically the same two-stage local construction. A small handful of checks cannot recover more unknown source blocks than its information permits. The original paper's Java tests demonstrate the design in research, not documented production 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.
Examples¶
Canonical¶
In the source construction, split an n-block message, add auxiliary outer-code blocks to make a composite message, then request check blocks one at a time. Each check chooses a degree and XORs selected composite blocks without first building a fixed-length codeword. At the receiver, a check with one unknown neighbor reveals that block; newly known blocks can unlock further checks, and the outer stage resolves the remaining fraction. This is a worked architecture, not a guarantee that an arbitrary handful of checks suffices.
Mapped back: message block set → the n source blocks; outer composite encoding → auxiliary blocks appended before check generation; rateless local check generator → on-demand degree-chosen XOR checks; received-check peeling → degree-one residual checks propagate decoded blocks; probabilistic overhead bound → recovery only after sufficiently many checks under source parameters.
Applied / In Practice¶
Maymounkov's published implementation study actually encoded and decoded with an unoptimized Java program. With the stated test parameters it reported received-check-to-message-block ratios of about 1.025–1.07 for 5,000-block messages and narrower intervals for larger tests. This attests a research implementation of the staged code; it is not proof that peer-to-peer deployment occurred or that its measured ratios hold for every channel.
Mapped back: message block set → tested 5,000-, 32,000-, and 100,000-block messages; outer composite encoding → implemented preprocessing in the tested design; rateless local check generator → program-generated check blocks; received-check peeling → tested decoder's successful recovery; probabilistic overhead bound → source-specific observed overhead intervals, not universal certainty.
Structural Tensions¶
T1 — Unbounded Output versus Finite Recovery Threshold. A sender can keep generating checks, but the receiver still needs enough independent information under the code's probabilistic guarantee.
Diagnostic: How many checks and what failure model are actually claimed?
T2 — Local Check Generation versus Outer Completion Burden. Fast independent checks simplify unknown-loss delivery, but preprocessing and residual recovery remain essential.
Diagnostic: Which outer stage closes the partially decoded message?
Structural–Framed Character¶
A provisional portable skeleton is generating redundancy on demand under uncertain loss. Maymounkov's online codes preprocess message blocks, produce sparse random-degree XOR checks locally, and recover probabilistically after enough checks; generic Encoding is an operation, not this family.
Evaluative weight: Efficiency claims depend on degree and channel assumptions. Human-practice-bound: Moderate, because code design and decoder rules are chosen while guarantees are mathematical. Institutional origin: Coding theory names the construction; one implementation test is not universal evidence. Vocabulary travels: File dispersal may use the scheme under matched assumptions; LT/Raptor codes are related, not identical. Import versus recognize: Recognize the two-stage check construction; calling any rateless code “online” imports unsupported outer recovery structure.
Its character: A specific erasure-code family with portable on-demand redundancy and formal probabilistic premises.
Structural Core vs. Domain Accent¶
Skeletal core. Produce additional redundant checks as needed to recover data despite unknown losses.
Domain-bound accent. Composite preprocessing, sparse random-degree XOR checks, local encoding, and staged probabilistic decoding define Maymounkov's family.
Why not prime. Redundancy is broad; other fountain codes need not use this construction or guarantee.
Instantiates / Related Primes¶
-
Related — fountain code. Online codes are a particular rateless family that generates potentially unbounded encoded blocks from a finite source.
-
Related — LT code. It shares unbounded encoded output but differs in construction and overhead guarantees.
-
Related — erasure code. The source message is recoverable after losses, subject to the stated received-check threshold.
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
Not to Be Confused With¶
- LT code. Tell: Does the Maymounkov outer-plus-local construction actually appear?
- Fixed-rate erasure code. Tell: Can new checks be generated without a predetermined finite codeword?
- Any-fraction recovery. Tell: Were sufficiently many independent checks received?
- Peer-to-peer deployment. Tell: Is the claim a proposed application, simulation, or observed production use?
References¶
- Petar Maymounkov, Online Codes (2002), original research paper: https://pdos.csail.mit.edu/~petar/papers/maymounkov-online.pdf
- Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Online_codes (revision 1336555548).
- Preserved source candidate: https://cs.nyu.edu/media/publications/TR2002-833.pdf
- Preserved source candidate: http://pdos.csail.mit.edu/~petar/papers/maymounkov-bigdown-lncs.ps
- Preserved source candidate: http://pdos.csail.mit.edu/~petar/pubs.html
- Preserved source candidate: http://rubyforge.org/projects/archipelago/
- Preserved source candidate: https://web.archive.org/web/20160303185414/http://rubyforge.org/projects/archipelago/