注册并分享邀请链接,可获得视频播放与邀请奖励。

Max Resnick
@MaxResnick
Lead Economist @anza_xyz
加入 June 2020
1.4K 正在关注    19.3K 粉丝
The bandwidth latency tradeoff: Solana blocks are split into FEC sets, each of these sets is broadcast through rotor/turbine. Turbine splits FEC set into 32 pieces and then adds 32 more shreds containing erasure coding to form 64 shreds then sends each of these shreds out to the validator set through a specific randomly chosen turbine path. How long does it take for each FEC set to get from the leader to a specific validator over turbine? Because of erasure coding, the validator does not need every shred. It only needs enough distinct shreds to decode. In the simple 32-of-64 case, the leader sends 64 shreds, but a validator only needs any 32 of them. So the slowest 32 paths do not matter for decoding. We can model this mathematically: for validator i, define Lᵢ as the latency distribution induced by: leader → random root → validator i where the root is sampled according to stake. (this is technically rotor not turbine but its just a simplification, you can do the same trick for turbine but the equations are messier). Each shred samples one relay path from Lᵢ. So in the 32-of-64 case, validator i observes X₁,…,X₆₄ ∼ Lᵢ These are the arrival times of the 64 shreds. But the relevant arrival time is Bᵢ = X₍₃₂₎ the 32nd order statistic or the time when the 32nd fastest shred arrived, completing the FEC set. We can write the cumulative distribution of X₍₃₂₎ as: Pr[Bᵢ ≤ t] = ∑ⱼ₌₃₂⁶⁴ (64 choose j) Lᵢ(t)ʲ(1−Lᵢ(t))⁶⁴⁻ʲ More generally, if a slice has m data shreds and p coding shreds, then validator i sees X₁,…,Xₘ₊ₚ ∼ Lᵢ and can decode once m have arrived Bᵢ = X₍ₘ₎. This turns Turbine design into a quantile/bandwidth tradeoff. Let n = m+p and m/n → q. Then Bᵢ ≈ Lᵢ⁻¹(q) and by the CLT for order statistics, √n · (X₍ₘ₎ − Lᵢ⁻¹(q)) ⇒ N(0, q(1−q)/fᵢ(Lᵢ⁻¹(q))²) TLDR More coding shreds -> block arrives faster! With more large validators moving to larger NICs and XDP activated, should we crank up the fan out to make the leader handoff faster if it costs us some theoretical max throughput?
显示更多
0
15
68
12
转发到社区