Самостабилизация: различия между версиями

Одним из открытий, сделанных в ходе исследования самостабилизирующихся графовых алгоритмов, является разница между алгоритмами, которые завершают работу, и теми, которые постоянно меняют состояние даже после того, как выходные результаты становятся стабильными. Рассмотрим задачу построения остовного дерева с корнем в процессе r. Некоторые алгоритмы самостабилизируются до получения свойства, заключающегося в том, что для каждого <math>p \ne r</math> переменная <math>u_p</math> ссылается на родителя p в остовном дереве, и состояние остается неизменным. Другие алгоритмы являются самостабилизирующимися протоколами для циркуляции маркеров с тем побочным эффектом, что маршрут циркуляции маркеров устанавливает остовное дерево. Первый тип алгоритмов требует <math>O(lg \; n)</math> памяти на процесс, тогда как второй – <math>O(lg \; \delta)</math>, где <math>\delta</math> – степень (число соседей) процесса. Это различие было формализовано в понятии ''молчаливых'' алгоритмов, которые со временем перестают изменять какое бы то ни было значение связи; в [5] для модели регистра связей было показано, что молчаливые алгоритмы для многих графовых задач требуют <math>\Omega(lg \; n)</math> памяти.

Общая проблема построения самостабилизирующегося алгоритма для входной нереактивной задачи может быть решена с помощью стандартных инструментов распределенных вычислений: моментальный снимок, трансляция, сброс состояния системы и синхронизация – эти задачи являются конструктивными блоками, позволяющими непрерывно проверять глобальное состояние (в некоторых удачных случаях <math>\mathcal{L}</math> можно локально проверить и исправить). Эти конструктивные блоки имеют самостабилизирующиеся решения, что позволяет использовать общий подход.