Replication Algorithms in a Remote Caching Architecture

Abstract

We study the cache performance in a remote caching architecture. The high performance networks in many distributed systems enable a site to access the main memory of other sites in less time than required by local disk access. Remote memory is thus introduced as an additional layer in the memory hierarchy between local memory and disks. Efficient use of remote memory implies that the system caches the “right” objects at the “right” sites. Unfortunately, this task can be difficult to achieve for two reasons. First, as the size of the system increases, the coordinated decision making needed for optimal decisions becomes more difficult. Second, because the participating sites in a remote caching architecture can be autonomous, centralized or socially optimal solutions may not be feasible. In this paper we develop a set of distributed object replication policies that are designed to implement different optimization goals. Each site is responsible for local cache decisions, and modifies cache contents in response to decisions made by other sites. We use the optimal and greedy policies as upper and lower bounds, respectively, for performance in this environment. Critical system parameters are identified, and their effect on system performance studied. Performance of the distributed algorithms is found to be close to optimal, while that of the greedy algorithms is far from optimal. © 1993 IEEE