一种分布式系统中最优复制的策略分析

在网络中定位最优复制以最小化通讯代价。假定网络采用read-one-write-all策略来保证网络数据一致性,那么存在一个决定复制定位的最优化问题。提出了研究复制问题中读、写比率以确定最优化通讯代价。问题可转换成一个0- 1线性规划问题,并将此问题扩展为一个P中值问题,可以证明这个问题是NP-complete的问题,并提出了一种多项式时间内的此问题求解算法。

Optimal Location of Replicas Strategy in Distribute System

We consider the problem of locating replicas in a network to minimize communications costs.Under the assumption that the read-one-write-all policy is used to ensure data consistency,an optimization problem is formulated in which the cost function estimates the total communications costs.The paper concentrates on the study of the optimal communications cost as a function of the ratio between the frequency of the read and write operations.The problem is reformulated as a zero-one linear programming problem.The general problem is proved to be NP-complete.For path graphs a dynamic programming algorithm for the problem is presented.