Managing redundancy in distributed computer networks: A state transition graph approach for the stashing problem

Managing redundant information is becoming an important issue in today's increasingly large distributed computer networks. As total redundancy is extremely costly to achieve, it has been proposed to keep perfectly updated information only at the servers, while keeping old copies of that information on local computers. For such copies to be useful, a maximum lifetime length is assigned to them. Before the lifetime has elapsed, the local devices must be stashed with a new updated copy. The problem of optimizing the updates so that the maximum lifetime length constraints are respected has been previously formulated as a binary problem and proved to be NP-hard through a reduction to the Steiner tree problem in graphs. In this paper we explore the properties of another formulation, based on a state transition graph approach. We prove that only a subset of states and transitions will be in the optimal solution and that, thanks to those properties, it is possible to greatly reduce the size of the graph. A solution algorithm that is based on an efficient evaluation of similar Steiner tree problems with similar properties is presented. We discuss extensions of this problem to future applications of broadband multicast services.