Efficient point-to-multipoint data reconciliation

Details Efficient point-to-multipoint data reconciliation Efficient point-to-multipoint data reconciliation

2011-07-19

2011-07-19

Vo, Tim T. (Department: 2168)

Data processing: database and file management or data structures

File or database maintenance

Synchronization

C707S624000, C707S634000, C711S216000

Reexamination Certificate

active

07984018

ABSTRACT:
Efficient reconciliation of different versions of a target file or dataset can be facilitated using a hash hierarchy of a master version of the dataset. Each level of the hash hierarchy has hashes of blocks of the master version that may be sub-blocks of the hashes in the level above. The top level of the hash hierarchy, having the hashes of the largest blocks of the master, may be transmitted on a first communication channel, possibly a one-way or broadcast communication channel. Streams of encodings of each lower level of the hash hierarchy may be transmitted on respective communication channels. The encodings for a level of the hierarchy may be combinations, such as random linear combinations, of the hashes of that level. A receiver with a target dataset can receive the top level hashes from the first channel and use them to determine which lower hashes are needed to identify parts of the master missing from the target. The encodings can be used to help obtain needed lower level hashes that can be used to more finely identify missing parts. Different receivers may not have to wait for a particular piece of information about the master. Rather, any received information (e.g. encoding) about the master will most likely allow any receiver to advance its understanding of the master dataset. Receivers will usually not have to wait for delivery of a particular hash in the hierarchy.

