考虑到每个对等点在您的情况下都是单独行动的,并不是只有一个自动机在解决您的问题,而是很多。由于在给定延迟内不可用时获取数据块通常是多项式问题,并且由于该工作是由单个对等方完成的,因此您的问题不是本地每个对等方的 NP 问题。
另一方面,如果服务器必须计算备份资源的最小分配来传输“丢失的块”,则必须首先找出对等方丢失块的概率(例如平均值 + 标准偏差)。假设您知道此类事件的统计分布,您可以计算传输那些丢失的块所需的总带宽,并选择带宽中的故障/容限风险。如果您使用多个服务器来满足需求,请确保您的对等方随机联系它们以分配负载。
解决这个统计问题不是 NP 问题。您可以从每个对等点收集故障信息并将其添加到中央/服务器对等点。因此,我的结论是,您的问题不是 NP 问题。
第二部分:
哦,我现在更好地理解了您的情况:多个“服务器”对等点可能会帮助一个对等点获得完整的块。在这种情况下,对于给定的块,系统中服务器对等点的数量呈指数增长。在这种情况下,这个优化问题对我来说具有泛滥问题的所有特征,它们是 NP。
即使你的对等点图和它们之间的潜在连接是静态的(在真正的 P2P 网络中绝不会出现这种情况),在合理的时间内为超过 50 或 100 个节点计算最佳解决方案实际上是不可能的,除非你可以在这张图上做出非常具体的假设(这在一般情况下几乎从来没有,而且并不总是有用的)。
但是您是否绝对需要绝对最优解,或者接近最优解是否足够好?
启发式方法会告诉您,如果您的对等点具有或多或少相同的下载带宽容量,那么首先为具有最高 UPLOAD 带宽的对等点提供服务以最大化雪崩效应并降低对等点寻求帮助的风险是有意义的,一般来说。
如果你的图是相对平衡的(也就是说,大多数对等点可以连接到大多数对等点),那么我敢打赌初始服务器的最小带宽将是图中节点数乘以对等点期望的平均速度的对数函数被送达。这只是我的直觉,应该通过实际测量或对您的案例进行强有力的建模来验证。