THE DYNAMIC PREDICATE STASHING COPY PROBLEM

One important issue being addressed in the design of Distributed Compu ter Networks is how to increase the availability of time-changing info rmation even in the event of failures. Recently, a technique called '' stashing'' was proposed. Stashing a file signifies placing a copy of t hat file in several nodes of the network. In addition, a ''predicate'' has been defined as a consistency requirement for a particular file c opy with respect to the original. We address the problem of minimizing the propagation cost of stashed copies subject to predicate restricti ons imposed by the user. In the version of the problem that we tackle, the user may receive a copy with a predicate better than requested. W e call this problem the Dynamic Predicate Stashing Copy Problem (DPSCP ) and propose a formulation to solve it. Resolution approaches, numeri cal results, and properties of the problem are also discussed. (C) 199 3 by John Wiley & Sons, Inc.