REFERENCES:
patent: 4538240 (1985-08-01), Carter et al.
patent: 5199073 (1993-03-01), Scott
patent: 5390187 (1995-02-01), Stallmo
patent: 5475826 (1995-12-01), Fischer
patent: 5530757 (1996-06-01), Krawczyk
patent: 5694569 (1997-12-01), Fischer
patent: 5701418 (1997-12-01), Luitje
patent: 5909700 (1999-06-01), Bitner et al.
patent: 6148382 (2000-11-01), Bitner et al.
patent: 6202135 (2001-03-01), Kedem et al.
patent: 6233589 (2001-05-01), Balcha et al.
patent: 6397309 (2002-05-01), Kedem et al.
patent: 6850969 (2005-02-01), Ladan-Mozes et al.
patent: 2001/0037323 (2001-11-01), Moulton et al.
patent: 2001/0042222 (2001-11-01), Kedem et al.
patent: 2002/0055991 (2002-05-01), Arrouye et al.
patent: 2003/0182568 (2003-09-01), Snapp et al.
patent: 2003/0217058 (2003-11-01), Ladan-Mozes et al.
“Low cost comparisons of file copies”; Schwarz, T.; Bowdidge, R.W.; Burkhard, W.A.;Distributed Computing Systems, 1990. Proceedings., 10th International Conference on May 28-Jun. 1, 1990 pp. 196-202; Digital Object Identifier 10.1109/ICDCS.1990.89272.
“Multilevel error-control codes for data storage channels”; Abdel-Ghaffar, K.A.S.; Hassner, M.; Information Theory, IEEE Transactions on vol. 37, Issue 3, Part 2, May 1991 pp. 735-741; Digital Object Identifier 10.1109/18.79944.
“Software-based erasure codes for scalable distributed storage”; Cooley, J.A.; Mineweaser, J.L.; Servi, L.D.; Tsung, E.T.;Mass Storage Systems and Technologies, 2003. (MSST 2003). Proceedings. 20th IEEE/11th NASA Goddard Conference on Apr. 7-10, 2003 pp. 157-164.
“Improved single-round protocols for remote file synchronization”; Irmak, U.; Mihaylov, S.; Suel, T.;INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE vol. 3, Mar. 13-17, 2005 pp. 1665-1676 vol. 3; Digital Object Identifier 10.1109/INFCOM.2005.1498448.
“Shift-register synthesis and BCH decoding”; Massey, J.; Information Theory, IEEE Transactions on vol. 15, Issue 1, Jan. 1969 pp. 122-127.
Julian Chesterfield and Pablo Rodriguez; “DeltaCast: Efficient File Reconciliation in Wireless Broadcast Systems” Jun. 2005—Proceedings of the Third International Conference on Mobile Systems, Applications, and Services (MobiSys 2005) (1931971315); Berkley, CA; Seattle, WA USA; 14 pages.
Q. L. Hu, D.L. Lee, and W.C. Lee; Performance evaluation of a wireless hierarchical data dissemination system., In Proceedings of the 5th Annual ACM International Conference on Mobile Computing and Networking (MobiCom99), Seattle, WA, Aug. 1999.
S. Acharya, R. Alonso, M. Franklin, and S. Zdonik. Broadcast disks: Data management for asymmetric communications environments., In Proceeding of ACM SIGMOD Conference on Management of Data, San Jose, CA, May 1995.
T. Imielinski, S. Viswanathan, and B.R. Badrinath. Data on air Organization and access., IEEE Transactions on Knowledge and Data Engineering (TKDE), May/Jun. 1997.
StarBand., http://www.starband.com/.
Hughes Network Systems., http://www.direcway.com/.
Multimedia Broadcast/Multicast System (MBMS), http://www.3gpp2.org/ftp/Specs/html-info/29846.htm.
Broadcast and Multicast Service in cdma2000 Wireless IP Network., http://www.3gpp2.org/, Oct. 2003.
Digital Audio and Video Broadcasting systems, http://www.etsi.org/.
First UK user trial of multi-channel TV to mobile phones, Nokia Press Release, IBC Amsterdam, 2004.
DirectBand Network. Microsoft Smart Personal Objects Technology (SPOT). http://www.microsoft.com/resources/spot/.
A. Tridgell and P. MacKerras, The rsync algorithm, Technical Report TR-CS-96-05, Australian National University, Jun. 1996.
N. Baric and B. Pfitzmann, Collision-free accumulators and fail-stop signature schemes without trees, Advance in Cryptology, EUROCRYPT 97, 1997.
M. Bellare and D. Micciancio, A new paradigm for collision-free hashing: Incrementality at reduced cost, Advances in Cryptology, EUROCRYPT 97, 1997.
R. Johnson, D. Molnar, D. Song, and D. Wagner, Homomorphic signature schemes, Progress in Cryptology CT-RSA 2002, 2002.
T. Schwarz, R., Bowdidge, and W. Burkhard, Low cost comparison of File copies, Proc. of the 10th Int. Conf. on Distributed Computing Systems, 1990, pp. 196202.
Zdelta Home Page, http://cis.poly.edu/zdelta/.
J. Byers and J. Considine, Informed Content Delivery Across Adaptive Overlay Networks, Proc. of ACM SIGCOMM, Aug. 2002.
G. Cormode, M. Paterson, S. Sahinalp, and U. Vishkin, Communication complexity of document exchange, Proc. of the ACM-SIAM Symp. on Discrete Algorithms, Jan. 2000.
G. Cormode, Sequence Distance Embeddings, Ph.D thesis, University of Warwick, Jan. 2003.
A. Orlitsky, Interactive communication of balanced distributions and of correlated files, SIAM Journal of Discrete Math, vol. 6, No. 4. pp. 548564, 1993.
A. Orlitsky, Worst-case interactive communication II: Two messages are not optimal, IEEE Transactions on Information Theory, vol. 37, No. 4, pp. 9951005, Jul. 1991.
A. Orlitsky and K. Viswanathan, One-way communication and error-correcting codes, Proc. of the 2002 IEEE Int. Symp. on Information Theory, Jun. 2002 p. 394.
Y. Minsky, A. Trachtenberg, and R. Zippel, Set reconciliation with almost optimal communication complexity, Technical Report TR2000-1813, Cornell University, 2000.
D. Starobinski, A. Trachtenberg, and S. Agarwal, Efficient PDA synchronization, IEEE Trans. on Mobile Computing, 2003.
S. Agarwal, D. Starobinski, and A. Trachtenberg, On the scalability of data synchronization protocols for PDAs and mobile devices, IEEE Network Magazine, special issue on Scalability in Communication Networks, Jul. 2002.
R. Karp and M. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, vol. 31, No. 2, pp. 249260. 1987.
S. Rhea, K. Liang, and E. Brewer, Value-based web caching, Proc. of the 12th Int. World Wide Web Conference, May 2003.
N. Spring and D. Wetherall, A protocol independent technique for eliminating redundant network traffic, ACM SIGCOMM Conference, 2000.
A. Muthitacharoen, B. Chen, and D. Mazi'eres, A low bandwidth network file system, in Proc. of the 18th ACM Symp. on Operating Systems Principles, Oct. 2001, pp. 174187.
L. Cox, C. Murray, and B. Noble, Pastiche: Making backup cheap and easy, in Proc of the 5th Symp. on Operating Systems Design and Implementation, Dec. 2002.
Byers, John et al., “A Digital Fountain Approach to Reliable Distribution of Bulk Data”, pp. 12.
Bellare, Mihir et al., “A New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost”, pp. 21.
Spring, Neil et al., “A Protocol-Independent Technique for Eliminating Redundant Network Tra

Affiliated with

Also associated with

Rating

Efficient point-to-multipoint data reconciliation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient point-to-multipoint data reconciliation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient point-to-multipoint data reconciliation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2709461