algorithm - 最小限のブロードキャスト メッセージを使用してスパニング ツリーを計算するアルゴリズム

Question

課題では、メッセージの複雑さを軽減するために使用されるメッセージの 1 つを削除しながら、アルゴリズムの正確性を維持できるように、このアルゴリズムを変更する方法を考え出す必要があります。正直なところ、これを行う方法がわかりません。私が知る限り、すべてのノードは、ツリー内でどの隣接ノードが接続されていて、どのノードが接続されていないかを知る必要があるためです。

これは同期システムを使用して行うことを追加する必要があります

元のアルゴリズムは次のとおりです。

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

「すでに」メッセージを削除する必要があるため、最初のステップは、コードの最後のブロックと「else send "already" to p_j」という行を削除することでした。しかし、今は何ですか？私がこれを理解している限り (そして、それはあまりよくありません)、プロセッサーを永久に実行させて、すべての隣人からの応答を待つことはできません。ツリーがまだ構築されていない可能性があるため、任意に終了することもできません。

これを達成する方法に関するヒントはありますか?