0
$\begingroup$

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|$

$\endgroup$
  • $\begingroup$ What have you tried? Where did you get stuck? What specifically is your question? Can you identify a more narrowly scoped question about your attempt and what you need help with? $\endgroup$ – D.W. Nov 28 '14 at 9:27
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For future reference: We're looking for answers that you are confident in (not guesses, not attempts that you want feedback on). Not sure whether that applies in this case or not, but I just wanted to let you know so that you can be aware of the expectations on this site. $\endgroup$ – D.W. Nov 28 '14 at 9:28
  • $\begingroup$ This is not an attempt. My teacher tells me that my answer is correct. $\endgroup$ – Duccio Bertieri Dec 2 '14 at 21:35
  • $\begingroup$ When you write "I tried to solve this problem...", it sounds like you are not confident whether your answer is correct. $\endgroup$ – D.W. Dec 3 '14 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.