TU Berlin

Internet Network ArchitecturesPublications by Type: Articles


zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Journal and Magazine Articles

Bandwidth Efficient String Reconciliation Using Puzzles
Zitatschlüssel ACT-BESRUP-06
Autor Agarwal, Sachin and Chauhan, Vikas and Trachtenberg, Ari
Seiten 1217–1225
Jahr 2006
ISSN 1045-9219
DOI http://dx.doi.org/10.1109/TPDS.2006.148
Journal IEEE Transactions on Parallel and Distributed Systems
Jahrgang 17
Nummer 11
Monat November
Zusammenfassung Of considerable interest in recent years has been the problem of exchanging correlated data with minimum communication. We thus consider the problem of exchanging two similar strings held by different hosts. Our approach involves transforming a string into a multiset of substrings that are reconciled efficiently using known multiset reconciliation algorithms, and then put back together on a remote host using tools from graph theory. We present analyses, experiments, and results to show that the communication complexity of our approach for high-entropy data compares favorably to existing algorithms including rsync, a widely-used string reconciliation engine. We also quantify the trade-off between communication and the computation complexity of our approach.
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe