Самостабилизация — это концепция отказоустойчивости в распределенных системах . При любом начальном состоянии самостабилизирующаяся распределенная система придет в правильное состояние за конечное число шагов выполнения .
На первый взгляд, гарантия самостабилизации может показаться менее многообещающей, чем гарантия более традиционной отказоустойчивости алгоритмов, которые стремятся гарантировать, что система всегда остается в правильном состоянии при определенных видах переходов состояний. Однако эта традиционная отказоустойчивость не всегда может быть достигнута. Например, ее нельзя достичь, когда система запущена в неправильном состоянии или повреждена злоумышленником. Более того, из-за их сложности очень трудно отлаживать и анализировать распределенные системы. Следовательно, очень трудно предотвратить достижение распределенной системой неправильного состояния. Действительно, некоторые формы самостабилизации включены во многие современные компьютерные и телекоммуникационные сети, поскольку это дает им возможность справляться с ошибками, которые не были предусмотрены при проектировании алгоритма.
Спустя много лет после основополагающей статьи Эдсгера Дейкстры в 1974 году эта концепция остается важной, поскольку она представляет собой важную основу для самоуправляемых компьютерных систем и отказоустойчивых систем . В результате статья Дейкстры получила премию ACM PODC Influential-Paper Award 2002 года , одно из самых высоких признаний в сообществе распределенных вычислений. [1] Более того, после смерти Дейкстры награда была переименована и теперь называется премией Дейкстры.
EW Dijkstra в 1974 году представил концепцию самостабилизации, что побудило к дальнейшим исследованиям в этой области. [2] Его демонстрация включала представление самостабилизирующихся алгоритмов взаимного исключения . [3] Она также показала первые самостабилизирующиеся алгоритмы, которые не полагались на строгие предположения о системе. Некоторые предыдущие протоколы, используемые на практике, действительно стабилизировались, но только предполагая существование часов, которые были глобальными для системы, и предполагая известную верхнюю границу продолжительности каждого системного перехода. Только десять лет спустя, когда Лесли Лэмпорт указал на важность работы Дэйкстры на конференции 1983 года под названием «Симпозиум по принципам распределенных вычислений », исследователи [4] обратили свое внимание на эту элегантную концепцию отказоустойчивости. В своем докладе Лэмпорт заявил:
Я считаю это самой блестящей работой Дейкстры — по крайней мере, его самой блестящей опубликованной работой. Она почти совершенно неизвестна. Я считаю это вехой в работе по отказоустойчивости... Я считаю самостабилизацию очень важной концепцией в отказоустойчивости и очень плодородной областью для исследований. [3]
Впоследствии работа Дейкстры была удостоена премии ACM-PODC influencer paper award, которая затем стала премией Дейкстры в области распределенных вычислений от ACM (Ассоциации вычислительной техники), вручаемой на ежегодном симпозиуме ACM-PODC. [5]
Распределенный алгоритм является самостабилизирующимся, если, начиная с произвольного состояния, он гарантированно сходится к законному состоянию и остается в законном наборе состояний после этого. Состояние является законным, если, начиная с этого состояния, алгоритм удовлетворяет своей спецификации. Свойство самостабилизации позволяет распределенному алгоритму восстанавливаться после временной неисправности независимо от ее природы. Более того, самостабилизирующийся алгоритм не нужно инициализировать, поскольку он в конечном итоге начинает вести себя правильно независимо от своего начального состояния.
В статье Дейкстры, в которой вводится концепция самостабилизации, представлен пример в контексте «маркерного кольца» — сети компьютеров, упорядоченных по кругу. Здесь каждый компьютер или процессор может «видеть» все состояние одного процессора, который непосредственно ему предшествует, и что это состояние может подразумевать, что процессор «имеет маркер» или «не имеет маркера». [5] [6] Одним из требований является то, что ровно один из них должен «держать маркер» в любой момент времени. Второе требование предписывает, чтобы каждый узел «передавал маркер» компьютеру/процессору, следующему за ним, так что маркер в конечном итоге циркулирует по кольцу. [5] [6]
Первые самостабилизирующиеся алгоритмы не обнаруживали ошибки явно, чтобы впоследствии исправить их. Вместо этого они постоянно подталкивали систему к законному состоянию. Поскольку традиционные методы обнаружения ошибки [7] часто были очень сложными и отнимали много времени, такое поведение считалось желательным. (Метод, описанный в цитируемой выше статье, собирает огромное количество информации со всей сети в одно место; после этого он пытается определить, является ли собранное глобальное состояние правильным; даже это определение само по себе может быть сложной задачей).
Совсем недавно исследователи представили новые методы легкого обнаружения ошибок для самостабилизирующихся систем с использованием локальной проверки. [8] [9] и для общих задач. [10]
Термин «локальный» относится к части компьютерной сети. При использовании локального обнаружения компьютеру в сети не требуется взаимодействовать со всей сетью для обнаружения ошибки — ошибка может быть обнаружена, если каждый компьютер будет взаимодействовать только со своими ближайшими соседями. Эти методы локального обнаружения значительно упростили задачу разработки самостабилизирующихся алгоритмов. Это связано с тем, что механизм обнаружения ошибок и механизм восстановления могут быть разработаны отдельно. Более новые алгоритмы, основанные на этих методах обнаружения, также оказались намного более эффективными. Более того, в этих работах были предложены довольно эффективные общие преобразователи для преобразования несамостабилизирующихся алгоритмов в самостабилизирующиеся. Идея заключается в том, чтобы,
Комбинация этих 4 частей является самостабилизирующейся (при условии отсутствия срабатывания неисправности во время фаз коррекции неисправности, например, [11] ). Первоначальные самостабилизирующиеся протоколы также были представлены в вышеуказанных работах. Более эффективные протоколы сброса были представлены позже, например, [12]
Дополнительная эффективность была введена с понятием адаптивных ко времени протоколов. [13] Идея, лежащая в основе этого, заключается в том, что когда происходит только небольшое количество ошибок, время восстановления может (и должно) быть сокращено. Оригинальные алгоритмы самостабилизации Дейкстры не обладают этим свойством.
Полезным свойством самостабилизирующихся алгоритмов является то, что они могут быть составлены из слоев, если слои не проявляют никаких циклических зависимостей . Время стабилизации композиции тогда ограничено суммой индивидуальных времен стабилизации каждого слоя. [6]
Позднее появились новые подходы к работе Дейкстры, такие как случай Кшиштофа Апта и предложения Эхсана Шоджи, которые продемонстрировали, как самостабилизация может быть естественным образом сформулирована с использованием стандартных концепций стратегических игр, в частности концепции пути улучшения. [14] Эта конкретная работа стремилась продемонстрировать связь между самостабилизацией и теорией игр.
Временная сложность самостабилизирующегося алгоритма измеряется в (асинхронных) раундах или циклах.
Для измерения времени стабилизации выходных данных подмножество переменных состояния определяется как видимое извне ( выходные данные ). Определенные состояния выходных данных определяются как правильные (легитимные). Набор выходных данных всех компонентов системы считается стабилизированным в момент, когда он начинает быть правильным, при условии, что он остается правильным неопределенно долго, если только не произойдут дополнительные сбои. Время стабилизации выходных данных — это время (количество (асинхронных) раундов ), пока выход не стабилизируется. [8]
Система является самостабилизирующейся тогда и только тогда, когда:
Система называется рандомизированной самостабилизирующейся тогда и только тогда, когда она самостабилизируется и ожидаемое количество раундов, необходимых для достижения правильного состояния, ограничено некоторой константой . [15]
Хорошо известно, что проектирование самостабилизации в вышеупомянутом смысле является сложной работой. Фактически, класс распределенных алгоритмов не обладает свойством локальной проверки: легитимность состояния сети не может быть оценена одним процессом. Наиболее очевидным случаем является кольцо токенов Дейкстры, определенное выше: ни один процесс не может определить, является ли состояние сети легитимным или нет, в случае, когда в несоседних процессах присутствует более одного токена. Это говорит о том, что самостабилизация распределенной системы является своего рода коллективным интеллектом , где каждый компонент предпринимает локальные действия, основываясь на своих локальных знаниях, но в конечном итоге это гарантирует глобальную конвергенцию в конце.
Чтобы помочь преодолеть трудности проектирования самостабилизации, как определено выше, были разработаны другие типы стабилизации. Например, слабая стабилизация — это свойство, при котором распределенная система имеет возможность достичь своего законного поведения из каждого возможного состояния. [16] Слабую стабилизацию легче проектировать, поскольку она просто гарантирует возможность сходимости для некоторых запусков распределенной системы, а не сходимость для каждого запуска.
Самостабилизирующийся алгоритм молчит тогда и только тогда, когда он сходится к глобальному состоянию, в котором значения регистров связи, используемых алгоритмом, остаются фиксированными. [17]
Расширением концепции самостабилизации является концепция суперстабилизации . [18] Целью здесь является работа с динамическими распределенными системами, которые подвергаются топологическим изменениям. В классической теории самостабилизации произвольные изменения рассматриваются как ошибки, при которых не дается никаких гарантий, пока система снова не стабилизируется. В суперстабилизирующихся системах существует предикат перехода , который всегда выполняется, пока топология системы перенастраивается.
Теория, которая началась в области самостабилизации, проверяет (распределенным образом), что совокупность состояний узлов в сети подчиняется некоторому предикату. Эта теория вышла за рамки самостабилизации и привела к таким понятиям, как «распределенный NP» (распределенная версия NP (сложности) ), распределенное нулевое знание (распределенная версия нулевого знания ) и т. д. Премия Международного коллоквиума по структурной информационной и коммуникационной сложности (SIRROCO) за инновации в распределенных вычислениях 2024 года была присуждена за инициирование этой теории.
