Prioritized data synchronization with applications
OA Version
Citation
Abstract
We are interested on the problem of synchronizing data on two distinct devices
with differed priorities using minimum communication. A variety of distributed sys-
tems require communication efficient and prioritized synchronization, for example,
where the bandwidth is limited or certain information is more time sensitive than
others. Our particular approach, P-CPI, involving the interactive synchronization of
prioritized data, is efficient both in communication and computation. This protocol
sports some desirable features, including (i) communication and computational com-
plexity primarily tied to the number of di erences between the hosts rather than the
amount of the data overall and (ii) a memoryless fast restart after interruption. We
provide a novel analysis of this protocol, with proved high-probability performance
bound and fast-restart in logarithmic time. We also provide an empirical model
for predicting the probability of complete synchronization as a function of time and
symmetric differences.
We then consider two applications of our core algorithm. The first is a string
reconciliation protocol, for which we propose a novel algorithm with online time com-
plexity that is linear in the size of the string. Our experimental results show that
our string reconciliation protocol can potentially outperform existing synchroniza-
tion tools such like rsync in some cases. We also look into the benefit brought by
our algorithm to delay-tolerant networks(DTNs). We propose an optimized DTN
routing protocol with P-CPI implemented as middleware. As a proof of concept, we
demonstrate improved delivery rate, reduced metadata and reduced average delay.