|
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 ''fast'' 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. ==Definitions== 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” that occurs 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. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Superstabilization」の詳細全文を読む スポンサード リンク
|