Минимизированное вложение произвольных гамильтоновых графов в отказоустойчивый граф и реконфигурация при отказах. I. Одно-отказоустойчивые структуры

В работе предложены решения по минимизированному вложению гамильтоновых графов в объемлющий отказоустойчивый граф, являющийся структурной моделью многопроцессорной отказоустойчивой вычислительной системы. Неисправности рассматриваются как отказы вершин и (или) связей между вершинами в графе. Математической основой исследований выбран инвариантно-групповой анализ свойств структуры системы. На его базе предложен единый подход к синтезу одно- и $k$-отказоустойчивых структур, сохраняющих после реконфигурации от отказов логическую структуру исходного целевого графа и, тем самым, исходный скомпилированный код заданий системы. Найдены минимальные отказоустойчивые решения для одно- и $k$-отказоустойчивых циклов, простых и диагональных решеток, других популярных структур, включая произвольные гамильтоновые графы, для которых решения носят минимизированный характер. Рассмотрены алгоритмы реконфигурации после произвольных одиночных и кратных отказов. Восстановление от отказов происходит очень просто, базируясь на небольших таблицах групповых автоморфизмов системы, которые позволяют корректно восстанавливать систему “на уровне теорем”, не требуя дополнительной верификации процесса реконфигурации ни в статике, ни в динамике.

Статья представлена к публикации членом редколлегии: П. П. Пархоменко