CODEWITHSUNDEEP
algorithmcomputer-sciencedistributed-computing
Mirrana
Mirrana

Reputation: 1731

Algorithm to compute a spanning tree using minimal broadcast messages

For an assignment, I have to come up with a way to modify this algorithm in such a way that I can remove one of the messages used to reduce message complexity, yet still maintain algorithm correctness. I'm honestly not sure how to do this, since as far as I can tell, every node needs to know which of its neighbors are connected to it in the tree, and which are not.

I should add that this is to be done using a synchronous system

Here's the original algorithm:

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

I need to remove the "already" message... so my first step was to remove the last block of code and the line "else send "already" to p_j". But now what? As far as I understand this (and that's not terribly well), I can't just let a processor run forever waiting to hear back from all of its neighbors. I can't terminate it arbitrarily either because the tree may not be done building yet.

Any tip on how I can accomplish this?

Upvotes: 0

Views: 76

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65427

In a synchronous system, not receiving a message on time is information too.

Upvotes: 2

Related Questions