Fast PDA synchronization using characteristic polynomial interpolation
Proceedings - IEEE INFOCOM - Tập 3 - Trang 1510-1519 vol.3
Tóm tắt
Modern personal digital assistant (PDA) architectures often utilize a wholesale data transfer protocol known as "slow sync" for synchronizing PDAs with personal computers (PCs). This approach is markedly inefficient with respect to bandwidth usage and latency, since the PDA and PC typically share many common records. We propose, analyze, and implement a novel PDA synchronization scheme (CPIsync - characteristic polynomial interpolation-based synchronization) predicated upon recent information-theoretic research. The salient property of this scheme is that its communication complexity depends on the number of differences between the PDA and PC, and is essentially independent of the overall number of records. Moreover, our implementation shows that the computational complexity of CPIsync is practical, and that the overall latency is typically much smaller than that of slow sync. Thus, CPIsync has potential for significantly improving synchronization protocols for PDAs and, more generally, for heterogeneous networks of many machines.
Từ khóa
#Polynomials #Interpolation #Personal digital assistants #Protocols #Delay #Computer architecture #Microcomputers #Personal communication networks #Bandwidth #Information analysisTài liệu tham khảo
ratner, 0, Peer replication with selective control, MDA '99 First International Conference on Mobile Data Access Hong Kong December 1999
10.1145/146941.146942
10.1145/224057.224070
hayden, 1996, Probabilistic broadcast
0, Pilot PRC-Tools
weisberg, 1985, Applied Linear Regression
cormen, 1990, Introduction to Algorithms
shoup, 0, NTL: A library for doing number theory
karpovsky, 2001, Data verification and reconciliation with generalized error-control codes, IEEE Trans on Info Theory
silberschatz, 1999, Database System Concepts
denny, 2000, EDISON: Enhanced data interchange services over networks
10.1109/ICDSC.2001.918981
macwilliams, 1977, The Theory of Error-Correcting Codes
10.1109/18.53757
10.1109/DCS.1988.12550
10.1109/71.89062
fuchs, 1996, Low-cost comparison and diagnosis of large remotely located files, Proceedings of the Symposium on Reliability in Distributed Software and Database Systems, 67
10.1109/TC.1983.1676310
10.1109/71.262591
10.1109/ICDCS.1990.89272
minsky, 0, Set reconciliation with nearly optimal communication complexity, International Symposium on Information Theory June 2001, 232
minsky, 2000, Set reconciliation with nearly optimal communication complexity
10.1109/TIT.2003.813498
0, Palm developer on-line documentation
10.1109/SFCS.1991.185373
van renesse, 0, Captain cook: A scalable navigation service
10.1145/301308.301362
adams, 1987, RFC1036: Standard for interchange of USENET messages
golding, 1992, Weak-consistency group communication and membership
cormode, 0, Communication complexity of document exchange, ACM-SIAM Symposium on Discrete Algorithms January 2000
0, Frontline test equipment
guo, 1997, GSGC: An efficient gossip-style garbage collection scheme for scalable reliable multicast, 10.21236/ADA542422
10.1007/978-1-4471-1283-9_4