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

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

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

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

История

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

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

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

Обзор

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

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

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

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

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

Совсем недавно исследователи представили новые методы облегченного обнаружения ошибок для самостабилизирующихся систем с использованием локальной проверки.[7][8] Период, термин местный относится к части компьютерной сети. Когда используется локальное обнаружение, компьютеру в сети не требуется связываться со всей сетью для обнаружения ошибки - ошибку можно обнаружить, если каждый компьютер обменивается данными только со своими ближайшими соседями. Эти методы локального обнаружения значительно упростили задачу разработки алгоритмов самостабилизации. Это связано с тем, что механизм обнаружения ошибок и механизм восстановления могут быть разработаны отдельно. Новые алгоритмы, основанные на этих методах обнаружения, также оказались намного эффективнее. Более того, в этих статьях предлагались довольно эффективные преобразователи общего назначения для преобразования несамостабилизирующихся алгоритмов в самостабилизирующие. Идея состоит в том, чтобы,

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

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

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

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

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

Сложность времени

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

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

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

Определение

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

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

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

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

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

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

Связанных с работой

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

использованная литература

  1. ^ «Премия PODC Influential Paper Award: 2002», Симпозиум ACM по принципам распределенных вычислений, получено 2009-09-01
  2. ^ Дейкстра, Эдсгер В. (1974), «Самостабилизирующиеся системы, несмотря на распределенное управление» (PDF), Коммуникации ACM, 17 (11): 643–644, Дои:10.1145/361179.361202.
  3. ^ а б Долев, Шломи (2000). Самостабилизация. Кембридж, Массачусетс: MIT Press. п. 3. ISBN  978-0262041782.
  4. ^ Лэмпорт, Лесли (1985), «Решенные проблемы, нерешенные проблемы и не проблемы параллелизма» (PDF), Обзор операционных систем ACM Special Interest Group, 19 (4): 34–44, Дои:10.1145/858336.858339.
  5. ^ а б c Чаудхури, Сома; Дас, Самир; Пол, Химадри; Тиртхапура, Шриканта (2007). Распределенные вычисления и сети: 8-я международная конференция, ICDCN 2006, Гувахати, Индия, 27-30 декабря 2006 г., Материалы. Берлин: Springer. п. 108. ISBN  978-3540681397.
  6. ^ Кац, Шмуэль; Перри, Кеннет Дж. (1993), "Самостабилизирующиеся расширения для измерительных систем передачи", Распределенных вычислений, 7 (1): 17–26, Дои:10.1007 / BF02278852.
  7. ^ а б Авербух, Барух; Патт-Шамир, Вооз; Варгезе, Джордж (1991), "Самостабилизация путем локальной проверки и коррекции", Proc. 32-й симпозиум по основам компьютерных наук (FOCS), стр. 268–277, CiteSeerX  10.1.1.211.8704, Дои:10.1109 / SFCS.1991.185378, ISBN  978-0-8186-2445-2.
  8. ^ Афек, Иегуда; Куттен, Шай; Юнг, Моти (1997), «Парадигма локального обнаружения и ее приложения к самостабилизации», Теоретическая информатика, 186 (1–2): 199–229, Дои:10.1016 / S0304-3975 (96) 00286-1, Г-Н  1478668.
  9. ^ [Барух Авербух, Шай Куттен, Ишай Мансур, Боаз Патт-Шамир, Джордж Варгезе. Оптимальная по времени самостабилизирующаяся синхронизация. ACM STOC 1993: 652-661.]
  10. ^ Шай Куттен, Боаз Патт-Шамир: Стабилизация протоколов с адаптацией ко времени. Теор. Comput. Sci. 220 (1): 93-111 (1999).
  11. ^ де Бур, Франк; Бонсанге, Марчелло; Руттен, янв (2018). Квартира. Чам: Спрингер. п. 22. ISBN  9783319900889.
  12. ^ Долев, Шломи (2000), Самостабилизация, MIT Press, ISBN  978-0-262-04178-2.
  13. ^ Гауда, Мохамед (1995), > Триумф и горе стабилизации системы, Материалы 9-го международного семинара по распределенным алгоритмам..
  14. ^ Шломи Долев, Мохамед Г. Гауда и Марко Шнайдер. Требования к памяти для тихой стабилизации. В PODC '96: Материалы пятнадцатого ежегодного ACM Симпозиум по принципам распределенных вычислений, страницы 27-34, Нью-Йорк, Нью-Йорк, США, 1996. ACM Press. Расширенная аннотация онлайн.
  15. ^ Долев, Шломи; Герман, Тед (1997), "Суперстабилизирующие протоколы для динамических распределенных систем", Чикагский журнал теоретической информатики, 3: 1–40, Дои:10.4086 / cjtcs.1997.004, статья 4.

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

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