[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/564691.564701acmconferencesArticle/Chapter ViewAbstractPublication PagesmodConference Proceedingsconference-collections
Article

Best-effort cache synchronization with source cooperation

Published: 03 June 2002 Publication History

Abstract

In environments where exact synchronization between source data objects and cached copies is not achievable due to bandwidth or other resource constraints, stale (out-of-date) copies are permitted. It is desirable to minimize the overall divergence between source objects and cached copies by selectively refreshing modified objects. We call the online process of selecting which objects to refresh in order to minimize divergence best-effort synchronization. In most approaches to best-effort synchronization, the cache coordinates the process and selects objects to refresh. In this paper, we propose a best-effort synchronization scheduling policy that exploits cooperation between data sources and the cache. We also propose an implementation of our policy that incurs low communication overhead even in environments with very large numbers of sources. Our algorithm is adaptive to wide fluctuations in available resources and data update rates. Through experimental simulation over synthetic and real-world data, we demonstrate the effectiveness of our algorithm, and we quantify the significant decrease in divergence achievable with source cooperation.

References

[1]
B. Adelberg, H. Garcia-Molina, and B. Kao. Applying update streams in a soft real-time database system. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 245-256, San Jose, California, May 1995.
[2]
B. Adelberg, B. Kao, and H. Garcia-Molina. Database support for efficiently maintaining derived data. In Proceedings of the International Conference on Extending Database Technology, pages 223-240, Avignon, France, Mar. 1996.
[3]
S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. In Proceedings of the Seventh International World Wide Web Conference, Brisbane, Australia, Apr. 1998.
[4]
G. S. Brodal, J. L. Träff, and C. D. Zaroliagis. A parallel priority queue with constant time operations. Journal of Parallel and Distributed Computing, 49(1):4-21, Feb. 1998.
[5]
M. Cherniack, M. J. Franklin, and S. Zdonik. Expressing user profiles for data recharging. IEEE Personal Communications: Special Issue on Pervasive Computing, 8(4):32-38, Aug. 2001.
[6]
J. Cho and H. Garcia-Molina. Estimating frequency of change. Technical report, Stanford University Computer Science Department, 2000. http://dbpubs.stanford.edu/pub/2000-4.
[7]
J. Cho and H. Garcia-Molina. Synchronizing a database to improve freshness. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 117-128, Dallas, Texas, May 2000.
[8]
E. Cohen and H. Kaplan. Refreshment policies for web content caches. In Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2001), Anchorage, Alaska, Apr. 2001.
[9]
P. Deolasee, A. Katkar, A. Panchbudhe, K. Ramamritham, and P. Shenoy. Adaptive push-pull: Disseminating dynamic Web data. In Proceedings of the Tenth International World Wide Web Conference, Hong Kong, China, May 2001.
[10]
L. Do, P. Ram, and P. Drew. The need for distributed asynchronous transactions. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 534-535, Philadelphia, Pennsylvania, June 1999.
[11]
T. Dorcey. CU-SeeMe desktop videoconferencing software. Connexions, 9(3), Mar. 1995.
[12]
D. Estrin, L. Girod, G. Pottie, and M. Srivastava. Instrumenting the world with wireless sensor networks. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2001), Salt Lake City, Utah, May 2001.
[13]
A. Gal and J. Eckstein. Managing periodically updated data in relational databases: A stochastic modeling approach. Journal of the ACM (to appear), 2002.
[14]
R. A. Golding and D. D. E. Long. Modeling replica divergence in a weak-consistency protocol for global-scale distributed data bases. Technical report UCSC-CRL-93-09, Computer and Information Sciences Board, University of California, Santa Cruz, 1993.
[15]
J. M. Kahn, R. H. Katz, and K. S. J. Pister. Next century challenges: Mobile networking for "smart dust". In Proceedings of the ACM/IEEE International Conference on Mobile Computing and Network Monitoring (MobiCom 99), pages 271-278, Seattle, Washington, Aug. 1999.
[16]
A. Labrinidis and N. Roussopoulos. Update propagation strategies for improving the quality of data on the Web. In Proceedings of the Twenty-Seventh International Conference on Very Large Data Bases, pages 391-400, Rome, Italy, Sept. 2001.
[17]
M. J. McPhaden. Tropical Atmosphere Ocean Project, Pacific Marine Environmental Laboratory, 2001. http://www.pmel.noaa.gov/tao/.
[18]
C. Olston, B. T. Loo, and J. Widom. Adaptive precision setting for cached approximate values. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 355-366, Santa Barbara, California, May 2001.
[19]
C. Olston and J. Widom. Offering a precision-performance tradeoff for aggregation queries over replicated data. In Proceedings of the Twenty-Sixth International Conference on Very Large Data Bases, pages 144-155, Cairo, Egypt, Sept. 2000.
[20]
C. Olston and J. Widom. Best-effort cache synchronization with source cooperation. Technical report, Stanford University Computer Science Department, 2001. http://dbpubs.stanford.edu/pub/2001-43.
[21]
G. Pottie and W. Kaiser. Wireless integrated network sensors. Communications of the ACM, 43(5):551-558, May 2000.
[22]
C. Pu and A. Leff. Replica control in distributed systems: An asynchronous approach. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 377-386, Denver, Colorado, May 1991.
[23]
K. Ramamritham. Real-time databases. International Journal of Distributed and Parallel Databases, 1(2):199-226, 1993.
[24]
G. Salton and C. S. Yang. On the specification of term values in automatic indexing. Journal of Documentation, 29:351-372, 1973.
[25]
P. Sanders. Randomized priority queues for fast parallel access. Journal of Parallel and Distributed Computing, 49(1):86-97, Feb. 1998.
[26]
J. Stewart. Calculus: Early Transcendentals, Second Edition. Brooks/Cole, 1991.
[27]
B. Urgaonkar, A. G. Ninan, M. S. Raunak, P. Shenoy, and K. Ramamritham. Maintaining mutual consistency for cached Web objects. In Proceedings of the Twenty-First International Conference on Distributed Computing Systems, Phoenix, Arizona, Apr. 2001.
[28]
H. Yu and A. Vahdat. Design and evaluation of a continuous consistency model for replicated services. In Proceedings of the Fourth Symposium on Operating Systems Design and Implementation, San Diego, California, Oct. 2000.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGMOD '02: Proceedings of the 2002 ACM SIGMOD international conference on Management of data
June 2002
654 pages
ISBN:1581134975
DOI:10.1145/564691
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 June 2002

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMOD/PODS02

