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