使用最少广播消息计算生成树的算法

Question

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

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

这是原始算法:

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”这一行。但现在呢？据我了解这一点(这不是很好)，我不能让处理器永远运行等待收到所有邻居的回复。我也不能任意终止它，因为树可能还没有完成构建。

关于如何完成此操作的任何提示？

Answer 1

在同步系统中，没有及时收到消息也是信息。