Кешірімділік және өздігінен тұрақтандыру концепциясы
Self-stabilization
Түзілуге төзілділік: өздігінен тұрақталатын жүйелер қате күйден шығып, дұрыс күйге жетеді. Бастапқы қателіктерде де жұмыс істейді, жүйеге қауіпсіздік қамтамасыз етеді.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Қатеге төзімділік ұғымы
Concept of fault tolerance
Өзін-өзі тұрақтандыру – таратылған жүйелердегі қатеге төзімділік ұғымы. Кез келген бастапқы күй берілген жағдайда, өзін-өзі тұрақтандыратын таратылған жүйе шекті сандағы орындау қадамдарында дұрыс күйге жетеді. Бір қарағанда, өзін-өзі тұрақтандыру кепілі, жүйенің белгілі бір күйлер арасындағы өзгерулер кезінде әрқашан дұрыс күйде қалуын қамтамасыз етуге бағытталған дәстүрлі қатеге төзімділіктен кем үміт беретін сияқты көрінеді. Дегенмен, дәстүрлі қатеге төзімділіктің өзі әрқашан қол жеткізілмейді. Мысалы, жүйе дұрыс емес күйде іске қосылғанда немесе сыртқы тұлғаның әрекетінен зардап шеккенде оны қамтамасыз ету мүмкін емес. Сонымен қатар, таратылған жүйелердің күрделілігі оларды жөндеу мен талдауды өте қиын жасайды. Сондықтан, таратылған жүйенің дұрыс емес күйге жетуіне жол бермеу де қиын. Шындығында, өзін-өзі тұрақтандырудың кейбір түрлері көптеген қазіргі заманғы компьютерлік және телекоммуникациялық желілерге енгізілген, себебі бұл оларға алгоритмді жобалау кезінде ескерілмеген қателермен күресуге мүмкіндік береді. 1974 жылы Эдсгер Дайкстраның жариялаған мақаласынан бері көп жылдар өткенімен, бұл ұғым маңыздылығын сақтап келеді, өйткені ол өзін-өзі басқаратын компьютерлік жүйелер мен қатеге төзімді жүйелер үшін маңызды негіз болып табылады. Нәтижесінде, Дайкстраның мақаласы 2002 жылы ACM PODC ықпалды мақаласы сыйлығын алды, бұл таратылған есептеу қауымдастығының ең жоғары наградаларының бірі. Сонымен қатар, Дайкстраның қазасынан кейін сыйлықтың аты өзгертіліп, қазір Дайкстра сыйлығы деп аталады.
Self stabilization is a concept of fault tolerance in distributed systems. Given any initial state, a self stabilizing distributed system will end up in a correct state in a finite number of execution steps. At first glance, the guarantee of self stabilization may seem less promising than that of the more traditional fault tolerance of algorithms, that aim to guarantee that the system always remains in a correct state under certain kinds of state transitions. However, that traditional fault tolerance cannot always be achieved. For example, it cannot be achieved when the system is started in an incorrect state or is corrupted by an intruder. Moreover, because of their complexity, it is very hard to debug and to analyze distributed systems. Hence, it is very hard to prevent a distributed system from reaching an incorrect state. Indeed, some forms of self stabilization are incorporated into many modern computer and telecommunications networks, since it gives them the ability to cope with faults that were not foreseen in the design of the algorithm. Many years after the seminal paper of Edsger Dijkstra in 1974, this concept remains important as it presents an important foundation for self managing computer systems and fault tolerant systems. As a result, Dijkstra's paper received the 2002 ACM PODC Influential Paper Award, one of the highest recognitions in the distributed computing community. Moreover, after Dijkstra's death, the award was renamed and is now called the Dijkstra Award.
Тарих
Э. В. Дикстра 1974 жылы өзін-өзі тұрақтандыру концепциясын ұсынды, бұл осы саладағы одан әрі зерттеулерге түрткі болды. Оның демонстрациясы өзін-өзі тұрақтандырушы өзара қатынасты шектеу алгоритмдерін көрсетуді қамтыды. Сондай-ақ, ол жүйеге қатысты күшті шарттарға тәуелді емес, тұрақтандырушы алгоритмдерді көрсетті. Алдыңғы кейбір протоколдар іс жүзінде тұрақтанды, бірақ жүйеде жаһандық сағат бар деген және әрбір жүйелік өтудің ұзақтығының белгілі жоғарғы шегі бар деген болжамдарға негізделді. Тек он жыл өткен соң, Лесли Лампорт 1983 жылы өткен «Сандық есептеулердің принциптері» (Symposium on Principles of Distributed Computing) конференциясында Дикстраның жұмысының маңыздылығын атап көрсеткенде ғалымдар осы әдемі қатеге төзімділік концепциясына назар аударды. Лампорт өз баяндамасында былай деді: «Мен мұны Дикстраның ең керемет жұмысы деп санаймын, кемінде, оның ең керемет жарияланған мақаласы. Бұл дерлік белгісіз. Мен оны қателерге төзімділік жұмысының маңызды кезеңі деп санаймын. Өзін-өзі тұрақтандыруды қателерге төзімділіктегі өте маңызды концепция деп санаймын және зерттеу үшін өте құнарлы сала деп есептеймін».
E. W. Dijkstra in 1974 presented the concept of self stabilization, prompting further research in this area. His demonstration involved the presentation of self stabilizing mutual exclusion algorithms. It also showed the first self stabilizing algorithms that did not rely on strong assumptions on the system. Some previous protocols used in practice did actually stabilize, but only assuming the existence of a clock that was global to the system, and assuming a known upper bound on the duration of each system transition. It was only ten years later when Leslie Lamport pointed out the importance of Dijkstra's work at a 1983 conference called Symposium on Principles of Distributed Computing that researchers directed their attention to this elegant fault tolerance concept. In his talk, Lamport stated:<blockquote>I regard this as Dijkstra's most brilliant work at least, his most brilliant published paper. It's almost completely unknown. I regard it to be a milestone in work on fault tolerance I regard self stabilization to be a very important concept in fault tolerance and to be a very fertile field for research.
Шолу
Бөлінген алгоритм өзін-өзі тұрақтандырады, егер кез келген бастапқы күйден бастап, ол міндетті түрде заңды күйге жуысса және одан кейін заңды күйлер жиынтығында қалып отырса. Күй заңды болып есептеледі, егер осы күйден бастап алгоритм өзінің талаптарын орындаса. Өзін-өзі тұрақтандыру қасиеті үлестірілген алгоритмге оның себебіне қарамастан, уақытша қатеден қалпына келуге мүмкіндік береді. Сонымен қатар, өзін-өзі тұрақтандыру алгоритмін бастапқы күйіне қарамастан, дұрыс жұмыс істеуі үшін бастаудың қажеті жоқ, өйткені ол ақырында дұрыс әрекет ете бастайды. Өзін-өзі тұрақтандыру тұжырымдамасын енгізген Дикстраның мақаласында "токендік сақина" – шеңбер бойынша орналасқан компьютерлер желісі – мысалы келтірілген. Мұнда әрбір компьютер немесе процессор бірден алдыңғы процессордың толық күйін "көре алады", және бұл күй процессордың "токені бар" немесе "токені жоқ" екенін көрсетеді. Бұрын мұндай әрекеттер өте қиын және көп уақыт алатын болғандықтан, осы сипаттама қажетті деп есептелген. (Жоғарыда аталған мақалада сипатталған әдіс бүкіл желіден көп көлемде ақпаратты бір жерге жинап, содан кейін жиналған жаһандық күйдің дұрыс екенін анықтауға тырысады; тіпті осы анықтаудың өзі қиын міндет болуы мүмкін).
A distributed algorithm is self stabilizing if, starting from an arbitrary state, it is guaranteed to converge to a legitimate state and remain in a legitimate set of states thereafter. A state is legitimate if, starting from this state, the algorithm satisfies its specification. The property of self stabilization enables a distributed algorithm to recover from a transient fault regardless of its nature. Moreover, a self stabilizing algorithm does not have to be initialized as it eventually starts to behave correctly regardless of its initial state. Dijkstra's paper, which introduces the concept of self stabilization, presents an example in the context of a "token ring"—a network of computers ordered in a circle. Here, each computer or processor can "see" the whole state of one processor that immediately precedes it and that this state may imply that the processor "has a token" or it "does not have a token." were often very difficult and time consuming, such a behavior was considered desirable. (The method described in the paper cited above collects a huge amount of information from the whole network to one place; after that, it attempts to determine whether the collected global state is correct; even that determination alone can be a hard task).
Уақыт күрделілігі
Өзін-өзі тұрақтандыру алгоритмінің уақыт күрделілігі (синхронды емес) раундтар немесе циклдармен өлшенеді. Раунд – әрбір процессор кем дегенде бір қадам атқаратын ең қысқа орындалу тізбегі. Сол сияқты, цикл – әрбір процессор өзінің қайта-қайта орындалатын командалар тізімін кем дегенде бір толық рет орындайтын ең қысқа орындалу тізбегі. Шығыс тұрақтандыру уақытын өлшеу үшін күй айнымалыларының бір бөлігі сыртқы түрде көрінетін (шығыс) деп анықталады. Шығыстардың белгілі бір күйлері дұрыс (заңды) деп белгіленеді. Жүйенің барлық компоненттерінің шығыстары жиынтығы, егер қосымша қателер тумаса, олар дұрыс күйде қалып, осы күйге енген сәттен бастап тұрақтанған деп есептеледі. Шығыс тұрақтандыру уақыты – шығыс тұрақтанғанға дейін өтетін уақыт (асинхронды раундтардың саны).
The time complexity of a self stabilizing algorithm is measured in (asynchronous) rounds or cycles. A round is the shortest execution trace in which each processor executes at least one step. Similarly, a cycle is the shortest execution trace in which each processor executes at least one complete iteration of its repeatedly executed list of commands. To measure the output stabilization time, a subset of the state variables is defined to be externally visible (the output). Certain states of outputs are defined to be correct (legitimate). The set of the outputs of all the components of the system is said to have stabilized at the time that it starts to be correct, provided it stays correct indefinitely, unless additional faults occur. The output stabilization time is the time (the number of (asynchronous) rounds) until the output stabilizes.
Қатысушы жұмыстар
Өзін-өзі тұрақтандыру тұжырымдамасының кеңейтімі – суперстабилизация. Мұндағы мақсат – топологиялық өзгерістерге ұшырайтын динамикалық таратылған жүйелермен күресу. Классикалық өзін-өзі тұрақтандыру теориясында, кездейсоқ өзгерістер қателер ретінде қарастырылады, жүйе қайта тұрақтанғанша ешқандай кепілдік берілмейді. Суперстабилизацияланған жүйелерде жүйе топологиясы қайта конфигурацияланатын кезде әрқашан орындалатын өту предикаты болады.
An extension of the concept of self stabilization is that of superstabilization. The intent here is to cope with dynamic distributed systems that undergo topological changes. In classical self stabilization theory, arbitrary changes are viewed as errors where no guarantees are given until the system has stabilized again. With superstabilizing systems, there is a passage predicate that is always satisfied while the system's topology is reconfigured.