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

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

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

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

История

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

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

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

Обзор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

Ссылки

^ «Награда PODC Influential Paper Award: 2002» , Симпозиум ACM по принципам распределенных вычислений , получено 1 сентября 2009 г.
^ Дейкстра, Эдсгер В. (1974), «Самостабилизирующиеся системы, несмотря на распределенное управление» (PDF) , Communications of the ACM , 17 (11): 643–644, doi : 10.1145/361179.361202 , S2CID 11101426 .
^ Jump up to: ^а ^б Долев, Шломи (2000). Самостабилизация . Кембридж, Массачусетс: MIT Press. п. 3. ISBN 978-0262041782 .
^ Лэмпорт, Лесли (1985), «Решенные проблемы, нерешенные проблемы и отсутствие проблем в параллельной работе» (PDF) , Обзор операционных систем Специальной группы по интересам ACM , 19 (4): 34–44, doi : 10.1145/858336.858339 , S2CID 228819 .
^ Jump up to: ^а ^б ^с Чаудхури, Сома; Дас, Самир; Пол, Химадри; Тиртхапура, Шриканта (2007). Распределенные вычисления и сети: 8-я Международная конференция, ICDCN 2006, Гувахати, Индия, 27–30 декабря 2006 г., Материалы . Берлин: Шпрингер. п. 108. ИСБН 978-3540681397 .
^ Jump up to: ^а ^б ^с Шломи Долев , Шломо Моран , Амос Исраэль: Самостабилизация динамических систем, предполагающая только атомарность чтения/записи. Распределенные вычисления, том 7, страницы 3–16 (1993).
^ Кац, Шмуэль; Перри, Кеннет Дж. (1993), «Самостабилизирующиеся расширения для систем передачи сообщений», Distributed Computing , 7 (1): 17–26, doi : 10.1007/BF02278852 , S2CID 37245790 .
^ Jump up to: ^а ^б Авербух, Барух ; Патт-Шамир, Боаз; Варгезе, Джордж (1991), «Самостабилизация путем локальной проверки и коррекции», Proc. 32-й симпозиум по основам компьютерных наук (FOCS) , стр. 268–277, CiteSeerX 10.1.1.211.8704 , doi : 10.1109/SFCS.1991.185378 , ISBN 978-0-8186-2445-2 , S2CID 8320293 .
^ Афек, Иегуда ; Каттен, Шей ; Юнг, Моти (1997), «Парадигма локального обнаружения и ее приложения к самостабилизации» , Theoretical Computer Science , 186 (1–2): 199–229, doi : 10.1016/S0304-3975(96)00286-1 , МР 1478668 .
^ Шломи Долев , Иегуда Афек: Местный стабилизатор. Журнал параллельных и распределенных вычисленийТом 62, выпуск 5, май 2002 г., страницы 745–765.
^ Барух Авербух, Боаз Патт-Шамир, Джордж Варгезе, Шломи Долев . Самостабилизация путем локальной проверки и глобального сброса. ВДАГ 1994: 326–339.
^ [Барух Авербух, Шей Каттен , Ишай Мансур, Боаз Патт-Шамир, Джордж Варгезе. Оптимальная по времени самостабилизирующаяся синхронизация. ACM STOC 1993: 652-661.]
^ Шей Каттен , Боаз Патт-Шамир: Стабилизация протоколов, адаптирующихся ко времени. Теор. Вычислить. наук. 220(1): 93-111 (1999).
^ де Бур, Франк; Бонсанге, Марчелло; Руттен, Ян (2018). Апт . Хэм: Спрингер. п. 22. ISBN 9783319900889 .
^ Долев, Шломи (2000), Самостабилизация , MIT Press , ISBN 978-0-262-04178-2 .
^ Гауда, Мохамед (1995), > Триумф и скорбь стабилизации системы , Труды 9-го международного семинара по распределенным алгоритмам. .
^ Шломи Долев , Мохамед Г. Гауда и Марко Шнайдер. Требования к памяти для бесшумной стабилизации . В PODC '96: Материалы пятнадцатого ежегодного симпозиума ACM по принципам распределенных вычислений , страницы 27–34, Нью-Йорк, Нью-Йорк, США, 1996. ACM Press. Расширенный онлайн-реферат .
^ Долев, Шломи ; Герман, Тед (1997), «Суперстабилизирующие протоколы для динамических распределенных систем», Чикагский журнал теоретической информатики , 3 : 1–40, doi : 10.4086/cjtcs.1997.004 , статья 4.

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

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

