6 Distributed Data Management II – Caching

In this section we will study the approach of using caching for the management of data in distributed systems. Caching always tries to keep data at the place where it is needed. The problem with this approach is that it may not be known in advance which processor will be the next to access a certain data item. Is it nevertheless possible to find good caching strategies? When is a caching strategy “good”? Obviously, a model is needed that allows us to measure the performance of caching strategies. 6.1 The model Let G = (V, E) be an arbitrary graph, and let U be the set of all shared objects. We assume that an adversary specifies a distributed application running on the nodes of the network, i.e., the adversary initiates read and write requests to the objects at the nodes of the network G. These requests must be served by an on-line caching strategy. We restrict the class of allowed applications specified by the adversary to be data-race free, i.e., a write access to an object is not allowed to overlap with other accesses to the same object, and there is some order among the accesses to the same object such that for each read and write access, there is a unique least recent write. Note that this still allows arbitrary concurrent accesses to different objects and concurrent read accesses to the same object