Slotted ALOHA P(All nodes successful @ time t)

[testietester]

I'm trying to understand slotted ALOHA and I have a question regarding the probabilities.

Here is an example: I have 3 nodes, ready to send a frame each. The probability of them sending = 0.5. What is the probability that at time 3 (3 time slots later) they will have all been successful? I know that: P(given node successful) = p(1-p)^(N-1) P(any node successful) = Np(1-p)^(N-1)

I have a couple versions of the answer and I'm not sure which one is correct(or none at all):

1) P(node 1 success) + P(node 2 " ") + P(node 3 " ") = 3*[0.5(1-0.5)^(3-1)] = 3/8

OR

2) P(1 node successful) * P(next node " ") * P(last node " ") = 3(0.5)(0.5)^(3-1) * 2(0.5)(0.5)^(2-1) * 1(0.5)(0.5)^(1-1)

I'm leaning towards version 2 of my answer, but I don't see how to extend it to t = 4.

I don't remember much from my discrete math days. But I'm leaning towards the first one(or a variation of the first one). Please help me clear this up.

Thanks for looking!

In case you didn't know slotted ALOHA works like this:
You have nodes, ready to send "frames" of data. They send every time slot, but when more than one node sends on the same time slot there is a collision and the frames don't make it to its destination. That is why every node sends at the beginning of every time slot based on a certain probability. If there is another crash, the nodes involved resend their frames based on probability p. This continues until eventually only 1 frame is expressed on a time slot, and it is sent successfully.

 

[Stephen Tashi]

If the nodes are numbered 1,2,3 then you can consider all possible orders in which they succeed. There are 3! = (3)(2)(1)=6 possible orders. For each order (such as 2,1,3) the probability of that sequence of successes is the same. Its p(1-p)(1-p) p(1-p)(1-p) p(1-p)(1-p). (For example, if you wrote the factors for the sequence of successes 2,1,3 in order, they would be ((1-p)p(1-p)) ((p)(1-p)(1-p)) ((1-p)(1-p)p) and these factors can be rearranged.) The probability of success is the sum of the probabilities of success in particular ways, so it is 3! (p(1-p)(1-p))^3.

When you say "extend to t=4", do you mean to extend both the number of nodes and the number of time steps?

 

[testietester]

@ Stephen Tashi

Thanks for the reply. By t=4 I mean the time slots have been extended to 4. There are still 3 nodes with a frame to send. But, we now have 4 time slots to get them all sent.

Because failures can happen because of collisions, or simply because nodes choose not to send(they send with probability p) I would have to OR(add) in the cases where the first slot empty, 2nd slot empty, and 3rd slot empty. The 1 and 2 slot can be empty due to collisions/choosing not to send. But the only way for the 3rd to be empty is just choosing not to send. I think...

Also, why is it p(1-p)(1-p)? Plugging in p=0.5 gives 3!(0.5(0.5)(0.5))^3 = 0.01171875. Seems a little low.

Thanks again!

 

[Stephen Tashi]

Also, why is it p(1-p)(1-p)?

What do you mean by "it"? p(1-p)(1-p) represents the probability of one node transmitting in a time slot and the other two being quiet.

Plugging in p=0.5 gives 3!(0.5(0.5)(0.5))^3 = 0.01171875. Seems a little low.

I don't know what you are comparing this number to. I glanced at documents on the web that analyze "slotted ALOHA" and they analyze it as a continuous process, not as a synchronous process that proceeds in time steps. So your analysis isn't an analysis of what the web calls "slotted ALOHA".