Тарбелділік жүйелердегі супержағдаю алгоритмдері: қателерге төзімділік, жылдам қалпына келтіру, өздігінен тұрақтандыру қасиеттері. Желідегі өзгерістерге бейімділік.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы 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.