The following is a Java applet demo of the best-effort cache synchronization algorithm presented in the SIGMOD 2002 paper Best-Effort Cache Synchronization with Source Cooperation
by Chris Olston and Jennifer Widom. Select a data set and size for viewing the demo, or read the instructions below. Brief descriptions of the data sets are also available.
| Data Set | Screen Size | |
| Random Walk | small | large |
| Ocean Buoy Data (2 data objects) | small | large |
| Ocean Buoy Data (6 data objects) | small | large |
Overview
This demo plots the actual and cached data values of several data objects reporting to a single cache in a bandwidth-limited network environment. Data objects are assigned a priority based on the time averaged divergence between the cached value for the data and the actual value at the source, where the divergence is calculated using a value deviation metric. Each data source maintains a threshold level which is determined dynamically. At every time step, each source tries to send its data objects starting with those of highest priority and stopping when there are no more data objects whose priorities exceed the threshold or it runs out of bandwidth. With each data object that is sent, the source increases its threshold value. When there is extra bandwidth available, the cache sends messages to the sources signifying that they should decrease their thresholds.
Display
Each graph on the display plots the actual data value (red) and the cached data value (blue) against time. The data curve is updated as the data changes, and the cached value is updated as the cache receives the data packet containing the update from the source. Divergence can be seen as the distance between the two curves. The time averaged divergence since the last update can be calculated by adding up the total area between the two curves.
In some of the data sets, there are multiple data objects residing on the same source. In these cases, the shading at the right hand side of each graph alternates between data sources.
At the lower right corner are bars corresponding to the network queue size and bandwidth utilization.
Controls
The sliders on the left hand side of each graph control the bandwidth of the source. In cases where two or more data objects reside on the same source, the sliders for those objects will be linked since the bandwidth is shared between the two objects. The sliders at the bottom control the cache bandwidth, and the simulation delay. Bandwidth is measured in arbitrary unit amounts. In each of the simulations, the size of each data packet is set to 10 units, and the size of the positive feedback packet from the cache is set to 1 unit.
Note
This demo is a Java Applet which uses AWT. If you are using Netscape 4.x for the Mac or Unix, the default JRE may not have AWT support, which will cause the demo not to work.
Random Walk: At each time step an item in this data set will transition to another value with a certain probability. If an item is selected to transition it will either transition to a value one higher or one lower with equal probability.
Ocean Buoy Data: This data set is a subset of real-world data collected from ocean buoys monitoring wind speed. In the demo with 2 data objects, the data reported is from two different buoys. In the demo with 6 data objects, the data is reported from three buoys, each monitoring two values, velocities in the X and Y directions.