4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
(не показаны 2 промежуточные версии этого же участника) | |||
Строка 44: | Строка 44: | ||
'''Графовые алгоритмы''' | '''Графовые алгоритмы''' | ||
Сети коммуникаций обычно представляются моделями в виде графов, и потребность в распределенных графовых алгоритмах, устойчивых к преходящим сбоям, стимулирует изучение таких задач. В этой области получены такие результаты, как самостабилизирующиеся алгоритмы для остовных деревьев, | Сети коммуникаций обычно представляются моделями в виде графов, и потребность в распределенных графовых алгоритмах, устойчивых к преходящим сбоям, стимулирует изучение таких задач. В этой области получены такие результаты, как самостабилизирующиеся алгоритмы для остовных деревьев, поиска центра, поиска паросочетаний, проверки на планарность, раскраски, нахождения независимых множеств и другие. В общем случае все графовые задачи могут быть решены при помощи самостабилизирующихся алгоритмов: задачи, которые имеют на входе топологию сети и, возможно, связанные с ней коэффициенты, такие как веса ребер, и определяют выходные данные как функцию от входных, могут быть решены общими методами самостабилизации. Эти общие методы требуют значительных затрат времени и памяти, а также могут использовать более сильные предположения о модели, чем требуется для конкретных задач – например, уникальные идентификаторы процессов и предполагаемое ограничение на диаметр сети. Поэтому исследования алгоритмов на графах продолжаются. | ||
Одним из открытий, сделанных в ходе исследования самостабилизирующихся графовых алгоритмов, является разница между алгоритмами, которые завершают работу, и теми, которые постоянно меняют состояние даже после | Одним из открытий, сделанных в ходе исследования самостабилизирующихся графовых алгоритмов, является разница между алгоритмами, которые завершают работу, и теми, которые постоянно меняют состояние даже после стабилизации выходных результатов. Рассмотрим задачу построения остовного дерева с корнем в процессе r. Некоторые алгоритмы самостабилизируются на свойстве, заключающемся в том, что для каждого <math>p \ne r</math> переменная <math>u_p</math> ссылается на родителя p в остовном дереве, и состояние остается неизменным. Другим примером алгоритмов являются самостабилизирующиеся протоколы для циркуляции маркеров с тем побочным эффектом, что маршрут циркуляции маркеров формирует остовное дерево. Первый тип алгоритмов требует <math>O(lg \; n)</math> памяти на процесс, тогда как второй – <math>O(lg \; \delta)</math>, где <math>\delta</math> – степень (число соседей) процесса. Это различие было формализовано в понятии ''молчаливых'' алгоритмов, которые со временем перестают изменять какое бы то ни было значение в процессе коммуникации; в [5] для модели регистра связей было показано, что молчаливые алгоритмы для многих графовых задач требуют <math>\Omega(lg \; n)</math> памяти. | ||
Строка 57: | Строка 57: | ||
'''Общие методы''' | '''Общие методы''' | ||
Общая проблема построения самостабилизирующегося алгоритма для входной нереактивной задачи может быть решена с помощью стандартных инструментов распределенных вычислений: моментальный снимок, трансляция, сброс состояния системы и синхронизация – эти задачи являются конструктивными блоками, позволяющими непрерывно | Общая проблема построения самостабилизирующегося алгоритма для входной нереактивной задачи может быть решена с помощью стандартных инструментов распределенных вычислений: моментальный снимок, трансляция, сброс состояния системы и синхронизация – эти задачи являются конструктивными блоками, позволяющими непрерывно отслеживать глобальное состояние (в некоторых удачных случаях <math>\mathcal{L}</math> можно локально проверить и исправить). Эти конструктивные блоки имеют самостабилизирующиеся решения, что позволяет использовать общий подход. | ||
правок