Связность и отказоустойчивость в случайных регулярных графах: различия между версиями

Ключевые слова и синонимы: [[Устойчивость]]

Новая модель случайных графов, которая была предложена в работе [7], касается случайных графов с пропущенными дугами (далее обозначаемыми Grn p), полученных путем выбора дуг из случайного элемента множества всех регулярных графов степени r независимым образом, с вероятностью p. Такие графы могут представлять сеть коммуникаций, в которой связи обрываются независимо друг от друга с вероятностью f = 1 — p. Формальное определение пространства вероятностей Grn p:

Определение 1 (пространство вероятности Grn). Пусть Gnr – пространство вероятности всех случайных регулярных графов с n вершинами, каждая вершина которых имеет степень r. Пространство вероятности Grn p случайных регулярных графов с ошибочными дугами строится на основании двух последовательных случайных экспериментов: вначале из пространства Grn выбирается случайный регулярный граф, а затем каждая дуга случайным и независимым образом удалется из этого графа с вероятностью f = 1 — p.

»Важное свойство связности Gnr; p исследуется путем оценки диапазонов r;f, для которых, с высокой вероятностью, графы Gnr; p (а) являются сильно связными; (б) становятся несвязными и (в) содержат большой (размера 0{n)) связный компонент меньшего диаметра.

Термины «почти наверняка» и «с высокой вероятностью» будут использоваться в их обычном значении при описании свойств случайных графов. Свойство, определенное для случайного графа, выполняется «почти наверняка», если его вероятность стремится к 1 по мере того, как значение независимой переменной (обычно такой переменной является число вершин графа) стремится к бесконечности. Выражение «с высокой вероятностью» означает, что вероятность выполнения свойства случайного графа (или вероятность успешного завершения рандомизированного алгоритма) равна по меньшей мере 1 — n~a, где a > 0 – константа, а n – число вершин графа.

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

Рассмотрим несколько важных свойств связности для случайных регулярных графов с ошибочными дугами. Чтобы иметь возможность работать с моделью Grn p, в [ ] вначале расширяется понятие конфигураций и приводится лемма о переводе между конфигурациями и случайными регулярными графами, введенная Боллобасом [2, 3]; вводится понятие случайных конфигураций, отвечающих за пропущенные дуги, и приводится расширенная лемма о переводе между случайными конфигурациями и случайными регулярными графами с пропущенными дугами.

Разработан алгоритм для построения этого огромного компонента за время O(n log n).

С технической точки зрения делать какие-либо утверждения о случайных регулярных графах не так просто, как в случае Gn;p, в силу стохастических зависимостей от существования дуг, связанных с регулярностью. Введенная Боллобасом [2, 3] нотация конфигурации предназначена для перевода операторов для случайных регулярных графов в операторы для соответствующих конфигураций, которые не содержат зависимостей между дугами в силу регулярности и с которыми поэтому намного проще работать.

Теорема 6. Если f < 1 — ^, то Grn p содержит огромный (размером 0{n)) связный компонент для любого r > 64

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

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

Отдельного упоминания заслуживает один из важнейших вариантов ее применения: многозадачность в мультипроцессорах с распределенной памятью обычно достигается путем назначения каждой задаче (называемой графом вычислений) произвольной подсети имеющейся сети. В результате каждая параллельная программа может быть представлена в виде взаимосвязей процессоров над графом вычислений. Заметим, что величина мультисвязности k графа вычислений означает, что исполнение приложения может допускать до k — 1 дополнительных ошибок в режиме выполнения.

На основе представленных в [ ] идей были проведены и другие интересные исследования. Андреас Гердт [ ] продолжил работать над темами, представленными в предыдущей ([8]) версии работы [7], и продемонстрировал следующие результаты: если степерь r фиксирована, то p = -^ представляет собой пороговую вероятность существования компонента линейного размера в версии почти любого случайного регулярного графа с пропусками дуг. Фактически он демонстрирует, что в случае, если каждая дуга произвольного графа G с максимальной степенью, ограниченной сверху r, имеется в наличии с вероятностью p = -^, где Я < 1, тогда версия G с пропусками дуг с высокой вероятностью содержит только компоненты, имеющие не более чем логарифмический размер относительно числа вершин. Из этого следует некоторое понятие оптимальности случайных регулярных графов с пропущенными дугами. В [5, 10] исследуются важные свойства расширения случайных регулярных графов с пропущенными дугами; в [ ] та же задача рассматривается для случая утолщенных деревьев – распространенного типа топологии сетей. В продолжение этих исследований следовало бы изучить другие комбинаторные свойства случайных регулярных графов с пропущенными дугами, а также предложить для них эффективные алгоритмы.