Суперстабилизация

Суперстабилизация — это концепция отказоустойчивости в распределенных вычислениях . Суперстабилизирующие распределенные алгоритмы сочетают в себе черты самостабилизирующихся и динамических алгоритмов . Суперстабилизирующий алгоритм, как и любой другой самостабилизирующийся алгоритм, можно запустить в произвольном состоянии, и в конечном итоге он придет к допустимому состоянию. восстанавливается Кроме того, алгоритм суперстабилизации быстро после одного изменения в топологии сети (добавление или удаление одного ребра или узла в сети).

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

Определения

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

Время суперстабилизации — это время восстановления после одного изменения топологии. Предполагается, что изначально система находится в допустимой конфигурации. Затем топология сети меняется; время суперстабилизации — это максимальное время, которое требуется системе, чтобы снова достичь допустимой конфигурации. Аналогично, мерой корректировки является максимальное количество узлов, которые должны изменить свое состояние после таких изменений.

«Почти легитимные конфигурации», возникающие после одного изменения топологии, можно формально смоделировать с помощью предикатов перехода : предикат перехода — это предикат, который сохраняется после однократного изменения топологии сети, а также во время сходимости к легитимной конфигурации.

Ссылки

• Долев, Шломи ; Герман, Тед (1997), «Суперстабилизирующие протоколы для динамических распределенных систем» , Чикагский журнал теоретической информатики , 3 : 1–40, doi : 10.4086/cjtcs.1997.004 , статья 4.
• Долев, Шломи (2000), Самостабилизация , MIT Press , ISBN  0-262-04178-2 , Раздел 7.1.