264
правки
Изменения
м
→Анализ работы сети
== Анализ работы сети ==
Посторонним ключем будем называть ключ, находящийся в узле <tex>x</tex>, котороый при этом не будет отправлен ниже по дереву при переходе к следующему шагу. Посторонним ключем порядка <tex>r</tex> будем называть такой ключ, который останется посторонним, даже если его переместить в его предка, находящегося на <tex>r</tex> уровней выше по дереву.(По сути, посторонний ключ - посторонний ключ порядка ноль).
Далее мы докажем, что в момент времени <tex>t_f</tex> узлы на уровне <tex>\alpha(t_f) </tex> не содержат посторонних ключей порядка <tex>r</tex> для некоторой константы <tex>r</tex>, зависящей только от <tex>A, k, \nu</tex> Для этого рассмотрим следующее предположение
Для любого <tex> i = 0, 1, \dots , d </tex> и для любого <tex> r = 0, 1, \dots , d </tex> каждый узел на уровне <tex>i</tex> содержит менее чем <tex>\mu \delta^r c(i, t) </tex> посторонних ключей порядка <tex> r </tex>.
Так как <tex>c(\alpha(t_f), t_f) < 2 A^2 k^2 </tex>, то остается только проверить, что предположение выполняеся во время tex>t_f</tex> для некоторых <tex>\mu</tex> и <tex>\delta</tex> (зависящего только от <tex> i = 0, 1, \dots , d </tex>) ,такого, что <tex>\delta < 1 </tex>
<tex>(\dfrac{1}{k} + \dfrac{\mu\delta kA^2}{1 - \delta^2k^2A^2})c(i,t)</tex>
<tex> \dfrac{1}{k}(Nk^{-i} - c(i,t)) </tex>
<tex> \sum\limits_{j\ge 1} k^{2j-1}\mu\delta^{2j-1}c(i+2j, t) </tex>
<tex> \sum\limits_{j\ge 1} (k\delta)^{2j-1}c(i+2j, t) = c(i,t)\sum\limits_{j\ge 1} (k\delta)^{2j-1}A^{2j} < c(i,t)\dfrac{\delta k A^2}{1-\delta^2k^2A^2} </tex>
<tex>\dfrac{1}{k}Nk^{-i}</tex>
лемма 4.2
<tex>(\mu + (k - 1)\dfrac{\mu\delta k A^2}{1 - \delta^2k^2A^2} + \dfrac{A\nu k - 2A\nu + 1}{2k^2A^2} + \varepsilon_B)c(i,t)</tex>
<tex>c=c(i, t), \quad a=a(i,t),\quad \pi=\pi(i,t), \quad \chi=\chi(i, t) </tex>
<tex>\Delta_1 = \dfrac{\mu\delta kA^2}{1-\delta^2k^2A^2}c</tex>
<tex>\Delta_2 = \dfrac{\nu}{1 - \delta^2k^2A^2}c</tex>
dfrac
<tex> \Delta =
\begin{cases}
\Delta_1,&\text{ $i = \alpha(t) < \alpha(t+1)$,}\\
\Delta_2,&\text{ $i = \omega(t) < \omega(t+1)$,}\\
\Delta_1 + \Delta_2,&\text{если $\alpha(t) <i < \omega(t) \quad ||\quad i = \alpha(t) > \alpha(t + 1), t \ge 2$,}
\end{cases}
</tex>
<tex>(k - 1)\Delta - \dfrac{1}{2}\pi \le (k - 1)\Delta_1 + \dfrac{A\nu k - 2A\nu + 1}{2A^2k^2}c </tex>
лемма 4.3
<tex> \varepsilon^* \le \dfrac{\mu}{k},</tex>
<tex>(\mu + (k - 1)\dfrac{\mu\delta k A^2}{1 - \delta^2k^2A^2} + \dfrac{A\nu k - 2A\nu + 1}{2k^2A^2} + \varepsilon_B)\dfrac{1}{A\nu} + \mu\delta\dfrac{Ak}{\nu} \le \mu </tex>
Лемма 4.4
<tex>\mu \le \dfrac{\nu}{Ak^2}, </tex>
<tex>\mu\le\dfrac{1}{2}\delta_F\dfrac{A\nu k - 1}{A^2k^2},</tex>
<tex>\varepsilon_F\dfrac{1}{A\nu} + \delta^2\dfrac{Ak}{\nu} \le \delta </tex>
<tex>\dfrac{\pi(i,t)}{c(i,t)} \ge \dfrac{A\nu k - 1}{A^2k^2}</tex>
Лемма 4.5
<tex>\mu\delta^rc(\alpha(t_f),t_f) \le 1</tex>
== Мусор ==
