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

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

Задача [3]. Первая формулировка задачи самостабилизации, предложенная Дейкстрой, представляет собой кольцо из n процессов с номерами от 0 до n - 1. Обозначим состояние процесса i как x[i]. Коммуникация в кольце однонаправленная с использованием ''модели совместно используемого состояния''. Атомарный шаг процесса i может быть выражен защищенным назначением вида <math>g(x[i \ominus 1], x[i]) \to x[i]: = f(x[i \ominus 1], x[i])</math>. Здесь <math>\ominus</math> - это вычитание по модулю n, так что <math>x[i \ominus 1]</math> представляет собой состояние предыдущего процесса в кольце по отношению к процессу i. Защищенное присваивание g – это булево выражение; если <math>g(x[i \ominus 1], x[i])</math> ''истинно'', то процесс i считается ''привилегированным'' (или включенным). Таким образом, за один атомарный шаг привилегированный процесс i считывает состояние предыдущего процесса и вычисляет новое состояние. Планирование выполнения контролируется ''центральным демоном'', который справедливым образом выбирает один из всех разрешенных процессов для выполнения следующего шага. Задача заключается в выводе g и f таким образом, чтобы независимо от начальных состояний <math>x[i], 0 \le i < n</math>, в конечном итоге оставалась одна привилегия, и каждый процесс пользовался привилегией бесконечно часто.

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