PaperlayerView exact revision on arXiv

Source-linked AI summary

The Coverage Depth Problem in Distributed DNA Data Storage

Xiangliang Kong, Ohad Elishco, Chen Wang, Tolga M. Duman

arXiv:2610.02931v1cs.ITmath.COmath.IT

TL;DR

Repeated sampling in DNA sequencing can increase reads beyond the number of information strands, making both latency and sequencing cost relevant to distributed full-message recovery. The paper derives exact analyses and bounds for code layouts, finding that distribution sometimes saves reads and sometimes offers only parallel speedup, while code and layout jointly shape the outcome.

  • Problem

    Repeated reads can make recovery require more reads than the number of information strands, so distributed full-message recovery must distinguish sequencing cost from latency.

    Source: §I · p. 1, B. Distributed Full-Message Recovery · p. 3

  • Method

    The paper derives exact recovery-time formulas and bounds for arbitrary linear-code layouts under synchronous rounds with one read per container.

    Source: A. Distributed Coverage-Depth Problem… · p. 4, §V · p. 23

  • Results

    MDS codes are optimal for fixed partitions; some MDS container regimes save reads while others only add parallelism, and simplex codes uniquely minimize single-container coverage depth up to isomorphism.

    Source: §V · p. 23

  • Takeaways & Limitations

    Whether distribution reduces total-read overhead or only latency depends on code rank geometry and the combinatorial structure of the layout.

    Source: §V · p. 23

    The model synchronously charges M reads each round, including the final round, while asynchronous read allocation is left open.

    Source: A. Distributed Coverage-Depth Problem… · p. 4

Abstract

from arXiv · show

Random sampling in DNA sequencing produces repeated reads, increasing retrieval latency and sequencing cost. We study the coverage-depth problem for full-message recovery in distributed DNA storage under noiseless uniform sampling, where strands are partitioned among $M$ containers and one strand is independently sampled with replacement from each container per round. For arbitrary linear codes and ordered partitions, we derive exact formulas for the recovery-time distribution and expectation. We prove that MDS codes, whenever they exist, are optimal for every fixed partition, and establish a universal lower bound on the expected total read cost together with its equality conditions. For MDS codes, we identify container-size regimes that yield genuine savings in total reads and regimes that provide only parallelism without changing the asymptotic sequencing cost. For simplex codes, we prove that the $q$-ary simplex code is, up to isomorphism, the unique single-container minimizer among codes with the same parameters, resolving a recent conjecture by Bertuzzo, Ravagnani, and Yaakobi. We further construct a partition attaining the minimum total read cost and derive bounds for intermediate and balanced partitions. These results clarify when distributed sampling reduces latency alone and when it also reduces sequencing cost.

I. INTRODUCTION

Random sampling makes repeated reads unavoidable in DNA storage, so distributed full-message recovery must be evaluated by both recovery latency and total reads. This paper analyzes how code structure and container layout affect those costs.

I. INTRODUCTION

  • Repeated reads can leave designed strands unseen, making the number of reads exceed the information-strand count and linking coverage depth to sequencing cost and recovery latency.Coverage depth is the number of reads normalized by the number of designed strands.Source: §I · p. 1

A. Related Work

  • Earlier work established MDS optimality for single-container recovery, while the simplex-code minimization conjecture is resolved here with a uniqueness statement.Prior work also studied random-access objectives, whose code optimality need not match that of full-message recovery.Source: §I · p. 2, A. Related Work · p. 2

B. Distributed Full-Message Recovery

  • Full-message recovery asks whether observed coded strands jointly span the message space, unlike failed-container recovery, which asks whether a missing block is determined by surviving containers.The full-message objective remains necessary even when no container has failed.Source: B. Distributed Full-Message Recovery · p. 2
  • The model samples one strand independently and uniformly with replacement from each container per round, tracking both expected rounds and expected total reads.These metrics are E[τ(G, P)] and M E[τ(G, P)], respectively.Source: B. Distributed Full-Message Recovery · p. 3

