6

I'm reading the white-paper about the tangle. In pages 8 to 10, the author is calculating the average time for first approval of a tip on a stationary tangle.

The first result is that under low load:

The first approval happens on an average timescale of order λ −1

where λ is the rate of arrival of new transactions. This result is clear to me.

But I must be missing something (maybe obvious) when the author present the result for a tangle under heavy load (page 10):

Let us now consider the high load regime, the case where L0 is large. As mentioned above, one may assume that the Poisson flows of approvals to different tips are independent and have an approximate rate of 2λ/L0. Therefore, the expected time for a transaction to receive its first approval is around L0/(2λ) ≈ 1.45h (1)

Where:

  • L0 is the number of tips (large under heavy load).
  • h is the average hidden time of a transaction (a transaction is hidden during the execution of the pow)

I don't see from where comes this factor: 1.45

I looked into reference "Sheldon M. Ross (2012) Introduction to Probability Models. 10th ed." (page 312) to have better understanding of the Poisson Process, but it didn't help me to understand why we obtain this result.

2

1/ln2 from equation (3) in page 8. (in version 1.2 of the whitepaper)

  • my version of white paper is 1.2 dated August 22, 2017 whereas your version is 1.3. Please check the equation 3 in version 1.2. – Casey Yeow Apr 3 '18 at 20:55
  • thanks for clarification about the version of the white paper. Wording in this section are very different. I hope that after reading both, I will eventually understand more deeply the math. Here is the link to old versions : untangled.world/iota-whitepaper-tangle – ben75 Apr 5 '18 at 17:52
  • L0/(2λ) ≈ 1.45h in v1.2, L0/(2λ) should be ≈ h in v1.3. I think they forgot to update. BTW, any idea in v1.3 pg8, why the mean number of chosen tips is 2r/(r+λh) ? And why equal to 1? Thx in advance. – Casey Yeow Apr 6 '18 at 12:10
  • Just discovered in pg 8 of v1.3 near last paragraph: "the expected time for a transaction to be approved for the first time is approximately h+L0/2λ = 2h". But then in pg 10: "Therefore, the expected time for a transaction to receive its first approval is around L0/2λ ≈ 1:45h (1)". which then should be ≈ h. Thus, it is very confusing! I don't know which statement is correct?! – Casey Yeow Apr 7 '18 at 4:31
  • @instantlink: Why is it that "the Poisson flow of approvals to it has rate approximately 2λ/L0" ? This statement followed with "(Recall Proposition 5.3 of [11], which says that if we independently classify each event of a Poisson process according to a list of possible subtypes, then the processes of events of each subtype are independent Poisson processes.)" I have checked eqn 5.3 of [11], it only shows memoryless property of exponential random variable. How they derived the rate = 2λ/L0 ? – Casey Yeow Apr 8 '18 at 14:39
2

r/(r+λh) is a mean value ( < 1 ) r is tips before time [t-h] r+λh is a slightly higher number adding all tips from time interval [t-h,t]

since the node does not know λh tips are no tips any more at time index t (assuming λh is always stationary value), we have a total probability of choosing a tip of r/(r+λh) ( < 1 )

Total mean number of chosen tips is then 2*r/(r+λh) - you always select 2 tips. Why this is equal to 1 in a stationary regime I also do not fully understand. I assume that the r number of tips and the λh number of tips should be equal (half/half for instance) and then a new addition of one transaction would not change it by much at that very moment - so resulting in 1 quotient. Anyone can confirm this interpretation?

What remains unclear after comments issued in other posts: Why is the time for 1st approval L0/(2λ) ≈ 1.45h (or lets say ≈ h as in version 1.3 of paper)?

Paper states that during a period of h a transaction cannot be approved.

This is because, by our assumption, during the first h units of time a transaction cannot be approved, and after that the Poisson flow of approvals to it has rate approximately 2λ/L0.

So it should it total be the sum of h + L0/(2λ) ≈ 2h

I think white paper needs an update on this. Moreover the link to the equation L0/(2λ) ≈ 1.45h (1) is wrong in v1.3

1

Expected increment of # of tips at time t is: 1 - 2*r/(r+λh) .....eqn(1) where "1" refers to new tip created by the tx and "2*r/(r+λh)" refers to expected # of "erased" tips. If the two "erased" tips were already approved (usually for small L(t)), then "2*r/(r+λh)" = 0, thus eqn(1) becomes positive or increasing.
If the two "erased" tips were not previously approved (usually for large L(t)), then "2*r/(r+λh)" = 2, thus eqn(1) becomes negative or decreasing.
If one "erased" tip was already approved and one not previously approved (for L(t) becomes stationary or L0), then "2*r/(r+λh)" = 1, thus eqn(1) becomes zero, neither increasing nor decreasing. Thus L(t)=L0, eqn(1) = 0; 1-2*r/(r+λh) = 0; therefore 2*r/(r+λh) = 1.

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.