Самостабилизирующиеся алгоритмы

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Самостабилизирующие алгоритмы — это идея построения алгоритмов, устойчивых к ошибкам:
  • Код потерять сложно, поэтому мы считаем, что он не портится при падении узлов.
  • Алгоритм может работать с любой комбинацией данных.
  • Из любого состояния мы попадаем в легальное через конечное число шагов (при отсутствии сбоев).

Тогда от любого сбоя мы через конечное число шагов будем восстанавливаться без консенсусов и прочих развлечений.

Взаимное исключение

Поиск остовного дерева