C. Main Contributions

  • For arbitrary linear codes and ordered partitions, the paper derives an exact expected-recovery-time formula; whenever they exist, MDS codes are optimal for every fixed partition.The work also gives a general lower bound and characterizes when recovery takes one round almost surely.Source: C. Main Contributions · p. 3
  • For MDS codes, constant-size balanced containers can reduce total reads, whereas containers of size k^ε provide parallel access without changing asymptotic sequencing cost.The paper also identifies parameter regimes where recovery time concentrates on an integer.Source: C. Main Contributions · p. 3
  • For simplex codes, the q-ary simplex code uniquely minimizes single-container coverage depth up to isomorphism, and an explicit k-partition attains minimum total reads.For intermediate container counts, the paper establishes no-saving results under specified divisibility and parameter conditions.Source: C. Main Contributions · p. 3
  • Whether distribution reduces total-read overhead or only latency depends on the code’s rank geometry and the combinatorial structure of the layout.The paper distinguishes architectural parallelism from read savings that require layouts to suppress repeated or rank-deficient observations.Source: C. Main Contributions · p. 3

B. Exact Formulas for Distributed Coverage Depth

The section expresses expected distributed recovery time through the subspaces that sampled columns can occupy. Its analysis follows the evolving span and uses subspace probabilities to characterize the stopping time.

B. Exact Formulas for Distributed Coverage Depth

  • The exact expectation formula is derived using Möbius inversion and probabilities that each round’s sampled columns lie within a subspace.For a subspace U, ρ_U is the probability that all M samples in one round lie in U.Source: B. Exact Formulas for Distributed… · pp. 5–6
  • The sampled span forms a chain of strictly increasing subspaces until it reaches the full message space, with at most k strict increases.The holding time at a current span is the number of rounds before the sampled span leaves it.Source: B. Exact Formulas for Distributed… · p. 6
  • Recovery has not occurred by round t exactly when the columns observed by then fail to span the full space; subspace probabilities yield the stopping-time tail.Independence across rounds gives the probability that all observations through round t lie in a fixed subspace U as ρ_U^t.Source: B. Exact Formulas for Distributed… · p. 7
  • With one container, the span dimension increases by at most one per round, so the chain has exactly k dimension-increasing stages.The section then states a single-container corollary for the expectation.Source: B. Exact Formulas for Distributed… · p. 7

C. The Optimality of MDS Codes in Distributed Model

MDS codes are optimal for every fixed partition in the distributed model, while general linear codes obey a universal recovery-time lower bound. At M=k, a staircase partition attains that bound, though its container sizes can be highly unequal.

C. The Optimality of MDS Codes in Distributed Model

D. General Lower Bounds on E[τ(G, P)] and One-Round-Perfect Layouts

III. DISTRIBUTED COVERAGE DEPTH PROBLEM OF MDS CODES

The MDS-code results recast distributed recovery as a coupon-collector variant and identify when partitioning strands cuts total sequencing cost. Savings depend on the parameters: some regimes save reads, while others mainly provide parallel access.

III. DISTRIBUTED COVERAGE DEPTH PROBLEM OF MDS CODES

  • For MDS codes, recovery is the number of rounds until k distinct strands are collected under independent uniform sampling from each container.Source: §III · pp. 10–11
  • Every partition of an [n, k] MDS code into k nonempty parts is one-round-perfect and yields the full saving.Any k MDS code symbols recover the k information symbols.Source: §III · p. 11
  • When n ≥ (k+2)(k−1)/2, the full saving is at most one.Source: §III · p. 11
  • When n=ck for fixed c>1, O_v(C) grows linearly with k, saving a constant fraction of all reads.Source: §III · p. 11
  • Figure 1b’s probability difference is nonnegative and peaks near Mt/n ≈ 1.750, where sequencing stop decisions occur.In Figure 1a, multi-container curves are steeper as M increases, consistent with suppression of part of the coupon-collector tail.Source: Figure 1 · p. 12, §III · p. 12

A. Constant Container Size

For balanced MDS layouts, fixed-size containers can reduce total reads in specified regimes, while containers of size k^ε provide parallel access without changing asymptotic read cost.

A. Constant Container Size

  • With constant container size s, the expected recovery time is r + o(1) in the stated parameter regime.Here r is the first round when the expected number of distinct observed columns exceeds k by a linear margin; each round reads from all Mk containers.Source: A. Constant Container Size · pp. 12–13
  • MkE[τk] is strictly smaller than E[Ck] for sufficiently large k in the stated constant-container regime.The saving is a constant fraction of the single-container read cost, bounded above by 0.2787 for s = 2, 0.1779 for s = 3, and 0.1310 for s = 4; it tends to zero as s grows.Source: A. Constant Container Size · p. 14

