Изменения

Перейти к: навигация, поиск

Самостабилизирующиеся алгоритмы

2182 байта добавлено, 4 июнь
Нет описания правки
[[Категория: Параллельное программирование]]
{{Определение
|definition=
== Поиск остовного дерева ==
Такая задача возникает, например, в internet of things: набросали с вертолёта на поле размером 3км*3км много хрупких устройств со слабыми антеннами, которым надо соединиться в единую сеть. При этом топология связи там неполная и половина устройств подохла.
А мы хотим построить дерево, чтобы узлы могли друг с другом общаться (а не каждый каждому передавать, потому что тогда надо бороться с циклами).
 
Решение начинается с инициатора (например, узел, которому надо что-нибудь узнать про всех остальных), которому это дерево нужно.
 
Каждый узел поддерживает у себя $d$ (расстояние до корня) и $p$ (узел-предок в дереве).
Корень всегда ставит у себя $d=0$ и $p=-1$, а остальные узлы в постоянном режиме делают:
* Найти соседа $j$ с минимальным $d_j$
* Установить его в качестве своего родителя и $d_i=d_j+1$
 
Тогда корень стабилизируется сразу, узлы, которым корень виден, стабилизируются через одну итерацию, их соседи — через две, и так далее.
 
Если какой-нибудь узел выпадает, то его дети найдут себе кого-нибудь ещё и снова встроятся в дерево.
 
Единственная проблема — если умирает корень, но тогда узнавший об этом узел может инициировать перестроение дерева (если у нас цель — связь).
292
правки

Навигация