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 redundan cy is extremely costly to achieve, it has been proposed to keep perfec tly 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. T he problem of optimizing the updates so that the maximum lifetime leng th constraints are respected has been previously formulated as a binar y 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 ano ther formulation, based on a state transition graph approach. We prove that only a subset of states and transitions will be in the optimal s olution and that, thanks to those properties, it is possible to greatl y 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 futu re applications of broadband multicast services.