  Consider two remote nodes having binary sequences $X$ and $Y$, respectively.
$Y$ is an edited version of ${X}$, where the editing involves random deletions,
insertions, and substitutions, possibly in bursts. The goal is for the node
with $Y$ to reconstruct $X$ with minimal exchange of information over a
noiseless link. The communication is measured in terms of both the total number
of bits exchanged and the number of interactive rounds of communication.
  This paper focuses on the setting where the number of edits is
$o(\tfrac{n}{\log n})$, where $n$ is the length of $X$. We first consider the
case where the edits are a mixture of insertions and deletions (indels), and
propose an interactive synchronization algorithm with near-optimal
communication rate and average computational complexity of $O(n)$ arithmetic
operations. The algorithm uses interaction to efficiently split the source
sequence into substrings containing exactly one deletion or insertion. Each of
these substrings is then synchronized using an optimal one-way synchronization
code based on the single-deletion correcting channel codes of Varshamov and
Tenengolts (VT codes).
  We then build on this synchronization algorithm in three different ways.
First, it is modified to work with a single round of interaction. The reduction
in the number of rounds comes at the expense of higher communication, which is
quantified. Next, we present an extension to the practically important case
where the insertions and deletions may occur in (potentially large) bursts.
Finally, we show how to synchronize the sources to within a target Hamming
distance. This feature can be used to differentiate between substitution and
indel edits. In addition to theoretical performance bounds, we provide several
validating simulation results for the proposed algorithms.
