World's most popular travel blog for travel bloggers.

# simple lower bound for constructing a Spanning tree

, ,
Problem Detail:

i have to demonstrate that under the assumptions{Bidirectional Links, Total Reliability (no error during the execution), Connectivity, Distincts ids values, Multiple inititators (entities that starts the algorithm} the problems of constructing a spanning tree takes at least $\Omega(m)$ messages, where $m=|E|$

#### Answered By : Duccio Bertieri

i tried to solve this problem in this way:

Assume that there exists a correct SPT protocol $A$ thatuses fewer than $m$ messages. This means that there is at least one link in $G$ where no message is transmitted. Consider an execution of the algorithm on $G$, and let $e = (x, y) \in E$ be the link where no message is transmitted by $A$.

Now construct a new graph $G^{'}$ from $G$ by removing the edge $e$ and adding a new node $z$ and two new edges $e1 = (x, z)$ and $e2 = (y, z)$. Set $z$ in a noninitiator status ($z$ does not starts the execution of the algorithm). Run exactly the same execution of $A$ on the new graph $G$ : since no message was sent along $(x,y)$ in the original execution in $G$, $x$ and $y$ never send a message to $z$ in the current execution in $G^{'}$ ; and since $z$ is not an initiator and does not receive any message, it will not send any message.

At the end of the alghoritm a tree $T$ should have been constructed, however, $z$ is not part of $T$, and hence $T$ does not span $G$.

in other words $A$ works only if $z$ is in a initiator status, therefore $A$ is not correct.