Tried to research here and on other sites with no luck regarding finding the maximal and average number of time slots in an Adaptive tree walk protocol. i'll explain what i mean here:

In a simple(provided an image for illustration at the end of the post) Adaptive tree walk protocol, Divided by time slots where a station can only transmit at the beginning of each time slot.

If for instance stations C and A want to broadcast in time t=0 with probability p(for simplicity) (None of the other stations want to transmit at all), Is it possible to know the maximal or average number of time slots that will pass until(including) the slot in which there will be a successful broadcast?

Simple network diagram i am asking about:


Note: for simplicity, in this question, no other station except C and A want to broadcast at all


1 Answer 1


It is clear that you cannot know the maximum if $p \neq 1$, because there is always some chance, no matter how small, that neither station will transmit after any $n$ attempts.

However, if $p=1$ then the answer is always 3 (both average and maximum): first all stations under 1 transmit (both A and C), then under 2 (same), then under 4 (just A – success).

Regarding the average (excepted value), it's a combination of two things: the average tries you need until any station transmits, and the expected value of a successful transmission assuming at least one station transmitted. The first is a standard geometric distribution, where the expected value is $E=1/p$.

  • $\begingroup$ could you elaborate on the calculation of the average? i am very much lost there and i don't want to teach mysrlf bad stuff. i've been struggling with it for a few weeks with no luck. it will help a lot $\endgroup$
    – Networking
    May 5, 2019 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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