4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
Строка 63: | Строка 63: | ||
'''Теорема 4. Когда «голова» подмножества поддержки движется по регулярному остовному подграфу G, ожидаемое время встречи A (или B) и узла поддержки не может быть меньше <math>(n - 1)^2 / 2m</math>. Поскольку <math>m = \Theta(n)</math>, нижняя граница ожидаемого времени передачи равна <math>\Theta(n)</math>. В этом смысле ожидаемое время передачи посредством протокола | '''Теорема 4. Когда «голова» подмножества поддержки движется по регулярному остовному подграфу G, ожидаемое время встречи A (или B) и узла поддержки не может быть меньше <math>(n - 1)^2 / 2m</math>. Поскольку <math>m = \Theta(n)</math>, нижняя граница ожидаемого времени передачи равна <math>\Theta(n)</math>. В этом смысле ожидаемое время передачи посредством протокола «змея» является оптимальным для размера подмножества поддержки, составляющего <math>\Theta(n)</math>.''' | ||
Строка 79: | Строка 79: | ||
'''Теорема 6. Протокол координации движения типа | '''Теорема 6. Протокол координации движения типа «змея» является 1-отказоустойчивым.''' | ||
== Применение == | == Применение == |
правок