Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

История [ править ]

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

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

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

Обзор [ править ]

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

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

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

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

Повышение эффективности [ править ]

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

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

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

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

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

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

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

Сложность времени [ править ]

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

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

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

Определение [ править ]

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

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

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

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

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

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

Связанные работы [ править ]

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

Ссылки [ править ]

  1. ^ "PODC Influential Paper Award: 2002" , Симпозиум ACM по принципам распределенных вычислений , получено 2009-09-01 CS1 maint: обескураженный параметр ( ссылка )
  2. ^ Дейкстр, Эдсгер W. (1974), "Self-стабилизирующие системы, несмотря на распределенное управление" (PDF) , связь по АКМ , 17 (11): 643-644, DOI : 10,1145 / 361179,361202 CS1 maint: обескураженный параметр ( ссылка ).
  3. ^ a b Долев, Шломи (2000). Самостабилизация . Кембридж, Массачусетс: MIT Press. п. 3. ISBN 978-0262041782.
  4. ^ Лампорт, Лесли (1985), "Решены проблемы, нерешенные проблемы, и не-проблем в параллельности" (PDF) , ACM Special Interest Group Операционные системы Обзор , 19 (4): 34-44, DOI : 10,1145 / 858336,858339 CS1 maint: обескураженный параметр ( ссылка ).
  5. ^ a b c Чаудхури, Сома; Дас, Самир; Пол, Химадри; Тиртхапура, Шриканта (2007). Распределенные вычисления и сети: 8-я международная конференция, ICDCN 2006, Гувахати, Индия, 27-30 декабря 2006 г., Материалы . Берлин: Springer. п. 108. ISBN 978-3540681397.
  6. ^ a b c Шломи Долев , Шломо Моран , Амос Израэли: Самостабилизация динамических систем, предполагающая только атомарность чтения / записи. Распределенные вычисления, том 7, страницы 3–16 (1993).
  7. ^ Кац, Шмуэль; Перри, Кеннет Дж (1993), "Self-стабилизирующие расширения для meassage обходя систем", распределенные вычисления , 7 (1): 17-26, DOI : 10.1007 / BF02278852.
  8. ^ а б Авербух, Барух ; Патт-Шамир, Вооз; Варгезе, Джордж (1991), "Самостабилизация путем локальной проверки и коррекции", Proc. Тридцать второй симпозиум по Основы информатики (РПД) , С. 268-277,. CiteSeerX 10.1.1.211.8704 , DOI : 10,1109 / SFCS.1991.185378 , ISBN  978-0-8186-2445-2 CS1 maint: обескураженный параметр ( ссылка ).
  9. ^ Афек, Иегуда; Куттен, Шай ; Юнг, Моти (1997), "Локальная парадигма обнаружения и ее приложения к самостоятельной стабилизации" , Теоретическая информатика , 186 (1-2): 199-229, DOI : 10.1016 / S0304-3975 (96) 00286-1 , Руководство по ремонту 1478668 .
  10. ^ Шломи Долев , Иегуда Афек: Местный стабилизатор. Журнал параллельных и распределенных вычислений, том 62, выпуск 5, май 2002 г., страницы 745-765.
  11. ^ Барух Ауэрбуч, Боаз Patt-Шамира, Джордж Varghese, Шломи Dolev . Самостабилизация с помощью локальной проверки и глобального сброса. WDAG 1994: 326-339.
  12. ^ [Барух Авербух, Шай Куттен, Ишай Мансур, Боаз Патт-Шамир, Джордж Варгезе. Оптимальная по времени самостабилизирующаяся синхронизация. ACM STOC 1993: 652-661.]
  13. ^ Шай Куттен , Боаз Патт-Шамир: Стабилизация протоколов , адаптирующихся ко времени. Теор. Comput. Sci. 220 (1): 93-111 (1999).
  14. ^ де Бур, Франк; Бонсанге, Марчелло; Руттен, янв (2018). Кв . Чам: Спрингер. п. 22. ISBN 9783319900889.
  15. ^ Dolev, Шломи (2000), Self-стабилизации , MIT Press , ISBN 978-0-262-04178-2 CS1 maint: обескураженный параметр ( ссылка ).
  16. ^ Гауда, Мохамед (1995), > Триумф и беда стабилизации системы , Труды 9-го международного семинара по распределенным алгоритмам. CS1 maint: обескураженный параметр ( ссылка ).
  17. ^ Шломи Dolev , Mohamed Г. Гауда , и Марко Шнайдер. Требования к памяти для бесшумной стабилизации . В PODC '96: Proceedings of the пятнадцатого ежегодного симпозиума ACM по принципам распределенных вычислений , страницы 27-34, Нью-Йорк, Нью-Йорк, США, 1996. ACM Press. Онлайн расширенная аннотация .
  18. ^ Долев, Шломи ; Герман, Тед (1997), "Superstabilizing протоколов для динамических распределенных систем", Чикаго Журнал теоретической информатики , 3 : 1-40, DOI : 10,4086 / cjtcs.1997.004 CS1 maint: обескураженный параметр ( ссылка ), статья 4.

Внешние ссылки [ править ]

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