Managing Redundancy in Distributed Computer Networks: A State Transition Graph Approach for the Stashing Problem

Brian Walker and Brunilde Sansó
Additional contact information
Brian Walker: École Polytechnique de Montréal, Montreal, Quebec, Canada
Brunilde Sansó: École Polytechnique de Montréal, Montreal, Quebec, Canada

Operations Research, 1998, vol. 46, issue 3, 305-315

Abstract: 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.

Keywords: Computers/computer science; distributed systems; Information; management (search for similar items in EconPapers)
Date: 1998
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.3.305 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:3:p:305-315

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().