Изменения
→Конструкция сети
Что касается перемещения значений в дереве, то в момент времени <tex>t = 0</tex> все <tex>k^d</tex> проводов входят в корень. Между временами <tex> t</tex> и <tex>t + 1</tex> каждый узел <tex>x</tex>, в который входят какие-нибудь провода, использует эти а проводов как вход для сепаратора, с разумно выбранным размером для выходных блоков. Провода из каждого выходного блока <tex>B_j</tex> посывлаются в <tex>j</tex>того сына узла <tex>x</tex>а провода попавшие в <tex>F_1</tex> или <tex>F_2/tex> посылаются обратно к родителю <tex>x</tex>. (Если <tex>x</tex>. - корень, то <tex>F_1</tex> и <tex>F_2</tex> должны быть пустыми. Так как <tex>F_1</tex> и <tex>F_2</tex> сравнительно маленькие, то большинство значений провалится ниже к листам дерева; так как сепаратор не идеальный, то некоторые ключи могут быть посланы вниз в неправильном направлениии. Свойство 1) гарантирует, что очень малое количество собъется с пути, а свойство 2) гарантирует, что большинство из этих ключей вернутся назад и смогут исправить свое положение позже.
== Конструкция сети ==
Пускай число детей у каждой вершины <tex>k</tex> будет степенью двойки, и число входных ключей - <tex> N = k ^ d </tex>. В любой момент времени <tex>t</tex> все <tex>N</tex> проводов распределены внутри дерева таким образом, что число проводов, содержащихся в вершине <tex>x</tex> зависит только от времени <tex>t</tex> и глубины <tex>i</tex> на которой находится вершина <tex>x</tex>. Тогда пускай <tex>a(i, t)</tex> будет описывать это число. Значение <tex>a(i, t)</tex> зависит от двух параметров <tex>A</tex> и <tex>\nu</tex>, таких, что <tex>\nu < 1 </tex> и <tex>A\nu > 1</tex>
В самом начале, число проводов, входящих в корень :
<tex>a(0, 0) = N</tex>
При переходе к <tex>t = 1</tex> корень делит <tex>N</tex> проводов на <tex>k</tex> групп и отправляет их своим <tex> k </tex> детям:
<tex>a(1, 1) = N/ k</tex>
При переходе к <tex>t = 2</tex> каждый узел, находящийся на 1 уровне отправляет <tex>N\nu / Ak^2 </tex> своих <tex>N/k</tex> проводов обратно в корень и распределяет оставшиеся провода равномерно среди детей :
<tex> a(0, 2) = \dfrac{\nu}{Ak}N</tex>
<tex> a(2, 2) = \dfrac{Ak - \nu}{Ak^3}N</tex>
Обозначим <tex>\alpha (t)</tex> и <tex>\omega (t)</tex> - верхний и нижний уровни, соответственно, такие что на на них содержатся непустые узлы на момент времени <tex>t</tex>. Иначе говоря, <tex>\alpha (t)</tex> - это наименьшее <tex>i</tex>, такое что
<tex>a(i, t) \neq 0</tex>, а <tex>\omega (t)</tex> - это наибольшее <tex>i</tex>, такое что
<tex>a(i, t) \neq 0</tex>
Так получаем, что
<tex>\alpha (0) = \omega (0) = 0; \quad \alpha (1) = \omega (1) = 1; \quad \alpha (2) = 0 \omega (2) = 2; </tex>
Значения <tex>\alpha (t)</tex> и <tex>\omega(t)</tex> расходятся в момент <tex>t = 2</tex>и сойдутся, когда перемещение значений по сети и их сортировка будет окончена.
Запишем
<tex>\alpha^*(t) = \dfrac{t\log \dfrac{1}{\nu} - \log N + \log(2A\nu k^3)}{\log A}</tex>
и
<tex>\omega^*(t) = \dfrac{t\log \dfrac{1}{\nu} + \log(A\nu k)}{\log Ak}</tex>
Пускай <tex>\alpha(t)</tex> будет наименьшим неотрицательным челым числом, таким что
<tex>\alpha(t) \ge \alpha^*(t),\quad \alpha (t)\equiv t\mod 2 </tex> Пускай <tex>\alpha(t)</tex> будет наименьшим челым числом, таким что <tex>\omega(t) \ge \omega^*(t),\quad \omega (t)\equiv t\mod 2 </tex> Поскольку <tex>A\nu \ge 1 </tex> получаем, что <tex>\alpha^*(t + 1) \le \alpha^* (t) + 1, \omega^*(t + 1) \le \omega^*(t) </tex> для любого <tex>t</tex> и поэтому <tex> |\alpha(t + 1) - \alpha(t) | = 1, \quad |\omega(t + 1) - \omega(t)| = 1 </tex> для любого <tex>t</tex>.<tex> \alpha(t) < \omega(t)</tex> <tex> 1 < t < t_f </tex> <tex> \alpha(t_f) = omega(t_f) </tex> <tex> c(i, t) = \dfrac{N}{A\nu k} A^i\nu ^i </tex> <tex> \dfrac{a(\alpha(t), t)}{c(\log alpha(t), t)} = 1 </tex>,<tex> \dfrac{a(i, t)}{c(i, t)} = 1 - \dfrac{1}{A^2 k^2} </tex> <tex> \alpha(t) < i < \omega(t) </tex> <tex> i \equiv t \mod 2 </tex> <tex> a(\omega(t),t) = Nk ^{-\nuomega(t)} + - dfrac{c(\logomega(t), t)}{A^2k^2}</tex> <tex> i \nu not\equiv t \mod 2</tex> <tex> a(i, t) = 0 <tex> <tex> N k^{-\omega(t)}\le c(\omega(t), t) < A^2k^2Nk^{-\log Akomega(t)}), </tex>
<tex> 0 < \dfrac{a(\omega(t), t)}{c(\omega(t), t)} \le 1 - \dfrac{1}{A^2k^2} </tex>
<tex>c(\omegaalpha(t), t) \ge \omega2k^*2 /tex> <tex>c(i, t),\quad ge 2A^2k^2 </tex> <tex>i\ge \omegaalpha(t)\equiv t\mod + 2 </tex>
