1
$\begingroup$

I'm doing a presentation for a distributed systems and networks course. I'm using the book "Design and Analysis of Distributed Algorithms", written by Nicola Santoro. This book contains the proof of equivalence between SPT and leader election but there are some points that I don't understand at all.

Santoro uses this method:

We create an algorithm $B$ that solves SPT as follows. Let $A$ be an universal election algorithm. At the first step, we execute $A$, and at the second step we use the leader elected in first step to use the protocol "Shout", (which constructs an ST because the leader is the single initiator). This takes exactly $2m$ messages. So the message complexity of $B$ is given by $$M[B]=M[A]+2m\,.\tag1$$ At this point because we have previously found a lower bound for $M[SPT]$ ($M[\mathrm{SPT}]\geq \Omega(m)$) Santoro says, "with at most $O(m)$ additional messages, any election protocol can be made to construct a spanning tree; as $\Omega(m)$ messages are needed anyway" therefore

$$M[\mathrm{SPT}]\leq M[\mathrm{Elect}]\,.\tag2$$

On the other side it's easy to see that we can use a SPT protocol $C$ to create a Spanning Tree and then with $O(n)$ additional messages (the cost of notification from the root to the leafs it's exactly $n-1$) simulate an Election algorithm $D$. we obtain that:

$M[D]=M[C]+O(n)\,.\tag3$

now santoro says:"In other words, the message complexity of Elect is no more than that of Elect plus at most another $O(n)$ messages; as election requires more than $O(n)$ messages anyway" therefore

$$M[\mathrm{Elect}]\leq M[\mathrm{SPT}]\,.\tag4$$

combining equation $(2)$ and $(4)$ we obtain that the problems are computationally equivalent and that they have the same complexity (in terms of messages).

what i do not understand are the conclusion $(2)$ and $(4)$.

the data given are: $$1) M[\mathrm{Elect}]=\Theta(m+ n\log n)$$; $$2) M[\mathrm{SPT}]\geq \Omega(m)$$; $M[X]:=$ message complexity of algorithm $X$

$\endgroup$
  • 1
    $\begingroup$ I've tidied up the formatting of your post but I found your question very hard to follow. In particular, I found it very hard to tell which parts of the maths you were stating as fact and which parts you are claiming follow from other parts. When writing mathematics, it's important to use little phrases like "We have...", "This gives...", "It follows that..." and "Therefore, ..." so that the reader can follow your argument, rather than just giving a list of formulas and equations. $\endgroup$ – David Richerby Nov 19 '14 at 10:46
  • $\begingroup$ ok @DavidRicherby firs thanks to using your time, i'll try to be clearer. $\endgroup$ – Duccio Bertieri Nov 19 '14 at 14:05
  • $\begingroup$ i did my best editing the question. $\endgroup$ – Duccio Bertieri Nov 19 '14 at 14:35
  • $\begingroup$ no one can explain it? $\endgroup$ – Duccio Bertieri Nov 22 '14 at 11:43

Your Answer

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

Browse other questions tagged or ask your own question.