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

Операциональная интерпретация самостабилизации изображена на рис. 1. Часть (a) рисунка представляет собой неформальное представление поведения самостабилизирующейся системы, где по оси x отложено время, а по оси y – некоторая неформальная мера корректности. Кривая иллюстрирует траекторию движения системы через последовательность состояний во время выполнения. В начальном состоянии состояние системы некорректно; позже система входит в корректное состояние, затем возвращается в некорректное, а затем стабилизируется на неопределенный период, когда все состояния корректны. Этот период стабильности нарушается преходящим сбоем, который переводит систему в некорректное состояние, после чего повторяется описанный выше сценарий. Часть (b) рисунка иллюстрирует сценарий в терминах предикатов состояния. В рамке представлен предикат true, который характеризует все возможные состояния. Предикат C характеризует корректные состояния системы, а L С C представляет закрытый предикат правомерности. Достижение состояния в L соответствует вступлению в период стабильности в части (a). Пусть имеется алгоритм A с таким типом поведения. Мы говорим, что A самостабилизируется в L; когда L понимается неявно, это утверждение упрощается до выражения «A самостабилизируется».

Сложность самостабилизации оценивается путем измерения ресурса, необходимого для сходимости из произвольного начального состояния. Наиболее широко в литературе по самостабилизации применяются метрики времени сходимости и объема памяти в наихудшем случае, необходимые решающему данную задачу алгоритму. Кроме того, для реактивных самостабилизирующихся алгоритмов оцениваются метрики для стабильного поведения алгоритма, то есть начиная с его правомерного состояния, и сравниваются с нестабилизирующимися алгоритмами, чтобы измерить затраты на самостабилизацию.

== Основные результаты ==