Data processing: database and file management or data structures – File or database maintenance – Synchronization
Reexamination Certificate
2008-06-09
2011-10-11
Trujillo, James (Department: 2159)
Data processing: database and file management or data structures
File or database maintenance
Synchronization
Reexamination Certificate
active
08037023
ABSTRACT:
Methods and systems are provided for optimally trading off replication overhead and consistency levels in distributed data replication where nodes are organized in a hierarchy. The root node has the original data that need to be replicated at all other nodes, and the replicated copies have a freshness threshold that must be satisfied. The data are propagated through periodic updates in the hierarchy. Each node periodically sends data to its child nodes. Given the freshness threshold, an algorithm and its distributed protocol can determine the optimal update period for each link of the hierarchy such that the freshness threshold is satisfied for every node and the overall replication overhead is minimized. The systems and methods can be used in any scenario where replicated data have consistency requirements, such as in a replicate overlay assisted resource discovery system.
REFERENCES:
patent: 5261094 (1993-11-01), Everson et al.
patent: 5713017 (1998-01-01), Lin
patent: 6289419 (2001-09-01), Takahashi
patent: 6839810 (2005-01-01), Takahashi
patent: 2003/0041074 (2003-02-01), Vasudevan et al.
patent: 2004/0158588 (2004-08-01), Pruet, III
patent: 2005/0144399 (2005-06-01), Hosomi
patent: 2006/0106894 (2006-05-01), Richardson
Haifeng Yu,Amin Vahdat,Design and Evaluation of a Continuous Consistency Model for Replicated Services,Computer Science Dept. Duke University,Durham,NC{yhf,vahdat]@cs.duke.ed.
Jalal Kawash,Consistency Models for Internet Caching, Dept. of Computer Science,American University of Sharjah,UAE,jkawash@ausharjah.edu.
S.B. Davidson,H.Garcia-Molina,D.Skeen,Consistency in Partitioned Networks,ACM Computing Survey,vol. 17,No. 3,Sep. 1985.
S. Adve,K. Gharachorloo,Shared Memory Consistency Models:A Tutorial, Rice University ECE Technical Report 9512,1995.
D. Abadi,Carney,Cetintemel,Cherniack,Convey,Lee,Stonebraker, Tatbul,Zdonik,Aurora: A new Model and architecture for data steam management,The VLDB Journal, 2003.
N.Beckmann,h.-P. Kriegel,The r*-Tree: An efficient and robust access method for points and rectangles,ACM SIGCMOD, 1998,West Germany.
S.Berchtold,C. Bohm,H.-P. Kriegel,The Pyramid-Technique:Towards Breaking the Curse of Dimensionality,ACM-SIGCMOD,1998,Seattle,Washington.
S.Berchtold,D. Keim,H.-P. Kriegel,The X-Tree:An Index Structure for High-Dimensional Data,In VLDB,1996,Munich, Germany.
A.Bharambe,M.Agrawal,S.Seshan,Mercury:Supporting Scalable Multi-Attribute Range Queries,In SIG-COMM,2004,Pittsburgh, PAB. Bloom,Space/Time Trade-offs in Hash Coding with Allow.
B. Bloom,Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM 13,7, 1970,Newton Upper Falls, MA.
P. Bonnet,J. Gehrke,P.Seshadri,Towards Sensor Darabase Systems,2nd Int'l Conference on MObile Data Management, Jan. 2001, Hong Kong.
Declan Butler, Everything,Everywhere, Nature 440,Mar. 23, 2006J.Chen,D.DeWitt,F. Tian, Y.Wang,Niagra:A Scalable Continuous Query System for Internet Databases,SIGMOD,2000.
M.Cherniack,H.Balakrishnan,M.Balazinska,D.Carney,U.Cetintemel, Y.Xing,S. Zdonik,Scalable Distributed Stream Processing,In CIDR Conference,2003.
K.Czajkowski,S.Fitzgerald,I. Foster, C. Kesselman,Grid Information sErvices for Distributed Resource Sharing,Proceedings of the 10th IEEE International Symposium,Aug. 2001.
D. Spence, T.Harris,XenoSearch:Distributed Resource Discovery in the XenoServer Open Platform,2003,Cambridge,UK.
D.Ganesan,B.Greenstein,D.Perelyubskiy,D.Estrin,J.Heidemann,An Evaluation of Multi-Resolution Storage for Sensor Networks,2003,ACM.
P. Gibbons,B. Karp,Y.Ke,S. Nath,S.Seshan, IrisNet:An Architecture for a Worldwide Sensor Web,IEEE Pervasive Computing,4(Oct.-Dec. 2003).
J.heidemann,F. Silva,C.Intanagonwiwat,R.Govindan,D.Estrin,D.Ganesan, Building Efficient Wireless Sensor Networks with Low Level Naming,ACM SOSP'01,2001.
R.Huebsch,J.Hellerstein,N.Lanham,B.T.Loo,S.Shenker,I.Stoica,Querying the Internet with PIER,29th VLDB Conference, 2003, Berlin, Germany.
Piotr Indyk,Rajeev Motwani,Approximate Nearest Neighbors:Towards Removing Curse of Dimensionality,in ACM STOC, 1998.
P. kulkarni,D.Ganesan,P. Shenoy,Qifeng Lu, SensEye:A Multi-tier Camera Sensor Network,2005,ACM Multimedia.
M. Balazinska,H. Balakrishnan, David Karger,INS/Twine:A Scalable Peer-to-Peer Architecture for Intentional Resource Discovery,2002,International Conf. on Pervasive Computing.
S.R. Madden,M.J.Franklin,J.M. Hellerstein,Wei Hong,TinyDB:An Acqusitional Query Processing System for Sensor Networks, 2005,TODS.
Michael Mitzenmacher, Compressed Bloom Filters, 2002, IEEE Transactions on Networking 10,5.
P.V. Mockapetris,Kevin J. Dunlap,Development of the Domain Name System, 1998,pp. 123-133,in SIGCOMM.
R.Motwani,J.Widom,A.Arasu,B.Babcock,S.Babu,M.Datar,G.Manku,C.Olston,J.Rosenstein,R.Varma, Query Processing,Resource Mngt.,and Approximation in Data Stream Mgnt.System,2003,CIDR.
D.Oppenheimer,J.Albrecht,D.Patterson,A.Vandat,Design and Implementation Tradeoffs for Wide-Area Resource Discovery,Jul. 2005,14th IEEE Symposium HPDC-14.
P.Pietzuch,J.Ledlie,J.Schneidman,M.Roussopoulos,M.Welsh,M.Selzter,Newtwork-Aware Operator Placement for Stream Processing Systems,2006,Harvard University.
J.Shneidman,P.Pietzuch,J.Ledlie,M.Roussopoulos,M.Seltzer,M.Welsh,Hourglass:An Infrastructure for Connecting SEnsor Networks and Application,2004,Harvard EECS Dept.,TR-21-04.
Chunqiang Tang,Zhichen Xu,S.Dwarkadas,Peer-to-Peer Information Retrieval Using Self-Organizing Semantic Overlay Networks,Aug. 2003,ACM SIGCOMM.
R.V.Renesse,K.Birman,W.Vogels,Astrolabe:A Robust and Scalable Technology for Distributed System Monitoring,Management,and Data Mining,2003,ACM Transactions on Computer Systems.
W.Yeong,T.Howes,S.Kille,Lightweight Directory Acess Protoco1,1995, RFC1777.
W.Yeong,T.Howes,S.Kille,Lightweight Directory Acess Protocol (v3), Dec. 1997,RFC 2251.
Java Naming and Directory Interface (JNDI), S8un MIcrosystems,,Java Naming and Directory Interface,http://java.sun.com/products/jndi/docs.html.
D. Oppenheimer,J.Albrecht,D. Patterson,A.Vahdat,Distributed Resorce Discovert on PlanetLab with SWORD,Dec. 2004,First Workshop on Real,Large Distributed Systems.
L.Peterson,T.Anderson,D.Culler,T.Roscoe, A Blueprint for Introducing Disruptive Technology into the Internet,Jul. 2002,PLanetLab.
International Search Report in corresponding PCT application No. PCT/US07/71403.
Liu Zhen
Xia Honghui
Yang Hao
Ye Fan
August Law LLC
International Business Machines - Corporation
Spieler William
Trujillo James
Willinghan George
LandOfFree
System and apparatus for optimally trading off the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and apparatus for optimally trading off the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and apparatus for optimally trading off the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4303027