Skip to main content
Open Access Publications from the University of California


UCLA Electronic Theses and Dissertations bannerUCLA

An Interactive Algorithm for Synchronizing From Burst Deletions


We consider the synchronization between two distant nodes A and B that are connected through a two-way communication channel. Node A contains file X, and node B contains file Y that is generated through i.i.d. deletions from X. In previous work, a deterministic polynomial-time protocol for reconstructing file X at node B is proposed, which has the order-wise optimal rate and exponentially low probability of error.

In this thesis, we consider the case of burst deletions, which is more applicable in practical scenario compared with i.i.d. deletions. In order to model this new deletion pattern, we use a stationary two-state Markov chain. Based on previous protocol, we offer a new synchronization scheme specifically designed for burst deletion pattern. The experimental result shows that our proposed protocol works well.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View