Accuracy-Based Cache Consistency Management
for Numerical Object Replication
Hideya Ochiai
The University of Tokyo
jo2lxq@hongo.wide.ad.jp

Abstract
Object replication and cache consistency have been
one of major design issues in the recent Internet applications. In this paper, we forcus on accuracy-aware
applications (i.e., sensor applications), which use numerical data with allowing some errors. As long as thecache consistency between the origin’s and replicatedobjects is guaranteed to some error levels, the system
do not need to refresh its cache, resulting in saving network workloads. We propose a numerical cache consistency model and a cache control method for such applications. The results of our experments on weather
temperature data have shown (1) network traﬃc wasdynamically reduced depending on application requested
accuracy, and (2) the rate of exceedance to the threshold of allowable error was controllable, which was notin the traditional time-based cache validity control.

1

INTRODUCTION

Recent Internet applications replicate objects
among distributed servers, improving user request-toresponse performance and reducing network workloads.
In wide area sensor networks, sensor readings collectedby a server could be replicated to other servers to whichmost of users periodically access. Static cache lifetime
setting, which is widely carried out in the Internet applications(e.g., DNS, HTTP), does not always satisfy
the requirements of accuracy-aware applications, whereinconsistency of caches is associated with the numericalerror between the origin server’s and cached value.
Applications, in this paper, allow some inconsistencies (i.e., errors) between the origin’s and cached value,modeling those allowable error numerically by accuracy
requirement. We propose a numerical cache consistency model and a cache validity test method for suchaccuracy-aware applications. Applications that utilize

Hiroshi Esaki
The University of Tokyo
hiroshi@wide.ad.jp

sensor readings are instances of such application families. Our proposed method reduces the traﬃc between
the origin and cache proxy servers as much as possible
with guaranteeing given accuracy requirement.
In this paper, we assume that continuously generated numerical objects at the origin server should befetched by proxy servers distributed over the Internet,
and that IP network latency and limited bandwidth
should not be ignored for transferring data. This situation occurs especially when these servers are distributed internationally or over poor datalinks.
In the Internet applications, the cache validity ispractically modeled by lifetime. They usually assume
that objects should be discrete with respect to time;i.e., the updated documents must be available within
speciﬁc minutes or hours. However, some applications(e.g., sensor) can assume that objects change numerically and continuously. The absolute subtracts of objects between the origin’s and cached are more appropriate for the model of cache consistency than the lifetime model.
In our proposed system model, a proxy server dynamically calculates cache validity time depending on
the changing frequency of the value and the accuracy
requirement of user applications. When the objects atthe origin server change more frequently, the time forcache validity decreases, while increasing the origin-toproxy traﬃc. On the other hand, when they change
less frequently, the validity time increases, resulting in
the reduction of traﬃc.
The rest of this paper is organized as follows. In section 2, we describe related works. In section 3, we propose a method for accuracy-based cache validity control. Section 4 describes evaluation. In section 5, we
provide discussion and conclusion.

2RELATED WORK

Yu and Vahdat[3, 4] have proposed a numerical consistency model in write propagation replication ser-The v(t0 ) is transferred with information that describes the hidden state of v(t0 ), which is denoted byh(t0 ). In our model, h(t) is used for cache time estimation and should be correlated with valid cache time
under given a and e. The changing rate of v(t) (i.e.,dv
dt |t=t0 ) is the one of candidates for h(t0 ).
We deﬁne estimated cache validity time as,T (a, e, h)Figure 1. Value replication with h, the information that describes the hidden state of v(t)vices, supposing that user applications should allow
some errors. In their model, a origin server waits for
propagating updates until the diﬀerences between its
and replicated values come to the threshold that user
requested.
Olston et al[2] have proposed approximate cachingand quering methods, which maximize performancegains by dynamically adapting precision setting to user
application requirements.
In these works, they focus on the situation whereupdates should be propagated by push manner, andthe propagation is initiated by the origin servers. Wefocus on pull-based cache replication, which objects arereplicated on demand. The validity of replicated data
are tested by the proxies and end users.

33.1

ACCURACY-BASED CACHE VALIDITY CONTROL
System ModelFigure 1 illustrates the system we discuss. Proxyservers make replications of the value managed at anorigin server, initiated by a request of user applications.
Let v(t) be the value produced by the origin server attime t, a be the accuracy requirement (i.e., allowableerror) given by the application to be guaranteed, ande be an expected exceedance of values to the accuracyrequirement. For example, if e = 0.1, the cache inconsistency is expected to exceed the allowable error at therate of 0.1. The end users submit latest data retrieval
queries to their local proxy servers with a and e.
Initiated by the end user, the proxy server downloads the current value v(t0 ) from the origin server if
it does not have any valid value in its cache. Here, weassociated that time as t0 . The proxy stores v(t0 ) in
the cache after downloaded.

This function tells the threshold for cache validity
by time on the a and e requirements. Normally, T isstrictly increasing function with regard to a and e; i.e.,the change of accuracy requirements from 0.1 to 1.0
prolongs cache validity.
We here address how to test cache validity. Supposethat a proxy has cached a value at time t0 ; v(t0 ) iscached with h(t0 ). When a user requests with a1 ande1 at time t1 to the proxy (t1 > t0 ),when,t1 − t0 ≤ T (a1 , e1 , h(t0 ))(1)then, the cached v(t0 ) is valid. The proxy should returnv(t0 ) to the requested user.
when,t1 − t0 > T (a1 , e1 , h(t0 ))(2)then, the cached v(t0 ) is invalid for the user, it must
be reﬂeshed.
Since the T varies on the a and e, the actually estimated cache validity time can be minimum T . Lessvariation of the a and e improves the eﬀectiveness of
our proposed method, and systems should be implemented to maximize such eﬀectiveness.

