Самостабилизация: различия между версиями

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