Acceptance Rates

SIGMOD '02 Paper Acceptance Rate 42 of 240 submissions, 18%;
Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)9
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2020)Energy Management Techniques for WSNs (2): Data-Driven ApproachWireless Sensor Networks10.1007/978-3-030-29700-8_5(259-398)Online publication date: 26-Jan-2020
  • (2019)Detecting removed attributes in the cyber system for smart manufacturingThe Journal of Supercomputing10.1007/s11227-019-02809-6Online publication date: 12-Mar-2019
  • (2019)A Difference Detection Mechanism Between API Cache and Data Center in Smart ManufacturingFrontier Computing10.1007/978-981-13-3648-5_39(349-353)Online publication date: 19-May-2019
  • (2018)Estimation of DNS Source and Cache Dynamics under Interval-Censored Age SamplingIEEE INFOCOM 2018 - IEEE Conference on Computer Communications10.1109/INFOCOM.2018.8485840(1358-1366)Online publication date: Apr-2018
  • (2016)On Sample-Path Staleness in Lazy Data ReplicationIEEE/ACM Transactions on Networking10.1109/TNET.2015.248859524:5(2858-2871)Online publication date: 1-Oct-2016
  • (2015)On sample-path staleness in lazy data replication2015 IEEE Conference on Computer Communications (INFOCOM)10.1109/INFOCOM.2015.7218484(1104-1112)Online publication date: Apr-2015
  • (2015)Online refresh strategies for content based feed aggregationWorld Wide Web10.1007/s11280-014-0288-y18:4(913-947)Online publication date: 1-Jul-2015
  • (2014)Stochastic models of pull-based data replication in P2P systems14-th IEEE International Conference on Peer-to-Peer Computing10.1109/P2P.2014.6934309(1-10)Online publication date: Sep-2014
  • (2013)Optimized retrieval algorithms for personalized content aggregation2013 IEEE 14th International Conference on Information Reuse & Integration (IRI)10.1109/IRI.2013.6642482(270-277)Online publication date: Aug-2013
  • (2013)Quality-Aware Sensor Data ManagementThe Art of Wireless Sensor Networks10.1007/978-3-642-40009-4_13(429-464)Online publication date: 14-Dec-2013
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media