B. Polynomial Container Size

  • For polynomial-size containers, the analysis uses negative association to derive the asymptotic recovery-time and total-read formulas.The containers are balanced and each has size k^ε for fixed 0 < ε < 1.Source: B. Polynomial Container Size · pp. 14, 16
  • When each container holds k^ε strands for fixed 0 < ε < 1, the distributed and single-container expected read costs have ratio tending to 1.This regime provides parallel access without an asymptotic increase in total reads.Source: B. Polynomial Container Size · pp. 14, 16

C. Low-Rate Obstructions

In the low-rate setting considered here, two containers do not reduce expected total reads; finite higher-rate examples show that this obstruction is not universal.

C. Low-Rate Obstructions

  • For M = 2, the distributed model offers no total-read savings in the low-rate regime described in the section.The stated obstruction includes [n, k] MDS codes with k ≥ 3 in the theorem’s specified cases.Source: C. Low-Rate Obstructions · p. 17
  • Three exact finite-parameter examples show strict savings for higher-rate MDS codes under a balanced two-container layout.These examples are presented as a contrast to the low-rate obstruction.Source: C. Low-Rate Obstructions · p. 18

IV. DISTRIBUTED COVERAGE DEPTH PROBLEM OF SIMPLEX CODES

This section studies simplex codes under distributed sampling, first establishing their single-container optimality and then examining distributed partitions.

IV. DISTRIBUTED COVERAGE DEPTH PROBLEM OF SIMPLEX CODES

  • The q-ary simplex code is, up to isomorphism, optimal for single-container coverage depth, resolving the conjecture of Bertuzzo, Ravagnani, and Yaakobi [20].The section also studies distributed optimality for staircase partitions and asymptotic coverage depth for randomly balanced partitions.Source: §IV · p. 18
  • The section uses the standard normalized simplex generator matrix, whose columns represent projective points with first nonzero coordinate equal to 1..Source: §IV · p. 18

A. Optimality of Simplex Codes in the Single-Container Model

In the single-container model, the q-ary simplex code uniquely minimizes coverage depth, up to isomorphism, among linear codes with the same length and dimension.

A. Optimality of Simplex Codes in the Single-Container Model

  • For any spanning column law π, the expected mass assigned to a random i-dimensional subspace is at least [i]q/[k]q, with equality at every i only for the uniform law.The simplex code has uniform column law because each projective point appears exactly once as a column.Source: A. Optimality of Simplex Codes in the… · p. 18
  • The result resolves the single-container optimality conjecture of Bertuzzo, Ravagnani, and Yaakobi [20].The paper derives the bound for arbitrary probability laws on projective points, not only for a particular code family.Source: A. Optimality of Simplex Codes in the… · p. 19
  • The q-ary simplex code is the unique, up to isomorphism, minimizer of single-container coverage depth among length-[k]q, dimension-k linear codes.Equality in the coverage-depth bound holds if and only if the column law is uniform.Source: A. Optimality of Simplex Codes in the… · p. 19

B. Full Saving for M = k and No-Saving Obstructions for M < k

For simplex codes, distributing strands among k containers can attain the minimum total read cost, while integrality bounds rule out savings for many intermediate container counts.

B. Full Saving for M = k and No-Saving Obstructions for M < k

  • The simplex-code overhead over k is bounded independently of dimension, by about 1.61 for q = 2 and less than 1 for q ≥ 3.Thus the rounding obstruction alone rules out savings whenever M⌈k/M⌉ exceeds k.Source: B. Full Saving for M = k and No-Saving… · p. 21
  • The minimum expected total reads over partitions is k, attained by the explicit k-container partition for every q-ary simplex code.The construction is one-round-perfect: recovery occurs after one round almost surely.Source: B. Full Saving for M = k and No-Saving… · pp. 20–21
  • For 1 < M < k, the lower bound M⌈k/M⌉ rules out savings when M divides neither k nor k + 1, and also when M divides k + 1 with q ≥ 3 or k = 3.In those cases the bound exceeds the single-container depth.Source: B. Full Saving for M = k and No-Saving… · p. 21

C. Distributed Coverage Depth under Balanced Partitions

Balanced simplex-code layouts have an O(M) total-read overhead that does not grow with dimension, and their asymptotic recovery time includes a residue-dependent correction. The paper also identifies when distribution saves total reads and which layout questions remain open.

