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

Теорема 1 (теорема о справедливой композиции [4]). Положим, что <math>A_i</math> самостабилизируется на <math>\mathcal{L}_i</math> в предположении, что все переменные в <math>X_i</math> остаются константными на протяжении любого выполнения; тогда <math>A_0 [] A_1 [] \cdot \cdot \cdot [] A_{m - 1}</math> самостабилизируется на <math>\{ \mathcal{L} \}^{m - 1}_{i = 0}</math>.

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

Одним из открытий, сделанных в ходе исследования самостабилизирующихся графовых алгоритмов, является разница между алгоритмами, которые завершают работу, и теми, которые постоянно меняют состояние даже после того, как выходные результаты становятся стабильными. Рассмотрим задачу построения остовного дерева с корнем в процессе r. Некоторые алгоритмы самостабилизируются до получения свойства, заключающегося в том, что для каждого p ф r переменная up ссылается на родителя p в остовном дереве, и состояние остается неизменным. Другие алгоритмы являются самостабилизирующимися протоколами для циркуляции маркеров с тем побочным эффектом, что маршрут циркуляции маркеров устанавливает остовное дерево. Первый тип алгоритмов требует O(lg n) памяти на процесс, тогда как второй – O(lgi5), где S – степень (число соседей) процесса. Это различие было формализовано в понятии молчаливых алгоритмов, которые со временем перестают изменять какое бы то ни было значение связи; в [5] для модели регистра связей было показано, что молчаливые алгоритмы для многих графовых задач требуют £?(lg n) памяти.