Optimal replica control protocols exhibit symmetric operation availabilities
Optimal replica control protocols exhibit symmetric operation availabilities
复制标题
最佳副本控制协议表现出对称操作可用性
DOI：
10.1109/ftcs.1998.689476
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
H. Pagnia
中科院分区：
文献类型：
--
作者：
Oliver E. Theel;H. Pagnia
在分布式系统中复制数据是提高数据访问操作的可用性和性能的合适方法。不幸的是，在这两个属性之间存在权衡：表现例如高读取可用性和低读取操作成本的副本控制协议通常遭受低写入可用性和高写入操作成本。这种权衡对于像加权投票这样的协议是可见的，对于这些协议，可以通过调整某些协议参数来定制上述特征。在保留协议的正确行为的同时更改加权投票协议的读写仲裁会增加读可用性和写操作成本，或者增加写可用性和读操作成本，但不能同时增加两者。我们证明了对于一大类副本控制协议，读写操作可用性之间存在一定的对称性。我们进一步演示了如何对没有这种对称性的协议进行优化，使得得到的协议具有相同的成本，但具有更高的读或写可用性，或者两者兼而有之。我们提出了两种设计策略来优化副本控制协议。以著名的网格协议(缺乏对称性)为例，应用我们的发现推导出两种具有优越特性的不同副本控制协议。
Replicating data in a distributed system is a suitable means for increasing the availability as well as the performance of data access operations. Unfortunately, there exists a trade-off between these two properties: a replica control protocol which exhibits, e.g., a high read availability and low read operation costs usually suffers from low write availability and high write operation costs. This trade-off is visible for protocols like Weighted Voting for which the above characteristics can be customized by adjusting certain protocol parameters. Changing the read and write quorums of a Weighted Voting protocol while preserving the protocol's correct behavior increases either the read availability and the write operation costs or the write availability and the read operation costs but not both at the same time. We prove that for a large class of replica control protocols, a certain symmetry between the read and write operation availability exists. We further demonstrate how a protocol without this symmetry property can be optimized such that the resulting protocol has identical cost but a higher read or write availability or both. We present two design strategies which lead to those optimized replica control protocols. By using the well-known Grid Protocol (which lacks symmetry) as an example, we apply our findings to derive two different replica control protocols with superior characteristics.