[1] «Награда PODC Influential Paper Award: 2002» , Симпозиум ACM по принципам распределенных вычислений , получено 1 сентября 2009 г.

[2] Дейкстра, Эдсгер В. (1974), «Самостабилизирующиеся системы, несмотря на распределенное управление» (PDF) , Communications of the ACM , 17 (11): 643–644, doi : 10.1145/361179.361202 , S2CID 11101426 .

[:0-3] Jump up to: ^а ^б Долев, Шломи (2000). Самостабилизация . Кембридж, Массачусетс: MIT Press. п. 3. ISBN 978-0262041782 .

[4] Лэмпорт, Лесли (1985), «Решенные проблемы, нерешенные проблемы и отсутствие проблем в параллельной работе» (PDF) , Обзор операционных систем Специальной группы по интересам ACM , 19 (4): 34–44, doi : 10.1145/858336.858339 , S2CID 228819 .

[:1-5] Jump up to: ^а ^б ^с Чаудхури, Сома; Дас, Самир; Пол, Химадри; Тиртхапура, Шриканта (2007). Распределенные вычисления и сети: 8-я Международная конференция, ICDCN 2006, Гувахати, Индия, 27–30 декабря 2006 г., Материалы . Берлин: Шпрингер. п. 108. ИСБН 978-3540681397 .

[DIM-6] Jump up to: ^а ^б ^с Шломи Долев , Шломо Моран , Амос Исраэль: Самостабилизация динамических систем, предполагающая только атомарность чтения/записи. Распределенные вычисления, том 7, страницы 3–16 (1993).

[7] Кац, Шмуэль; Перри, Кеннет Дж. (1993), «Самостабилизирующиеся расширения для систем передачи сообщений», Distributed Computing , 7 (1): 17–26, doi : 10.1007/BF02278852 , S2CID 37245790 .

[awerbuch-8] Jump up to: ^а ^б Авербух, Барух ; Патт-Шамир, Боаз; Варгезе, Джордж (1991), «Самостабилизация путем локальной проверки и коррекции», Proc. 32-й симпозиум по основам компьютерных наук (FOCS) , стр. 268–277, CiteSeerX 10.1.1.211.8704 , doi : 10.1109/SFCS.1991.185378 , ISBN 978-0-8186-2445-2 , S2CID 8320293 .

[afek-9] Афек, Иегуда ; Каттен, Шей ; Юнг, Моти (1997), «Парадигма локального обнаружения и ее приложения к самостабилизации» , Theoretical Computer Science , 186 (1–2): 199–229, doi : 10.1016/S0304-3975(96)00286-1 , МР 1478668 .

[10] Шломи Долев , Иегуда Афек: Местный стабилизатор. Журнал параллельных и распределенных вычисленийТом 62, выпуск 5, май 2002 г., страницы 745–765.

[APVD-11] Барух Авербух, Боаз Патт-Шамир, Джордж Варгезе, Шломи Долев . Самостабилизация путем локальной проверки и глобального сброса. ВДАГ 1994: 326–339.

[Awerbuch2-12] [Барух Авербух, Шей Каттен , Ишай Мансур, Боаз Патт-Шамир, Джордж Варгезе. Оптимальная по времени самостабилизирующаяся синхронизация. ACM STOC 1993: 652-661.]

[13] Шей Каттен , Боаз Патт-Шамир: Стабилизация протоколов, адаптирующихся ко времени. Теор. Вычислить. наук. 220(1): 93-111 (1999).

[14] де Бур, Франк; Бонсанге, Марчелло; Руттен, Ян (2018). Апт . Хэм: Спрингер. п. 22. ISBN 9783319900889 .

[15] Долев, Шломи (2000), Самостабилизация , MIT Press , ISBN 978-0-262-04178-2 .

[16] Гауда, Мохамед (1995), > Триумф и скорбь стабилизации системы , Труды 9-го международного семинара по распределенным алгоритмам. .

[17] Шломи Долев , Мохамед Г. Гауда и Марко Шнайдер. Требования к памяти для бесшумной стабилизации . В PODC '96: Материалы пятнадцатого ежегодного симпозиума ACM по принципам распределенных вычислений , страницы 27–34, Нью-Йорк, Нью-Йорк, США, 1996. ACM Press. Расширенный онлайн-реферат .

[18] Долев, Шломи ; Герман, Тед (1997), «Суперстабилизирующие протоколы для динамических распределенных систем», Чикагский журнал теоретической информатики , 3 : 1–40, doi : 10.4086/cjtcs.1997.004 , статья 4.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]