Distributed caching independent of the network size
Matthias Westermann · 2002
We consider distributed caching strategies for networks in a model that takes in addition to remote accesses also local accesses into account. The goal is to minimize the congestion while obeying memory capacity constraints in the network. The on-line strategies are evaluated in a competitive analysis in which their costs are compared with the cost of an optimal off-line strategy. Previous results either depend on the network size or assume that the on-line strategies have increased memory capacity constraints in comparison to an optimal off-line strategy.(MATH) Our main result is a strategy for complete networks. For each node v, we are given memory capacity m(v) and load d(v) for a remote access. The load for a local access is one. For each application concerning a set X of shared data objects, with |X| ≤ Σv m(v) / d(v), the strategy achieves a competitive ratio of