Back to search

Boston University

Prioritized data synchronization with applications

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Master of Science
Level thesis:degree_level
masters
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor
Boston University
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Jin, Jiaxi

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/17152

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Jin, Jiaxi. Prioritized data synchronization with applications. masters thesis, Boston University, 2013. https://hdl.handle.net/2144/17152