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

Сети коммуникаций обычно представляются моделями в виде графов, и потребность в распределенных графовых алгоритмах, устойчивых к преходящим сбоям, стимулирует изучение таких задач. В этой области получены такие результаты, как самостабилизирующиеся алгоритмы для остовных деревьев, поиск центра, поиск паросочетаний, проверка на планарность, раскраска, нахождение независимых множеств и другие. В общем случае все графовые задачи могут быть решены при помощи самостабилизирующихся алгоритмов: задачи, которые имеют на входе топологию сети и, возможно, связанные с ней коэффициенты, такие как веса ребер, и определяют выходные данные как функцию от входных, могут быть решены общими методами самостабилизации. Эти общие методы требуют значительных затрат времени и памяти, а также могут использовать более сильные предположения при моделировании, чем требуется для конкретных задач – например, уникальные идентификаторы процессов и предполагаемое ограничение на диаметр сети. Поэтому исследования алгоритмов на графах продолжаются.

Одним из открытий, сделанных в ходе исследования самостабилизирующихся графовых алгоритмов, является разница между алгоритмами, которые завершают работу, и теми, которые постоянно меняют состояние даже после того, как выходные результаты становятся стабильными. Рассмотрим задачу построения остовного дерева с корнем в процессе 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> можно локально проверить и исправить). Эти конструктивные блоки имеют самостабилизирующиеся решения, что позволяет использовать общий подход.