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

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

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

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

Общая проблема построения самостабилизирующегося алгоритма для входной нереактивной задачи может быть решена с помощью стандартных инструментов распределенных вычислений: моментальный снимок, трансляция, сброс состояния системы и синхронизация – эти задачи являются конструктивными блоками, позволяющими непрерывно проверять глобальное состояние (в некоторых удачных случаях L можно локально проверить и исправить). Эти конструктивные блоки имеют самостабилизирующиеся решения, что позволяет использовать общий подход.