Coding Methods for Data Synchronization 147 views

As the volume of digital data continues to grow and distributed systems become increasingly ubiquitous, efficient and reliable data synchronization has become a critical challenge. In scenarios where two users or devices each hold a version of the same file, and one of them undergoes a series of edits, it is essential to reconcile the differences with minimal communication overhead. Traditional synchronization methods often fall short in handling edit operations with low redundancy. This dissertation addresses the problem by studying coding-theoretic solutions for synchronization. First, we study codes correcting one substring edit (a burst of edits). We construct codes correcting a substring edit with optimal redundancy. We also propose a file synchronization protocol for a substring edit for any iid distribution with twice of the optimal redundancy. Second, we study local graph coloring codes and its applications in edit-correcting codes. We propose a framework of local graph coloring codes and use it to construct codes correcting a constant number of errors. We also construct list-decodable codes and randomized encoding codes correcting a constant number of errors with redundancy less than twice of the Gilbert-Varshamov bound. We then present an incremental synchronization protocol for edit errors. Moreover, we construct codes correcting multiple substring edits with redundancy twice of the Gilbert-Varshamov bound. Third, we study linear codes that are list decodable for a fraction of edits with rate approaching 1. We construct such codes with reasonable list size and polynomial-time encoders and decoders.

PHD (Doctor of Philosophy)

English

2025-11-18