Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Суперстабилизация – это концепция устойчивости к сбоям в распределенных вычислениях. Суперстабилизирующие распределенные алгоритмы сочетают в себе характеристики самостабилизирующихся и динамических алгоритмов. Суперстабилизирующий алгоритм, как и любой другой самостабилизирующийся алгоритм, может быть запущен из произвольного состояния и в конечном итоге сойдется к допустимому состоянию. Кроме того, суперстабилизирующий алгоритм быстро восстанавливается после единичного изменения в топологии сети (добавления или удаления одного ребра или узла в сети). Любой самостабилизирующийся алгоритм восстанавливается после изменения топологии сети – конфигурацию системы после изменения топологии можно рассматривать как любую другую произвольную начальную конфигурацию. Однако в самостабилизирующемся алгоритме время сходимости после единичного изменения топологии сети может быть таким же большим, как и время сходимости из произвольного начального состояния. При изучении суперстабилизирующих алгоритмов особое внимание уделяется времени, необходимому для восстановления после единичного изменения топологии сети.
Superstabilization is a concept of fault tolerance in distributed computing. Superstabilizing distributed algorithms combine the features of self stabilizing algorithms and dynamic algorithms. A superstabilizing algorithm – just like any other self stabilizing algorithm – can be started in an arbitrary state, and it will eventually converge to a legitimate state. Additionally, a superstabilizing algorithm will recover rapidly from a single change in the network topology (adding or removing one edge or node in the network). Any self stabilizing algorithm recovers from a change in the network topology – the system configuration after a topology change can be treated just like any other arbitrary starting configuration. However, in a self stabilizing algorithm, the convergence after a single change in the network topology may be as slow as the convergence from an arbitrary starting state. In the study of superstabilizing algorithms, special attention is paid to the time it takes to recover from a single change in the network topology.
Определения
Время стабилизации суперстабилизирующего алгоритма определяется точно так же, как и для самостабилизирующего алгоритма: это время, необходимое для достижения легитимного состояния из произвольной конфигурации. В зависимости от вычислительной модели, время измеряется, например, в синхронных раундах обмена сообщениями или в асинхронных циклах. Время суперстабилизации – это время восстановления после единственного изменения топологии. Предполагается, что система изначально находится в легитимной конфигурации. Затем топология сети изменяется; время суперстабилизации – это максимальное время, за которое система возвращается в легитимную конфигурацию. Аналогично, мера корректировки – это максимальное количество узлов, которым необходимо изменить своё состояние после такого изменения. "Почти легитимные конфигурации", возникающие после одного изменения топологии, могут быть формально смоделированы с использованием переходных предикатов: переходный предикат – это предикат, который выполняется после единственного изменения в топологии сети, а также в процессе сходимости к легитимной конфигурации.
The stabilization time of a superstabilizing algorithm is defined exactly as in the case of self stabilizing algorithm: how long it takes to converge to a legitimate state from an arbitrary configuration. Depending on the computational model, time is measured, e. g., in synchronous communication rounds or in asynchronous cycles. The superstabilization time is the time to recover from a single topology change. It is assumed that the system is initially in a legitimate configuration. Then the network topology is changed; the superstabilization time is the maximum time it takes for the system to reach a legitimate configuration again. Similarly, the adjustment measure is the maximum number of nodes that have to change their state after such changes. The “almost legitimate configurations” which occur after one topology change can be formally modelled by using passage predicates: a passage predicate is a predicate that holds after a single change in the network topology, and also during the convergence to a legitimate configuration.