Name
Title | ||
|---|---|---|
A Single-Round File Synchronization Scheme From Insertions and Deletions With Low Redundancy |
Abstract | ||
|---|---|---|
Consider a file synchronization problem at two remote nodes A and B connected by a noiseless link. The node A has a binary file
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula>
, and node B has a binary file
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$Y$ </tex-math></inline-formula>
which is an edited version of
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula>
with random insertions and deletions (indels). The goal is to reconstruct
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula>
at node B from
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$Y$ </tex-math></inline-formula>
with minimal exchange of information between A and B. In this letter, we design a single-round, thus low latency, file synchronization scheme with low redundancy. In particular, a series of redundancy bits, including markers, check symbols of Reed-Solomon (RS) codes for hashes and Varshamov-Tenengolts (VT) syndromes, are constructed from
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula>
at node A and send to node B. According to the received redundancy and
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$Y$ </tex-math></inline-formula>
, we develop a recovery algorithm at node B to reconstruct
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula>
. The amount of exchanged information of the proposed scheme is significantly reduced when compared with the existing single-round synchronization scheme under random indels. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1109/LCOMM.2022.3193809 | IEEE Communications Letters |
Keywords | DocType | Volume |
File synchronization,insertions and deletions,Reed-Solomon (RS) codes,Varshamov-Tenengolts (VT) codes | Journal | 26 |
Issue | ISSN | Citations |
10 | 1089-7798 | 0 |
PageRank | References | Authors |
0.34 | 10 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guochen Ma | 1 | 1 | 0.70 |
| Xiaopeng Jiao | 2 | 16 | 2.42 |
| Jianjun Mu | 3 | 8 | 3.23 |
| Hui Han | 4 | 0 | 0.34 |
| Yu-Cheng He | 5 | 0 | 0.34 |