Abstract-This paper tar upp problemet med synkronisering av två fjärrbaserade datakällor, som är felsynkroniserade på grund av raderingar, tillägg och substitutioner (kollektivt kallade 'editer'). Vi fokuserar på följande modell. Det finns två avlägsna noder, med en med en binär sekvens X, och den andra med Y. Y är en redigerad version av X, där redigeringen innebär slumpmässiga raderingar, tillägg och substitutioner, möjligen i sprickor. Problemet är att synkronisera Y med X med minimalt utbyte av information över en ljudlös länk. Mängden information som utbyts mäts både i fråga om den genomsnittliga kommunikationshastigheten och det genomsnittliga antalet interaktiva kommunikationsrundor. Målet är att synkronisera Y till X, antingen exakt eller inom ett mål Hamming avstånd. Vi bygger på tidigare arbete [1] som introducerade en interaktiv algoritm baserad på Varshamov-Tenengolts koder för att synkronisera från införande och radering redigerar (indels). Antagandet är att antalet redigeringar är litet (o(n) där n är filstorleken). För det första visar vi hur den ursprungliga algoritmen kan modifieras för att fungera med ett begränsat antal rundor, och kvantifiera avvägningen mellan antalet rundor och kommunikationshastigheten. Därefter presenterar vi en förlängning av algoritmen för att hantera det praktiskt taget viktiga fallet där tillägg och raderingar sker i (potentiellt stora) sprickor. Slutligen visar vi hur man synkroniserar källorna till inom ett mål Hamming avstånd. Denna funktion kan användas för att skilja mellan substitution och indelredigeringar.
I REF infördes en interaktiv synkroniseringsalgoritm som korrigerar slumpmässiga tillägg, raderingar och substitutioner i binärt alfabet, där n representerar filstorleken.
Efficient interactive algorithms for file synchronization under general edits
{'venue': '2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton)', 'journal': '2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton)', 'mag_field_of_study': ['Computer Science']}