C. Distributed Coverage Depth under Balanced Partitions

  • For fixed M, the total-read overhead of an arbitrary balanced simplex-code layout is O(M) uniformly in k, and this bound does not establish savings over one container.Balanced partitions exist only for admissible dimensions satisfying M | [k]q.Source: C. Distributed Coverage Depth under… · pp. 21–22
  • As k grows through admissible dimensions, the average balanced recovery time is k + δq + γM(k) + o(1), with γM(k) asymptotically periodic in k modulo M.The correction γM(k) is defined using the least nonnegative residue of −τsimp,k modulo M.Source: C. Distributed Coverage Depth under… · p. 22

V. CONCLUSION AND OPEN PROBLEMS

  • For MDS codes, constant-size balanced containers can reduce total reads, whereas polynomial-size containers provide parallel access without changing asymptotic sequencing cost.The reported gains depend jointly on code rate and container scaling.Source: §V · p. 23
  • The paper resolves a simplex-code conjecture and gives an optimal k-container layout, but structural characterization of optimal balanced layouts for general codes remains open.It also identifies optimal codes over small fields without available MDS codes as an open problem.Source: §V · p. 23

APPENDIX A ONE-ROUND-PERFECT CONSTRUCTIONS AND EXAMPLES

The appendix gives one-round-perfect constructions and examples across several code families, alongside MDS savings examples and simplex-code cases where two containers cannot reduce total reads.

APPENDIX A ONE-ROUND-PERFECT CONSTRUCTIONS AND EXAMPLES

  • A sufficient parity-check condition constructs one-round-perfect layouts, and it yields an explicit one-round-perfect layout for every stated q-ary Hamming code.The condition is not necessary: RM(1,3) has a one-round-perfect 4-partition despite lacking the specified 5-subset.Source: Appendix A · p. 24
  • The first-order Reed–Muller code has an affine staircase partition that is one-round-perfect.Its parts are organized by the first nonzero coordinate, and the sampled columns span in one round.Source: Appendix A · pp. 24–25

B. Balanced Two-Container MDS Examples with Reduced Total Reads

  • Three Reed–Solomon-realizable parameter sets give balanced two-container MDS layouts with fewer expected total reads than the single-container case.For n = 8, k = 4, the distributed recovery time is 53/21, below the single-container value 533/105.Source: B. Balanced Two-Container MDS Examples… · p. 25

APPENDIX C EXCEPTIONAL TWO-CONTAINER CASES FOR SIMPLEX CODES

  • For simplex codes with (q, k) = (2, 5) or (3, 4), every two-partition has greater expected total reads than the single-container model.These cases address parameter regimes left open by the general integrality obstruction.Source: Appendix C · p. 26

7. Recall that P

The passage gives an average-mass calculation for a family of hyperplanes and applies an earlier inequality to it.

7. Recall that P

  • The average mass of the remaining thirty hyperplanes is 23/105, and this value is used with inequality (50).The subsequent displayed numerical expression does not support a clear additional conclusion.Source: §7 · p. 28

7. Hence,

For the (q, k) = (3, 4) case, the passage gives E[C] = E[T3,4] = 1621/351. The proof separately treats cases according to n1.

  • When n1 = 2, two distinct projective points span a two-dimensional space, which is used to derive the bound E[C]/2 = 3567/1120.Source: §7 · p. 29
  • In Case 2, for (q, k) = (3, 4), the reported setting has n = 40, with E[C] = E[T3,4] = 1621.Source: §7 · p. 29
  • When n1 = 1, τ(Gsimp, P) has the same distribution as Tq,k−1.Source: §7 · p. 29

APPENDIX D PROOF OF THEOREM IV.12

The proof compares the random balanced-partition coverage process with an i.i.d. sampling process and analyzes the single-container coverage time. It establishes an asymptotic period for the rounding term γM(k).

  • Conditioned on all ML sampled columns being distinct, the random balanced process and the i.i.d. process are both uniform over ordered arrays of distinct columns.Source: Appendix D · p. 30
  • Under a balanced partition, collisions can occur only between draws from the same container.Source: Appendix D · p. 30
  • The single-container process is decomposed into k dimension stages, with independent geometric draw counts for the stages.For stage j, the success probability is 1 − [k−j]q/[k]q.Source: Appendix D · p. 31
  • The integer-valued variables Dk converge in distribution to D∞, implying pointwise convergence of their probability mass functions.Source: Appendix D · p. 32
  • The rounding term γM(k) is asymptotically periodic with period M.Source: Appendix D · p. 32
Loading 2610.02931v1…