Trace Repair Never Loses to Classical Repair: Exact and Explicit Helper Nodes Selection
Wilton Kim, Stanislav Kruglik, Han Mao Kiah · 2025
Read Trace Repair Never Loses to Classical Repair: Exact and Explicit Helper Nodes Selection by Wilton Kim, Stanislav Kruglik, Han Mao Kiah (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06492.txt.
Introduction
Repairing lost data in storage systems while downloading as little as possible is the topic of a 2025 coding theory paper by Wilton Kim and two co-authors. The work concerns Reed-Solomon codes, a widely used error-correcting scheme. A trace-repair method from 2017 promised low repair bandwidth, meaning the amount of data helpers must send.
Two later improvements are unified here. One skips a chosen set of helper nodes entirely; the other exploits repeated patterns among downloaded traces. The authors compute the exact size of a key subspace, map the trade-off between skipping nodes and those repeats, and give an algorithm that picks the cheapest mix. They also name the helper nodes explicitly. A proof shows the tuned scheme never does worse than classic repair, with a firm bandwidth cap whenever trace repair applies.
Catalog record
| CREATOR | Wilton Kim, Stanislav Kruglik, Han Mao Kiah |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-06492
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Trace Repair Never Loses to Classical Repair: Exact and Explicit Helper Nodes Selection Wilton Kim, Stanislav Kruglik, Han Mao Kiah Abstract We study the repair of Reed–Solomon codes over 𝔽 = 𝔹 t \mathbb{F}=\mathbb{B}^{t} using traces over 𝔹 \mathbb{B} . Building on the trace framework of Guruswami–Wootters (2017), recent work of Liu–Wan–Xing (2024) reduced repair bandwidth by studying a related subspace 𝒲 k \mathcal{W}_{k} . In this work, we determine the dimension of 𝒲 k \mathcal{W}_{k} exactly using cyclotomic cosets and provide an explicit set of helper nodes that attains bandwidth ( n − d − 1 ) log | 𝔹 | (n-d-1)\log|\mathbb{B}| bits with d = dim ( 𝒲 k ) d=\dim(\mathcal{W}_{k}) . Moreover, we show that ( n − d − 1 ) ≤ k t (n-d-1)\leq kt , and so, trace repair never loses to the classical repair. I Introduction Reed-Solomon (RS) codes [ 17 ] are widely used in distributed storage because all information symbols can be recovered by downloading any k available code symbols (see [ 8 ] for a survey). More precisely, let \mathbb{F}={\mathrm{GF}}(p^{mt}) and let \mathcal{A}=\{\alpha_{1},\ldots,\alpha_{n}\}\subseteq\mathbb{F} be n distinct evaluation points. Given k information symbols in \mathbb{F} , we encode them as a polynomial f of degree at most k-1 and store \boldsymbol{c}=(f(\alpha))_{\alpha\in\mathcal{A}} . The MDS property then states that any k coordinates of \boldsymbol{c} uniquely determine f and hence \boldsymbol{x} . Equivalently, at most n-k erasures can be corrected by downloading any k surviving code symbols. In this paper we call this the classical repair scheme. Its bandwidth is k\log|\mathbb{F}| bits, since each downloaded symbol lies in \mathbb{F} . In [ 10 ] , Guruswami and Wootters proposed a repair scheme for a single erased code symbol f(\alpha^{*}) by utilizing the trace function {\rm Tr}:\mathbb{F}\to\mathbb{B} for some base field \mathbb{B}={\mathrm{GF}}(p^{m}) . Specifically, we download n-1 traces of the form ({\rm Tr}(\lambda_{\alpha}f(\alpha)/(\alpha-\alpha^{*})))_{\alpha\in\mathcal{A}\setminus\{\alpha^{*}\}} for some \lambda_{\alpha}\in\mathbb{F} . This then results in a bandwidth of (n-1)\log|\mathbb{B}| bits. In terms of bandwidth, the Guruswami-Wootters scheme outperforms the classical scheme only when k>(n-1)/t . There is a flurry of works utilizing the Guruswami-Wootters scheme in different setups [ 9 , 4 , 3 , 16 , 19 , 2 , 14 , 6 , 1 , 11 , 7 , 12 , 13 ] . However, whether there exists a repair scheme that improves upon the classical repair scheme for all values of k\leq(n-1)/t remains open. Progress towards this was made recently by Liu et al. [ 15 ] , where they lowered the repair bandwidth by omitting d helper nodes from the repair process. Specifically, they related the number d to the dimension of a subspace \mathcal{W}_{k} (see Theorem 1 for the exact statement) and in the same paper, provided lower bounds on \dim(\mathcal{W}_{k}) . In this work we determine \dim(\mathcal{W}_{k}) exactly and, as a consequence, obtain a tighter bandwidth guarantee together with an explicit choice of the d omitted helpers. Interestingly, the bandwidth of the resulting trace repair scheme is at most the bandwidth of classic repair for all k . We summarize our contributions as follows. • We determine the exact value of \dim(\mathcal{W}_{k}) (Theorem 5 ), yielding an improved bandwidth guarantee as compared to [ 15 ] . • We provide an explicit set of helper nodes that attains this bandwidth (Corollary 6 ). • We prove that trace-based repair never loses to the classical scheme in terms of bandwidth (Theorem 7 ). In Fig 1 , we provide a comparison of bandwidths with existing works when \mathbb{F}={\mathrm{GF}}(8^{2}) and \mathbb{B}={\mathrm{GF}}(8) . We see that our work improves the bandwidth for all values k\in\{1,\ldots,56\} . Nevertheless, there remains a gap to to the lower bound given in [ 5 ] . Fig. 1: Comparison of bandwidths (in number of elements in \mathbb{B} ) with existing works when \mathbb{F}={\mathrm{GF}}(8^{2}) and \mathbb{B}={\mathrm{GF}}(8) . II Preliminaries Let [n] denote the set \{1,2,\ldots,n\} and [a,b] denote the set \{a,a+1,\ldots,b\} . Let \mathbb{B} be the finite field of size q=p^{m} for some prime p and let \mathbb{F} be its extension field of degree t\geq 1 . Let \{u_{1},\ldots,u_{t}\} be a basis of \mathbb{F} over \mathbb{B} . We use \mathbb{F}[x] to denote the ring of polynomials over the finite field \mathbb{F} . We denote the dual of the code \mathcal{C} by \mathcal{C}^{\perp} , and so, for each \boldsymbol{c}=(c_{1},\ldots,c_{n})\in\mathcal{C} and \boldsymbol{c}^{\perp}=(c_{1}^{\perp},\ldots,c_{n}^{\perp})\in\mathcal{C}^{\perp} , it holds that \sum_{i=1}^{n}c_{i}c_{i}^{\perp}=0 . In this work, we focus on the ubiquitous Reed-Solomon code. Definition 1 . The Reed-Solomon code {\rm RS}(\mathcal{A},k) over finite field \mathbb{F} of dimension k with evaluation points \mathcal{A}\subseteq\mathbb{F} is defined as {\rm RS}(\mathcal{A},k)\triangleq\{(f(\alpha))_{\alpha\in\mathcal{A}}:f\in\mathbb{F}[x],\deg(f)\leq k-1\}, while the generalized Reed-Solomon code {\rm GRS}(\mathcal{A},k,\boldsymbol{\lambda}) of dimension k with evaluation points \mathcal{A}\subseteq\mathbb{F} and multiplier vector \boldsymbol{\lambda}\in(\mathbb{F}\setminus\{0\})^{n} is defined as: {\rm GRS}(\mathcal{A},k,\boldsymbol{\lambda})\triangleq\{(\lambda_{\alpha}r(\alpha))_{\alpha\in\mathcal{A}}:r\in\mathbb{F}[x],\deg(r)\leq k-1\}. It is well known (see [ 18 ] ) that dual of {\rm RS}(\mathcal{A},k) is {\rm GRS}(\mathcal{A},|\mathcal{A}|-k,{\boldsymbol{\lambda}}) for some {\boldsymbol{\lambda}}=(\lambda_{\alpha})_{\alpha\in\mathcal{A}} . Furthermore, when \mathcal{A}=\mathbb{F} , we have \lambda_{\alpha}=1 for all \alpha\in\mathcal{A} . Recently, Liu et al. [ 15 ] proposed a repair scheme for an erased Reed-Solomon code symbol without involving all available nodes. In the special case for the trace repair scheme, there exists a set \mathcal{I}\subseteq\mathcal{A} , so that, by downloading {\rm Tr}(\lambda_{\alpha}f(\alpha)/(\alpha-\alpha^{*})) for all \alpha\in\mathcal{A}\setminus(\mathcal{I}\cup\{\alpha^{*}\}) , we can recover {\rm Tr}(\lambda_{\alpha}f(\alpha)/(\alpha-\alpha^{*})) for all \alpha\in\mathcal{I} . It can be done by forming new parity-check polynomials to repair traces that we do not download. After we obtain all required traces, we apply the Guruswami-Wootters scheme to repair the erased node. This results in a bandwidth of (|\mathcal{A}|-|\mathcal{I}|-1)\log|\mathbb{B}| bits. In what follows, for simplicity and without loss of generality, we assume that f(0) is erased and we restate this special case of Liu et al. [ 15 ] in Theorem 1 . Theorem 1 (Liu et al. [ 15 ] ) . Let n=|\mathcal{A}| and fix k . Let {\cal Y}=\{(0,y_{1},\ldots,y_{n-1}):y_{i}\in\frac{1}{\alpha_{i}}\mathbb{B}\} and {\cal W}_{k}={\rm RS}(\mathcal{A},k)^{\perp}\cap\mathcal{Y}. If \dim({\cal W}_{k})\geq d , then we can repair f(0) with bandwidth of (n-d-1)\log|\mathbb{B}| bits. In the same work, Liu et al. provided lower bounds for \dim(\mathcal{W}_{k}) in two settings: namely, \mathbb{F}={\mathrm{GF}}(p^{2}) with \mathbb{B}={\mathrm{GF}}(p) ; and \mathbb{F}={\mathrm{GF}}(2^{s}) with \mathbb{B}={\mathrm{GF}}(2^{s/2}) for even s\geq 2 . In this work we study arbitrary finite fields and, crucially, determine the exact value of \dim(\mathcal{W}_{k}) using cyclotomic cosets. III Main Result Let us first formulate our problem. Let \mathcal{A}=\mathbb{F}={\mathrm{GF}}(q^{t}) and n=|\mathbb{F}| . Let \omega be the primitive element of \mathbb{F} . Consider the codeword (f(\alpha))_{\alpha\in\mathcal{A}}\in{\rm RS}(\mathcal{A},k) where f(0) is erased. Let \mathcal{W}_{k} be as defined in Theorem 1 . Our goal is to determine \dim(\mathcal{W}_{k}) exactly, and to identify the helper nodes to download from. We need the following terminology to achieve our result. Definition 2 . Fix t and q=p^{m} . A subset \{a_{1},\ldots,a_{s}\}\subset\{0,1,\ldots,q^{t}-2\} is called a cyclotomic coset if qa_{j}=a_{j+1}(\text{mod }q^{t}-1) for all j\in\{1,\ldots,s-1\} and qa_{s}=a_{1}(\text{mod }q^{t}-1) . The collection of all such cosets partitions \{0,1,\ldots,q^{t}-2\} and we refer to it as the collection of cyclotomic cosets modulo q^{t}-2 . Example 3 . Suppose q=3 and t=2 . Then, the collection of cyclotomic cosets of \{0,1,\ldots,7\} is \{\{0\},\{1,3\},\{2,6\},\{4\},\{5,7\}\} . In this work, we use C_{i}=\{a^{(i)},a^{(i)}q,\ldots,a^{(i)}q^{s_{i}-1}\} to denote the i -th cyclotomic coset in its collection \Xi . It is clear that |C_{i}|\leq t . Suppose that there is an element