Для распределенного восстановления необходимо, Чтобы каждая вершина x была способна работать как супервизор восстановления в малой части системы называемой соседством N(x).В данной системе N(x) ограничена до подграфа Gr, содержащим вершину x,полученный удаленной вершиной x и связанными с ней ребрами Gr.
Таким образом, если вершина x выходит из строя, ее состояние S(x) заменяется на “-I”, и этот факт может быть быстро и недвусмысленно обнаружен всеми вершинами в соседстве N(x).Каждая активная исправная вершина x периодически регистрирует и записывает состояние всех остальных вершин N(xi) . xi также запоминает файлы, которые позволяют переназначить задачи остальным вершинам, если случается отказ. Восстановление от сбоя выполняется, как правило, за несколько шагов.
1) Сбой F проявляется в замене системной конфигурации Gc на Gc1.
2) Активная вершина xi выявляет неисправную вершину xj в своем соседстве N(xi), берет на себя роль локального супервизора и начинает восстановление. Обычно xi в своем соседстве N(xi) пытается обнаружить запасную (избыточную) вершину xk в своем соседстве N(xi) такую, что xk может взять на себя предыдущее состояние Sj неисправной вершины xj.
3) Если отсутствует подходящая запасная вершина, или в N(xi) нет запасных , либо имеющиеся запасные вершины не имеют подходящей связности xi выполняет заменy в N(xi) и уступает роль локального супервизора другой вершине.
Следует отметить, что начальное обнаружение неисправности на шаге 2 соответствует отсутствию вершины в некотором состоянии Si. Последующее переназначение состояний в течении восстановления процесса может так же привести в другие состояния, которые являются временными заменами в системной конфигурации. Например, если супервизор вершины xi заменит состояние другой вершины xk из Sk в состояние Sj обойной вершины xj , старое состояние является неприсвоенным. Это приводит к важной концепции условия ошибки, которая формально определятся следующим образом.
Пусть Gr является отказоустойчивой системой, текущая конфигурация которой Gr. Отказ E(Sj) существует, если Gc не имеет активной вершины в состоянии Si соответствующей вершине графа Gb.Таким образом, обнаружение ошибки будет основано на идентификации локальной конфигурации, в которой одно из n – возможных состояний пропущено. Отметим, что некоторая ошибка Е (Si) может появиться при различных конфигурациях системы.
Наиболее быстрое восстановление достигается тогда, когда избыточная вершина xk немедленно используется для замены отказавшей вершины xj, беря на себя ее состояние. В этом случае говорят, что xk покрывает xj. Вообще, вершина xi покрывает вершину xj в графе G, если xi является смежной каждой вершине в G, которая смежна xj. Пусть Gr является отказоустойчивой системой и пусть Gr – правильная конфигурация. Далее, E(Sj) отказ в Gr, который приводит к замене Gc на Gc1. Вершина xi из Gr покрывает ошибку E(Sj),если заменой состояния вершины xi на Sj получается подграф, включающий xi и все исправные активные вершины в Gc, содержащий подграф М – изоморфной Gb.
Когда имеется непокрывающая избыточная вершина, активная вершина должна быть использована для покрытия ошибки, этим вводится новая ошибка, которая требует дополнительных шагов для восстановления. Заметим, что замена состояния вершины автоматически приводит к изменению множества ошибок, обнаруживаемых этой вершиной.
На рис 1.3в и рис 1.3 с показана избыточная система Gr(Gb). На рис.1.3
Представлена правильная конфигурация Gc. Если происходит отказ Fg, то генерируется ошибка Е(1). Новая конфигурация с ошибкой Е(1) показана на рис. 1.3 д . вершина I покрывает ошибку Е(1). Если состояние вершины переведено из состояния 0 в состояние 1 на основе некоторой стратегии восстановления, то получается новая правильная конфигурация Gc11 (Рис 1.3 е). Эта конфигурация представляет восстановленную систему, в которой вершина I заменяет отказавшую вершину g.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.