2

假设我有 n 台计算机。他们每个人都有一组整数。每台计算机不会有相同的设置。

即计算机 1 有 {1,2,3,4}，计算机 2 有 {4,5,10,20,21}，计算机 3 有 {-10,3,5}，依此类推。

我想复制这些数据，以便所有计算机都有所有整数，即所有计算机都有 {-10,1,2,3,4,5,10,20,21}

我想尽量减少每台计算机发送的消息数量，并尽量减少时间。（即避免使用串行方法，其中计算机 1 首先与每个人通信并获取丢失的数据，然后计算机 2 执行相同操作，依此类推。

这样做的有效方法是什么？

谢谢。

4

4 回答 4

1

最小的方法是：所有计算机仅将信息发送到一台（主）计算机并获得结果

为了可靠性，您可以考虑至少两台计算机作为主计算机

假设：

  1. 总共 n 台计算机
  2. 其中一台计算机被视为主机

算法 ：

  1. 所有计算机都发送input-info给 Master（总共 n-1 条消息）
  2. Master 处理信息
  3. Master 发送result-info到所有计算机（总共 n-1 条消息）

可靠性：

基于该算法的系统完全失效只有在所有的master都失效的情况下才会发生。

效率 ：

With 1 master  , total messages : 2 * (n-1)
With 2 masters , total messages : 2 * 2 * (n-1)
With 3 masters , total messages : 3 * 2 * (n-1)
于 2013-10-25T23:20:20.387 回答
1

如果所有计算机都在同一个网络上，您可以使用带有 SO_BROADCAST 选项的 UDP 套接字。

这样，当一台计算机“发送”消息时，所有其他计算机都会“接收”该消息并根据需要进行更新。

于 2013-10-26T00:14:54.247 回答
0

这是在 2*n - 2 次移动中执行此操作的一种方法。将机器建模为链表中的节点，编号从 1..n 开始。

  1. 让节点 1 在一条消息中将其所有数据发送到节点 2。
  2. 节点 2 记住节点 1 发送的消息，将其内容与节点 1 的内容合并，并将统一消息发送到节点 3。然后节点 2 等待节点 3 的响应。
  3. 节点 3 执行与上述相同的操作，依此类推，直到我们到达节点“n”。节点“n”现在拥有完整的集合。
  4. 节点“n”已经知道节点“n - 1”发送了什么消息，因此它将差异发送回节点“n - 1”
  5. 节点 'n - 1' 执行上述联合。由于它记住了节点'n - 2'的消息（在上面的步骤2中），它可以将差异发送回节点'n - 3'

等等。

我认为证明上述导致在网络中发送 2 * (n - 1) 条消息并不复杂。

我认为可以通过考虑每个节点具有唯一元素来证明 2n - 2 是必要的。证明 2n - 2 是必要的应该是一个简短的数学归纳练习。

于 2013-10-25T22:47:07.457 回答
0

好吧，已经有一个系统可以做到这一点，被广泛采用，有据可查，广泛可用，虽然它可能并不完美（对于完美的各种定义），但它是实用的。

它被称为 RSync。

你可以从这里开始：http: //www.samba.org/~tridge/phd_thesis.pdf

于 2013-10-25T22:52:18.567 回答