3.2

Formulating the Estimated Cache Validity TimeThe implementation of T (a, e, h) depends on the features of v(t). It could be formulated by statisticallyanalyzing v(t). We propose a method to get T (a, e, h)by analyzing distribution (i.e., probability density) of
the h and actual cache validity times, which we denoteby τ , under several accuracy requirements a.
In this paper, we denote the distribution by
Da (h, τ ). Formally, τ can be calculated by the following formula,τ (t) = min{t0 | |v(t0 ) − v(t)| > a} − tt0(t0 > t)(3)

At ﬁner accuracy requirement (e.g., a = 0.1), τ isbiased to be small, whereas at grainer accuracy requirement (e.g., a = 1.0), τ is widely distributed. As h becomes¯ dv ¯ larger, smaller τ becomes in the case of h being¯ ¯.
dt
After analyzing some Da , we can get T (a, e, h) by
the following transformation rule. T (a, e, h) is the Tthat satisﬁes,Z T
Da (τ | h)dτ = e(4)0Here, e is the rate of exceedance to the accuracy
requirement, and Da (τ |h) is,Da (h, τ )Da (τ | h) = R +∞Da (h, τ )dτ0(5)T (a, e, h) is the cache time such that the exceedanceof the threshold a are expected to e on given a and h.
In practice, after getting T (a, e, h) from the statisticalanalysis, it should be approximated to a formula.

Figure 2. The distribution of the valid cachetime τ and changing rate of value h at theaccuracy requirement 1.0 on Live E! weather
temperature data

4.2

4We evaluated how much our proposed method reduces network traﬃc and satisﬁes application requirements compared to the time-based cache validity control method.
We used Live E![1] temperature sensor readings forevaluation. We chose 39 sensors that have the samefeature in sampling data: i.e., they are organized by thesame sensor model. The total count of the temperature
values for analysis was about 4.2 million.
¯ dvIn¯ this analysis and simulation, we associated h as
¯ ¯, the absolute changing rate of the value. Cachedt¯ ¯¯validity time has a correlation with ¯ dv
dt .

4.1

Reduction of TraﬃcEVALUATION

Estimated Cache Validity TimeWe analyzed Da (h, τ ) from a = 0.1 to a = 1.0. Figure 2 shows the distribution in the case of a = 1.0.
Using these data, we transformed it to T (a, e, h) using
the formula (4).
After the analysis of the form of T (a, e, h), we concluded that the following formula approximately provides T (a, e, h).
T (a, e, h) ≈ 0.22ae exp{3.5e(e−1)} exp{−0.00963h}[sec]We used this formula for estimating the validity timein the following experiments.

Figure 3 shows the traﬃc on accuracy requirements
under the accuracy-based cache control. As grainer
the accuracy requirement becomes, the less traﬃc itgenerated. As more expected exceedance is allowed,
the less traﬃc it generated.
In the traditional time-based cache control, the trafﬁc do not vary even though users have diﬀerent accuracy requirements. The ability of changeing traﬃc depending on accuracy requirements indicates that theproposed method has reduced the wasteful data exchange workloads in the time-based cache control.

4.3

Exceedance of Error Boundaries

Figure 4 shows the observed exceedance on several
expected exceedance speciﬁcation given by e and accuracy requirements under the accuracy-based control.
They almost remained to the expected exceedance invarious accuracy requirements.
In the time-based validity control, the exceedancecannot be conﬁgured by users. The validity is determined statically by its administrator. As ﬁgure 5
shows, the observed exceedance was high for some users(i.e., system provided useless data for those users) andwas extremely low for others (i.e., system required highnetwork workloads).

Figure 3. Trafﬁc generated by the origin
serverFigure 5. Observed exceedance on timebased cache control

References

Figure 4. Observed exceedance on accuracybased cache control

5

DISCUSSION and CONCLUSION

We have proposed a numerical cache consistencymodel and a validity control method for accuracyaware applications. In this idea, the absolute subtracts of numerical values between the origin and cacheservers are more appropriate for the metric of cacheconsistency than the lifetime metric. Our method has
enabled dynamic cache time control depending on thechanging rate and accuracy requirements of applications. The results of our experiments have shown; (1)network traﬃc was dynamically and appropriately controlled depending on user requested accuracy; (2) exceedance rate to the threshold of error was controllable
in accuracy-based cache control, whereas the control
was diﬃcult in time-based method.

[1] M. Nakayama, S. Matsuura, H. Esaki, and H. Sunahara.
Live E! project: Sensing the earth. LNCS, 4311:61–74,2006.
[2] C. Olston, B. T. Loo, and J. Widom. Adaptive precision setting for cached approximate values. In ACM
SIGMOD, pages 355–366, 2001.
[3] H. Yu and A. Vahdat. Eﬃcient numerical error bounding for replicated network services. In The VLDB Journal, pages 123–133, 2000.
[4] H. Yu and A. Vahdat. Design and evaluation of aconit-based continuous consistency model for replicatedservices. ACM Transactions on Computer Systems,
20(3):239–282, aug 2002.