A probabilistic algorithm for updating files over a communication link

Autor:	Alexandre V. Evfimievski
Rok vydání:	2000
Předmět:	General Computer Science Stochastic process Probability of error Communication link Telecommunications network Algorithm Computer Science(all) Theoretical Computer Science Randomized algorithm Mathematics Running time
Zdroj:	Theoretical Computer Science. 233:191-199
ISSN:	0304-3975
DOI:	10.1016/s0304-3975(98)00019-x
Popis:	Let P and Q be two parties on either side of a communication link. Assume that P has an old version of some file and wants to get a newer version from Q (who has it). Our algorithm performs this operation using poly(log|x|,log|y|,d(x,y),log(1/ε)) communication bits where x and y are old and new versions, d(x,y) is the number of editing operations needed to transform x into y, and ε is the error probability. The running time is poly(|x|,|y|,log(1/ε)).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bbabe6062b18b577f1718438f969cd7c https://doi.org/10.1016/s0304-3975(98)00019-x Zobrazit plný text záznamu Full Text from ScienceDirect