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

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

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

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