Самостабилизация

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

На первый взгляд гарантия самостабилизации может показаться менее многообещающей, чем гарантия более традиционных отказоустойчивых алгоритмов, целью которых является гарантировать, что система всегда остается в правильном состоянии при определенных видах переходов между состояниями. Однако традиционная отказоустойчивость не всегда может быть достигнута. Например, этого невозможно достичь, если система запущена в неправильном состоянии или повреждена злоумышленником. Более того, из-за их сложности очень сложно отлаживать и анализировать распределенные системы. Следовательно, очень сложно предотвратить переход распределенной системы в неправильное состояние. Действительно, некоторые формы самостабилизации включены во многие современные компьютерные и телекоммуникационные сети, поскольку это дает им возможность справляться с ошибками, которые не были предусмотрены при разработке алгоритма.

Спустя много лет после основополагающей статьи Эдсгера Дейкстры в 1974 году эта концепция остается важной, поскольку представляет собой важную основу для самоуправляемых компьютерных систем и отказоустойчивых систем . В результате статья Дейкстры получила в 2002 году премию ACM PODC Influential-Paper Award , одну из самых высоких наград в сообществе распределенных вычислений. Более того, после смерти Дейкстры награда была переименована и теперь называется Премией Дейкстры.

История

Э. У. Дейкстра в 1974 году представил концепцию самостабилизации, побудившую к дальнейшим исследованиям в этой области. Его демонстрация включала презентацию самостабилизирующихся алгоритмов взаимного исключения . Он также продемонстрировал первые самостабилизирующиеся алгоритмы, которые не основывались на строгих предположениях о системе. Некоторые предыдущие протоколы, использовавшиеся на практике, действительно стабилизировались, но только при условии существования часов, которые были глобальными для системы, и при условии известной верхней границы длительности каждого системного перехода. Лишь десять лет спустя Лесли Лэмпорт указал на важность работы Дейкстры на конференции 1983 года под названием «Симпозиум по принципам распределенных вычислений ». обратили свое внимание на эту элегантную концепцию отказоустойчивости. В своем выступлении Лэмпорт заявил:

Я считаю это самой блестящей работой Дейкстры — по крайней мере, его самой блестящей опубликованной статьей. Это почти полностью неизвестно. Я считаю это важной вехой в работе над отказоустойчивостью... Я считаю самостабилизацию очень важной концепцией отказоустойчивости и очень плодотворным полем для исследований.

Впоследствии работа Дейкстры была удостоена влиятельной бумажной награды ACM-PODC, которая затем стала премией Дейкстры ACM (Ассоциации вычислительной техники) в области распределенных вычислений, вручаемой на ежегодном симпозиуме ACM-PODC.

Обзор

является Распределенный алгоритм самостабилизирующимся, если, начиная с произвольного состояния, он гарантированно сходится к легитимному состоянию и после этого остается в легитимном наборе состояний. Состояние является легитимным, если начиная с этого состояния алгоритм удовлетворяет своей спецификации. Свойство самостабилизации позволяет распределенному алгоритму восстанавливаться после кратковременного сбоя независимо от его характера. Более того, самостабилизирующийся алгоритм не требует инициализации, поскольку со временем он начинает вести себя правильно независимо от своего начального состояния.

Статья Дейкстры, в которой вводится концепция самостабилизации, представляет пример в контексте «токен-ринга» — сети компьютеров, упорядоченных по кругу. Здесь каждый компьютер или процессор может «видеть» все состояние одного процессора, который непосредственно ему предшествует, и что это состояние может означать, что у процессора «есть токен» или «нет токена». Одно из требований состоит в том, что ровно один из них должен «держать токен» в любой момент времени. Второе требование предписывает, чтобы каждый узел «передавал токен» следующему за ним компьютеру/процессору, чтобы токен в конечном итоге циркулировал по кольцу.

• Отсутствие токена является правильным состоянием для каждого компьютера в этой сети, поскольку токен может храниться на другом компьютере. Однако если каждый компьютер находится в состоянии «не имеет токена», то сеть в целом находится в неправильном состоянии.
• Аналогично, если более чем один компьютер «держит токен», то это неправильное состояние для сети, хотя его нельзя считать неправильным, рассматривая любой компьютер по отдельности. Поскольку каждый компьютер может «наблюдать» только за состояниями двух своих соседей, компьютерам трудно решить, находится ли сеть в целом в правильном состоянии.

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

Повышение эффективности

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

Термин локальный относится к части компьютерной сети. При использовании локального обнаружения компьютеру в сети не требуется связываться со всей сетью для обнаружения ошибки — ошибку можно обнаружить, если каждый компьютер взаимодействует только со своими ближайшими соседями. Эти методы локального обнаружения значительно упростили задачу разработки самостабилизирующихся алгоритмов. Это связано с тем, что механизм обнаружения ошибок и механизм восстановления могут быть разработаны отдельно. Новые алгоритмы, основанные на этих методах обнаружения, также оказались гораздо более эффективными. Более того, в этих статьях предложены довольно эффективные общие преобразователи для преобразования несамостабилизирующихся алгоритмов в самостабилизирующиеся. Идея состоит в том, чтобы,

