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

Многие самостабилизирующиеся протоколы имеют многослойную конструкцию. Обозначим за <math>\{ A_i \}^{m - 1}_{i = 0}</math> множество программ, обладающих следующим свойством: для каждой переменной состояния x, если программа <math>A_i</math> записывает x, то ни одна программа <math>A_j</math> для j > i не записывает x. Программы в <math>\{ A_j \}^{m - 1}_{j = i + 1}</math> могут читать переменные, записанные <math>A_i</math>, то есть использовать выходное значение <math>A_i</math> в качестве входа. Справедливая композиция программ B и C, записываемая в виде B [] C, предполагает справедливое планирование шагов B и C. Обозначим за <math>X_j</math> множество переменных, прочитанных <math>A_j</math> и, возможно, записанных <math>\{ A_i \}^{m - 1}_{i = 0}</math>.

Один из вопросов, связанных с проблемой, поставленной в разделе «Постановка задачи», заключается в том, может ли существовать ''равномерное'' решение, в котором все процессы имеют одинаковые алгоритмы. Результат Дейкстры для однонаправленного кольца представляет собой квазиравномерное решение (все процессы, кроме одного, имеют одинаковый алгоритм), использующее n состояний на процесс. Состояние каждого процесса – это счетчик: процесс 0 увеличивает счетчик по модулю k, где <math>k \ge n</math> достаточно для сходимости; остальные процессы копируют счетчик предыдущего процесса в кольце. В правомерном состоянии каждый раз, когда процесс 0 увеличивает счетчик, полученное значение отличается от значений всех остальных счетчиков в кольце. Этот кольцевой алгоритм оказывается самостабилизирующимся для ''распределенного демона'' (любое подмножество привилегированных процессов может выполняться параллельно), когда к > n. Последующие исследования установили, что взаимное исключение на однонаправленном кольце занимает <math>\Theta(1)</math> места на процесс для неравномерного решения. Детерминированные равномерные решения этой задачи в общем случае невозможны, кроме исключительного случая, когда n является простым. Известны рандомизированные равномерные решения для произвольного n, требующие <math>O(lg \; \alpha)</math> памяти, где <math>\alpha</math> – наименьшее число, не делящее n. Некоторые нижние границы памяти для равномерных решений получены в [7]. Временная сложность алгоритма Дейкстры составляет <math>O(n^2)</math> раундов, и было показано, что некоторые рандомизированные решения имеют ожидаемое время сходимости <math>O(n^2)</math>.

Дейкстра также представил решение проблемы взаимного исключения для линейного массива процессов, используя O(1) памяти на процесс [3]. Позже этот результат был обобщен на корневое дерево процессов, но при этом взаимное исключение было ослаблено до наличия одной привилегии на любом пути от корня до листа. Последующие исследования развили эту тему, показав, что задачи распределенных вычислений распространения волны имеют самостабилизирующиеся решения. Также были решены задачи синхронизации фазы и синхронизации часов. Пример самостабилизирующегося взаимного исключения в многопроцессорной модели совместно используемой памяти см. в работе [9].