0

对于作业，我必须想出一种方法来修改此算法，以便我可以删除用于降低消息复杂性的消息之一，但仍保持算法的正确性。老实说，我不确定如何做到这一点，因为据我所知，每个节点都需要知道它的哪些邻居在树中连接到它，哪些没有。

我应该补充一点，这是使用同步系统完成的

这是原始算法：

Initially parent = null, children = empty, and other = empty

Upon receiving no message:
  if p_i = p_r, and parent = null then
    send M to all neighbors
    parent := p_i

upon receiving M from neighor p_j:
  if parent = null then
    parent := p_j
    send "parent" to p_j
    send M to all neighbors except p_j
  else send "already" to p_j

upon receiving "parent" from neighor p_j:
  add p_j to children
  if children union other contains all neighbors except parent, then terminate

upon receiving "other" from neighbor p_j:
  add p_j to other
  if children union other contains all neighbors except parent, then terminate

我需要删除“已经”消息......所以我的第一步是删除最后一个代码块和“否则将“已经”发送到 p_j 行。但现在呢？据我了解（这不是很好），我不能让处理器永远运行等待所有邻居的回复。我也不能任意终止它，因为树可能还没有完成构建。

关于我如何做到这一点的任何提示？

4

1 回答 1

2

在同步系统中，未按时接收消息也是信息。

于 2013-05-23T12:50:47.937 回答