1000个项目,1000个节点,每个节点3个项目,最佳复制方案,以最大限度地减少节点失败时的数据丢失

Question

我想知道Skiena 算法设计手册(第2版)中问题2-44的正确答案是什么.

问题如下:

我们有1,000个数据项存储在1,000个节点上.每个节点可以存储三个不同项目的副本.提出复制方案,以在节点发生故障时将数据丢失降至最低.当三个随机节点发生故障时,丢失的数据条目的预期数量是多少？

我在考虑节点n有n,n + 1和n + 2的数据项.

因此,如果3个连续节点丢失,那么我们将丢失1个项目.

有更好的解决方案吗？

Answer 1

你提出的方法还不错,但也看看这里.RAID中使用的想法可能会给你一些想法.例如,如果您有2个数据项,而不是存储3个项目,则如果另一个项目失败,您可以恢复其中任何一项.这个想法非常简单 - 您将项目存储在2个节点中,将其位数存储在第三个项目中.我相信如果您利用这个想法,您将能够对单个数据项进行3次以上的备份(即超过3个节点必须失败才能丢失信息).