1. Одновременно запустите несамостабилизирующийся протокол.
2. обнаруживать неисправности (во время выполнения данного протокола) с помощью вышеупомянутых методов обнаружения,
3. затем применить (самостабилизирующийся) протокол «перезагрузки», чтобы вернуть систему в некоторое заранее определенное исходное состояние, и, наконец,
4. перезапустите данный (несамостабилизирующийся) протокол.

Комбинация этих 4 частей является самостабилизирующейся (до тех пор, пока не будет триггера неисправности во время фаз коррекции ошибки, например, ).Первоначальные протоколы самостабилизации также были представлены в вышеупомянутых статьях. Более эффективные протоколы сброса были представлены позже, например

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

Полезным свойством самостабилизирующихся алгоритмов является то, что они могут состоять из слоев, если слои не демонстрируют каких-либо циклических зависимостей . Время стабилизации композиции тогда ограничивается суммой отдельных времен стабилизации каждого слоя.

Позже появились новые подходы к работе Дейкстры, например, случай Кшиштофа Апта и предложения Эхсана Шоджи, которые продемонстрировали, как самостабилизация может быть естественным образом сформулирована с использованием стандартных концепций стратегических игр, в частности концепции пути улучшения. Эта конкретная работа была направлена ​​​​на то, чтобы продемонстрировать связь между самостабилизацией и теорией игр.

Временная сложность

Временная сложность самостабилизирующегося алгоритма измеряется в (асинхронных) раундах или циклах.

• Раунд — это кратчайшая трассировка выполнения, в которой каждый процессор выполняет хотя бы один шаг.
• Аналогично, цикл — это кратчайшая трасса выполнения, в которой каждый процессор выполняет хотя бы одну полную итерацию своего повторно выполняемого списка команд.

Для измерения времени стабилизации выхода определяется подмножество переменных состояния, видимых извне ( выход ). Определенные состояния выходов определяются как правильные (законные). Говорят, что набор выходных сигналов всех компонентов системы стабилизировался в тот момент, когда он начинает быть правильным, при условии, что он остается правильным в течение неопределенного времени, если не возникают дополнительные неисправности. Время стабилизации выходного сигнала — это время (количество (асинхронных) раундов ), пока выходной сигнал не стабилизируется.

Определение

Система является самостабилизирующейся тогда и только тогда, когда:

1. Начиная с любого состояния, гарантируется, что система в конечном итоге достигнет правильного состояния ( сходимости ).
2. Учитывая, что система находится в правильном состоянии, она гарантированно останется в правильном состоянии при условии, что не произойдет никаких ошибок ( замыкание ).

Говорят, что система является рандомизированной самостабилизирующейся тогда и только тогда, когда она самостабилизируется и ожидаемое количество раундов, необходимое для достижения правильного состояния, ограничено некоторой константой. $k$.

Проектирование самостабилизации в указанном выше смысле, как известно, является трудной задачей. Фактически класс распределенных алгоритмов не обладает свойством локальной проверки: легитимность состояния сети не может быть оценена одним процессом. Наиболее очевидным случаем является кольцо токенов Дейкстры, определенное выше: ни один процесс не может определить, является ли состояние сети законным или нет, в случае, когда в несмежных процессах присутствует более одного токена. Это говорит о том, что самостабилизация распределенной системы — это своего рода коллективный разум , где каждый компонент предпринимает локальные действия, основываясь на своих местных знаниях, но в конечном итоге это гарантирует глобальную конвергенцию в конце.

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

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

Связанная работа

Расширением концепции самостабилизации является концепция сверхстабилизации . Цель здесь — справиться с динамическими распределенными системами, которые претерпевают топологические изменения. В классической теории самостабилизации произвольные изменения рассматриваются как ошибки, при которых не даются никакие гарантии до тех пор, пока система снова не стабилизируется. В суперстабилизирующих системах существует предикат перехода , который всегда выполняется при реконфигурации топологии системы.

Теория, зародившаяся в области самостабилизации, проверяет (распределенным образом), что совокупность состояний узлов в сети подчиняется некоторому предикату. Эта теория вышла за рамки самостабилизации и привела к таким понятиям, как «распределенный NP» (распределенная версия NP (сложность) ), распределенное нулевое знание (распределенная версия нулевого знания ) и т. д. Международный коллоквиум по структурной информации и Премия Communication Complexity (SIRROCO) за инновации в распределенных вычислениях 2024 года была присуждена за разработку этой теории.

Внешние ссылки

• libcircle — реализация самостабилизации с использованием передачи токенов для завершения.