-Auto de stabilizare sau de auto-stabilizare , este proprietatea unui sistem distribuit care cuprinde mai multe mașini capabil să comunice unul cu celălalt, care este atunci când sistemul este inițializat sau grav perturbat, pentru a reveni automat la buna funcționare a unui număr finit de pași de calcul . A fost definit de Edsger Dijkstra în 1974 . Analizată în esență în informatică teoretică , auto-stabilizarea vizează aplicațiile din domeniile în care intervenția unui om pentru a restabili sistemul după o defecțiune este imposibilă sau în care este preferabil să se facă fără: rețele de calculatoare , senzori de rețea și sisteme critice , cum ar fi sateliți .
O rețea de senzori fără fir este o colecție de mașini mici, autonome, senzorii . Fiecare senzor are un microprocesor , o cantitate mică de memorie cu acces aleatoriu , o baterie , un radio transceiver și unul sau mai multe instrumente de măsurare: termometru , higrometru etc. Scopul unei astfel de rețele este de a reuni automat măsurătorile făcute de senzorii individuali pentru a deduce un rezultat global. Printre aplicații, rețelele de senzori pot fi desfășurate într-o pădure pentru a avertiza în caz de incendiu, într-o zonă de conflict pentru a detecta prezența inamicilor sau într-un biotop pentru a observa animalele fără a le deranja. Deoarece senzorii sunt limitați la procesoare rudimentare, puterea lor de calcul este limitată. În plus, bateriile lor sunt reduse și consumul de energie crește odată cu gama de transmisii radio, ceea ce limitează distanța comunicațiilor lor. Într-adevăr, întrucât senzorii sunt folosiți în principal în locuri greu accesibile, în general nu este planificat să se intervină asupra acestora pentru a înlocui bateria. În general, informațiile provenite de la senzori sunt recuperate de o stație de bază (diagrama opusă) care are o putere mai mare de calcul și transmisie. Ca regulă generală, senzorii sunt fixați : sunt așezați într-un loc dat și nu se pot mișca.
O rețea de senzori, pentru a fi utilă, trebuie să fie autonomă. Senzorii trebuie să își schimbe informațiile și să efectueze prelucrarea lor fără a fi nevoie niciodată de intervenție. Cu toate acestea, pot apărea multe perturbări ale sistemului. De exemplu, un senzor poate eșua sau pot fi implementați senzori noi în zonă. Auto-stabilizarea este una dintre soluțiile care permit asigurarea faptului că rețeaua de senzori se recuperează automat din aceste perturbații.
Algoritmii de auto-stabilizare pot rezolva problemele de bază specifice rețelelor de senzori, în special multiplexarea prin diviziune de timp (senzorii sunt de acord cu sloturile în care transmite doar unul dintre ele), comunicația de difuzare orientată (o metodă de rutare potrivită pentru rețelele de senzori) și funcționarea în ciuda faptului că unii senzori pot fi tăiați periodic din restul rețelei. De asemenea, există soluții de auto-stabilizare adaptate rețelelor de senzori pentru probleme convenționale, cum ar fi colorarea graficelor , calculul unui stabil maxim sau al unui copac întins sau chiar sincronizarea ceasului .
Există, de asemenea, rețele de senzori mobili , în care senzorii sunt așezați pe agenți capabili să se miște. Acest lucru oferă un nou mod de a observa animalele sălbatice fără a le perturba comportamentul prin instalarea senzorilor nu mai sunt în biotop, ci pe animalele în sine. În acest cadru au fost stabilite condițiile necesare și suficiente pentru a rezolva problema numărării autostabilizatoare, care constă în determinarea numărului de senzori prezenți în sistem. Această problemă este legată de cea a protocoalelor de populație , care au fost formulate separat și care constă în a considera sistemul ca un set de agenți cu memorie foarte limitată care se mișcă aleatoriu, capabili să facă schimb de informații atunci când se întâlnesc.
Auto-stabilizarea este definită în formalismul algoritmilor distribuiți , din care este o ramură. Definițiile de mai jos sunt limitate la ceea ce este necesar pentru a caracteriza auto-stabilizarea.
Un sistem este un set de n procese . Fiecare proces are variabile în care sunt stocate informațiile pe care le are procesul. Colecția de variabile a unui proces este starea sa .
Există două modele pentru a reprezenta comunicațiile între procese. Primul model este transmiterea mesajelor : procesele pot comunica prin trimiterea de mesaje reciproc prin canale FIFO . În acest caz, existența sau nu a unui canal între două procese date este definită de topologia rețelei . Starea unui canal este definită ca secvența de mesaje pe care le conține. Al doilea model este memoria partajată . În acest caz, există o serie de registre partajate și este necesar să se definească ce procese pot citi și scrie în ce registre. Starea unui registru este valoarea pe care o conține. Configurația sistemului este colectarea de starea tuturor proceselor și de comunicare.
O etapă c → c 'a sistemului este definită ca executarea unei tranziții printr-un proces astfel încât sistemul se află inițial în configurația c, apoi, prin efectuarea unei acțiuni, trece la configurația c'. În timpul unei tranziții, un proces poate primi un mesaj (resp. Citiți un registru partajat în cazul unui model de memorie partajată), schimba starea și trimite mesaje (resp. Scrieți în registre partajate ).
O execuție este o secvență alternativă infinită de configurații și pași: E = (c 0 , a 1 , c 1 , a 2 , c 2 , ...) astfel încât pentru toate i> 0, acțiunea a i face ca sistemul să meargă de la configurația c i-1 la configurația c i . Se spune că este corect dacă nu conține o secvență infinită de pași în timpul cărora s-ar putea executa o anumită tranziție, dar niciodată nu este. Cu alte cuvinte, în cadrul unei execuții corecte, niciun proces nu este privat de capacitatea de a face o anumită tranziție.
Pentru orice sistem de auto-stabilizare, definim un set ℒ de execuții legitime . Acest set reprezintă cursele în care sistemul se comportă întotdeauna corect. Se spune că o configurație c este sigură față de ℒ dacă și numai dacă orice execuție care începe cu c este în ℒ. Un sistem se auto-stabilizează către ℒ dacă și numai dacă orice execuție a acestui sistem, indiferent de configurația de pornire, ajunge la o configurație sigură în ceea ce privește ℒ.
Un sistem se auto-stabilizează dacă și numai dacă putem asocia cu orice configurație o valoare luată într-un inel noetherian astfel încât fiecare pas al execuției care începe într-o configurație nesigură a valorii v face ca sistemul să treacă într-o configurație a valorii v ' <v, iar valorile inferioare ale inelului corespund configurațiilor sigure. Această proprietate, demonstrată de Gouda, poate fi utilizată pentru a demonstra că un algoritm se auto-stabilizează, în același mod în care poate fi utilizată pentru a demonstra că un algoritm secvențial se oprește .
Măsurarea eficienței unui algoritm face obiectul analizei complexității algoritmilor . Acesta definește metode pentru calcularea performanței unui algoritm, în principal pe două axe: timpul de calcul și cantitatea de memorie utilizată . În cazul auto-stabilizării, timpul de stabilizare este definit ca cel mai lung timp pe care îl poate dura sistemul pentru a ajunge la o configurație sigură. Într-un sistem asincron , care nu are noțiune de timp, definim o rundă ca cea mai scurtă secvență de pași ai execuției în timpul căreia fiecare proces este activat cel puțin o dată, ceea ce dă o unitate în care putem exprima un timp de stabilizare. Celelalte măsuri de complexitate definite în sistemele distribuite se aplică și în auto-stabilizare: este astfel posibil să căutăm să schimbăm cât mai puține mesaje sau să folosim un minim de memorie pe fiecare proces.
În urma oricărui incident care schimbă starea sistemului, autostabilizarea asigură că, după o anumită perioadă de funcționare fără alte incidente, revine automat la executarea legitimă și, prin urmare, la corectarea funcționării. În special, acest lucru face posibilă tolerarea oricăror eșecuri tranzitorii , o modificare arbitrară a stării unui proces în timpul unei execuții. O astfel de defecțiune poate fi cauzată, de exemplu, de o rază cosmică care lovește un circuit integrat . Poate fi cauzată și de o funcționare deficitară a sistemului, în special supraîncălzirea sau overclocking-ul . O defecțiune tranzitorie lasă sistemul într-o configurație complet imprevizibilă. Această revenire automată la normal este de dorit în special într-un sistem pe care nu este posibil să se implice un tehnician, de exemplu un satelit.
În majoritatea sistemelor informatice, programul în sine este stocat în memorie RAM. Ca rezultat, este predispus la eșecuri tranzitorii, ceea ce previne auto-stabilizarea. Soluția este salvarea programului în ROM . Dacă programul trebuie încărcat în RAM, un câine de pază îl poate reîncărca de pe ROM, dacă este necesar. O altă posibilitate este de a produce programul direct sub forma unui circuit integrat.
Conceptul de auto-stabilizare este formulat pentru prima dată de Dijkstra în 1974 într-un articol care prezintă trei algoritmi de auto-stabilizare bazate pe conceptul inelului token . Principiul inelului de jetoane este de a rezolva problema excluderii reciproce prin circulația unui jeton , care reprezintă dreptul ca singurul proces care îl deține să efectueze o acțiune care ar fi problematică dacă mai multe procese ar efectua-o în același timp, pentru exemplu trimiterea de text către o imprimantă : un proces care dorește să imprime trebuie să aștepte mai întâi pentru a primi simbolul, apoi să trimită textul acestuia la imprimantă; după care pierde simbolul. În cazul unui inel de jetoane auto-stabilizabil, dacă sistemul este deranjat de introducerea unuia sau mai multor jetoane suplimentare, acesta se recuperează singur de la acest eșec prin eliminarea tuturor jetoanelor prezente pe inel, cu excepția unuia.; apoi își continuă execuția trecând singurul indicativ rămas ca și când nu ar fi existat niciodată altul.
Procesele n (cu n impar ), numerotate de la 0 la n-1, sunt conectate într-un inel , adică procesul este ca vecin în dreapta i + 1 modul n și ca vecin în stânga i-1 modulo n. Cu alte cuvinte, vecinul stâng al procesului 0 este procesul n-1 și vecinul drept al procesului n-1 este procesul 0. Fiecare proces are o stare întreagă între 0 și 2. Notăm prin É starea d 'un proces, D starea vecinului său din dreapta și G cea a vecinului său din stânga.
Algoritmul prezentat mai jos este al treilea din articol, pe care Dijkstra îl consideră cel mai de succes. Execuția de siguranță este dată pentru a arăta cum se comportă normal sistemul, și apoi este abordată problema eliminării privilegiilor supranumerare.
La fiecare pas al execuției, un proces este ales în mod arbitrar de către un planificator . În practică, acest programator depinde de hardware, de sistemul de operare și de mediul în care operează; comportamentul său este deci imprevizibil. Arbitrariul acestei alegeri stă la baza motivației inițiale a lui Dijkstra, care investighează dacă un sistem se poate comporta corect în ciuda controlului distribuit . În acest algoritm, numai procesele care au un privilegiu pot reacționa atunci când sunt alese, schimbând starea. Privilegiile și modificările de stare asociate sunt definite de următoarele reguli:
Aici, privilegiul reprezintă faptul că un proces deține un simbol. Pentru a înțelege cum funcționează acest algoritm atunci când există un privilegiu unic, luați în considerare cazul opus. Numerele procesului sunt în negru, stările în albastru. Procesul 0 are un privilegiu, concretizat în roșu, în aplicarea regulii 1. Într-adevăr, starea sa este 1; adăugând 1, obținem 2, care este starea vecinului său din dreapta. Pe de altă parte, niciun alt proces nu are privilegiu: procesul 4 deoarece stările vecinilor săi nu sunt egale, celelalte procese deoarece niciun proces nu are starea (2 + 1) mod 3 = 0.
În timpul primului pas de execuție, prin urmare, procesul 0 schimbă starea. În aplicarea regulii 1, este nevoie de starea 1-1 = 0. Aceasta oferă un privilegiu procesului 1, care, prin urmare, schimbă starea în etapa următoare a execuției. Continuă după cum urmează:
Configurare (2)
Configurare (3)
Configurare (4)
Configurare (5)
În configurația (5), procesul 4 are privilegiul. Prin urmare, schimbă starea în aplicarea regulii 2, luând starea 0 + 1 = 1. Acest lucru oferă privilegiul procesului 3.
Configurare (6)
Configurare (7)
Configurare (8)
Configurare (9)
Privilegiul a fost trecut, pas cu pas, tuturor proceselor. Configurarea (9) este echivalentă cu configurația (1); prin urmare, sistemul este gata să înceapă să treacă din nou privilegiul conform aceluiași principiu. Observația că „totul merge bine” arată, în mod informal, că această execuție este legitimă.
Pentru a înțelege cum algoritmul garantează că numărul de privilegii ajunge în mod necesar la 1, trebuie mai întâi să observăm că regulile nu permit nicio situație în care nu ar exista un privilegiu. Într-adevăr, în virtutea regulii 3, într-o astfel de configurație, procesele ale căror numere merg de la 1 la n-2 trebuie să aibă toate aceeași stare e; în plus, procesele 0 și n-1 trebuie să aibă fie starea e, fie starea (e-1) mod 3. Acum, dacă procesul 0 are starea (e-1) mod 3, atunci are un privilegiu; dacă procesul n-1 are starea (e-1) mod 3, atunci are privilegiu.
Dovada corectitudinii acestui algoritm, publicată în 1986 , se bazează pe faptul că, dacă există mai multe privilegii, atunci numărul lor trebuie să scadă în mod necesar. Pentru aceasta, Dijkstra demonstrează că între două schimbări de stare a procesului n-1, apare neapărat o schimbare de stare a procesului 0. El demonstrează apoi că nu există o succesiune de pași infiniti în care procesul 0 nu schimbă starea. În cele din urmă, el enumeră scenariile posibile pentru comportamentul privilegiului situat cel mai departe la stânga pe ring și demonstrează că acest privilegiu dispare. Prin recurență , după un anumit număr de pași, există în sfârșit un singur privilegiu.
Primul caz de coliziune
Al doilea caz de coliziune
Pentru a vedea cum dispar privilegiile supranumerare, este suficient să vedem, în execuția normală de mai sus, că privilegiile curg de la stânga la dreapta din procesul 0 și de la dreapta la stânga din procesul n- 1. Drept urmare, dacă există două privilegii pe ring, acestea ajung să se întâlnească. Această situație este ilustrată mai sus de primul caz de coliziune, în care nu este implicat nici procesul 0, nici procesul n-1. În acest caz, de îndată ce unul dintre procesele privilegiate își schimbă starea, acesta își pierde privilegiul în timp ce celălalt proces își păstrează propriul: numărul de privilegii a scăzut cu 1.
Cazul coliziunii proceselor 0 și 1 este deosebit (al doilea caz de coliziune de mai sus). Într-adevăr, dacă 1 schimbă starea, privilegiul său schimbă pur și simplu „direcția”, mergând acum de la stânga la dreapta. Cu toate acestea, poate trece prin procesul n-1 și, prin urmare, trebuie să dispară. Dacă procesul 0 schimbă starea, în mod analog, privilegiul său trece la procesul n-1.
Dijkstra nu abordează problema timpului de stabilizare a algoritmului său, nici în articolul său original din 1974, nici în articolul din 1986 în care dă dovada corectitudinii. În 2007, o echipă fără legătură cu Dijkstra a demonstrat că acest algoritm se stabilizează în trepte O (n²).
Deși algoritmul prezentat mai sus a fost folosit în producție, articolul lui Dijkstra a trecut aproape neobservat până când Leslie Lamport , invitat în 1984 să susțină o prezentare la conferința PODC, a menționat-o ca fiind demnă de menționat. Auto-stabilizarea devine apoi un subiect în sine în algoritmi distribuiți, pe care Lamport îl consideră una dintre cele mai importante contribuții ale sale la calcul. Studenții susțin teze de doctorat despre auto-stabilizare și se specializează în cercetări pe acest subiect. Auto-stabilizarea este predată la universitate ca parte a cursurilor de algoritmi distribuiți.
În 2000, a fost lansată auto-stabilizarea , o carte scrisă de Shlomi Dolev, prima dedicată în întregime auto-stabilizării. Ulterior, mai mulți algoritmi distribuiți și manuale de programare dedică un capitol acestui subiect. Dijkstra a primit PODC Influential Article Award pentru articolul său din 1974 în 2002 , cu puțin înainte de moartea sa. În anul următor, acest premiu a fost redenumit Premiul Dijkstra în memoria sa.
O întâlnire internațională pe tema auto-stabilizării a fost lansată în 1989 sub numele WSS, Workshop on Self-Stabilizing Systems . În 2003 , după cinci ediții ale atelierului, întâlnirea a devenit o renumită conferință internațională SSS, Simpozionul asupra sistemelor de auto-stabilizare . În 2005 , conferința și-a extins subiectul pentru a deveni Simpozion privind stabilizarea, siguranța și securitatea sistemelor distribuite . De la ediția din 2003, lucrările au fost publicate sub formă de carte .
Cercetările privind auto-stabilizarea oferă o mai bună înțelegere a modului în care este posibil să construim un algoritm de auto-stabilizare. Este posibil să-l obțineți automat dintr-un algoritm clasic distribuit prin intermediul unui stabilizator sau prin compunerea mai multor algoritmi care se auto-stabilizează. Pe de altă parte, analiza problemei funcționării la nivel scăzut arată condițiile pe care echipamentul trebuie să le îndeplinească pentru a permite funcționarea autostabilizării.
Un stabilizator este un algoritm care face ca orice algoritm distribuit să se auto-stabilizeze. Cea mai cunoscută soluție pentru obținerea unui stabilizator este de a oferi unui proces distinct rolul de a examina întregul sistem, care implică obținerea și înregistrarea stării tuturor celorlalte procese și apoi, dacă este necesar, resetarea sistemului. Zero într-o auto-stabilizare cale. Această metodă este prea costisitoare în memorie și în numărul de mesaje schimbate pentru a fi viabilă în practică.
Reutilizarea algoritmilor este o întrebare clasică în ingineria software . În contextul auto-stabilizării, se pune în acești termeni: presupunând algoritmi de auto-stabilizare date, este posibil să le combinăm pentru a obține un algoritm global sau trebuie să rescriem totul de la început de fiecare dată? Compoziția echitabilă prevede răspunsul: în anumite condiții, reutilizarea autostabilisants algoritmi este posibil.
Introdus de Shlomi Dolev, Amos Israeli și Shlomo Moran în 1989 și dezvoltat de aceiași autori în 1993 , se bazează pe două observații. În primul rând, un algoritm Q care nu scrie în variabilele citite de un algoritm nu poate interfera cu acesta pentru a se stabiliza. În al doilea rând, deoarece P se auto-stabilizează, Q poate citi variabilele lui P în timpul propriei stabilizări: într-adevăr, se garantează prin definiție că valorile acestor variabile devin în cele din urmă corecte; din acest moment, Q se stabilizează normal.
Prin urmare, este posibil să fuzionăm algoritmii P și Q, prin simpla adăugare a codurilor și variabilelor acestora, pentru a forma un nou algoritm, notat P⊕Q (a se vedea diagrama de mai jos). Acest nou algoritm se auto-stabilizează, cu condiția ca niciunul dintre algoritmi să nu-l poată bloca pe celălalt; prin urmare, este necesar să se solicite ca, în orice execuție a sistemului global, fiecare dintre cei doi algoritmi să efectueze un număr infinit de pași. Această ultimă condiție garantează corectitudinea ordonării între cei doi algoritmi, de unde și termenul de compoziție corectă .
Este astfel posibil să proiectăm un algoritm de auto-stabilizare într-un mod modular , împărțindu-l în sub-algoritmi specializați care să fie compuși pentru a obține algoritmul final. Dacă un algoritm a fost deja scris pentru o sarcină dată, acesta poate fi reutilizat. De exemplu, dacă vrem să circulăm un jeton pe un sistem a cărui topologie nu este într-un inel, este suficient să alcătuim algoritmul Dijkstra cu un algoritm de construcție a topologiei din care poate fi extras un inel.
Pentru ca un sistem să se autostabilizeze cu adevărat, hardware-ul pe care rulează trebuie să fie conceput pentru acesta. Într-adevăr, hardware-ul sau firmware - ul său pot conține erori care îl provoacă să se blocheze . Prin urmare, este necesar să se asigure că microprocesorul nu poate fi blocat intrând într-o stare din care nu mai poate ieși. Cercetările în acest domeniu au făcut posibilă identificarea precisă a condițiilor pe care trebuie să le îndeplinească microprocesorul, diferitele componente hardware de bază și software-ul care le utilizează, astfel încât să permită auto-stabilizarea: microprocesorul, sistemul de operare, driverele de dispozitiv și sistem de fișiere . În general, acest lucru este pentru a se asigura că nu este posibilă nici o blocare, nici într-o stare din care sistemul nu poate ieși, nici într-un set de stări în care ar rula la nesfârșit într-o buclă . Un compilator de conservare a stabilizării a fost conceput pentru a face posibilă scrierea de programe care profită de aceste hardware și software: dacă este prevăzut cu un program de auto-stabilizare, produce codul mașinii respectând același concept de evitare a blocării. Pe baza acestor rezultate a fost depus un brevet.
În funcție de circumstanțe și de problemele puse, auto-stabilizarea este uneori considerată a fi inutilă restrictivă sau, dimpotrivă, insuficient de puternică. Aici intervin variații, relaxări sau întăriri ale definiției de bază.
Pseudo-stabilizarea, sau pseudo-auto-stabilizarea, este o relaxare a constrângerilor de auto-stabilizare. În loc să solicităm fiecare execuție să se încheie cu ℒ, avem nevoie de fiecare execuție pentru a efectua o sarcină abstractă , adică un predicat al sistemului. De exemplu, pentru a specifica excluderea reciprocă, se poate cere ca toate procesele din sistem să aibă un privilegiu dat infinit de des, dar că două procese nu o au niciodată în același timp. Acest lucru nu permite definirea execuțiilor legitime, deoarece acestea trebuie să se bazeze pe starea sistemului; totuși, în definiția unei sarcini abstracte, acest lucru este imposibil, deoarece nu știm nimic despre modul în care se desfășoară procesele. Pseudo-stabilizarea este mai slabă și mai puțin restrictivă decât auto-stabilizarea, deoarece orice sistem de auto-stabilizare este pseudo-stabilizant, dar invers este fals. Burns, Gouda și Miller, care au introdus această noțiune în 1993, consideră că, în general, este suficientă în practică.
Prima buclă
Pierderea unui mesaj
A doua buclă
Exemplul clasic de pseudo-stabilizare ilustrat mai sus este un sistem în care două procese schimbă mesaje. În funcționare normală, sistemul este în starea A; trimite un mesaj, care pune sistemul în starea S; celălalt proces primește mesajul, care pune sistemul în starea B; al doilea proces la rândul său trimite un mesaj, care pune sistemul în starea T; primul proces primește mesajul, iar sistemul este din nou în starea A. Problema este că canalul prin care trec mesajele poate pierde un mesaj, caz în care sistemul se recuperează din această pierdere intrând în starea A '. Definiția lui A 'depinde în totalitate de metoda utilizată pentru a recupera din pierderea mesajului; este deci necunoscut la nivelul sarcinii abstracte. Din A ', execuția continuă în mod similar: A', S ', B', T ', A' etc.
Deoarece pierderea unui mesaj poate apărea, sistemul nu se auto-stabilizează față de bucla A, S, B, T. Pe de altă parte, această pierdere a mesajului nu se poate întâmpla niciodată, astfel încât sistemul să nu fie auto-stabilizat. stabilizându-se fie spre bucla A ', S', B ', T', nici spre setul de stări posibile. Pe de altă parte, acest sistem, fără a se auto-stabiliza, este într-adevăr pseudo-stabilizator pentru sarcina abstractă conform căreia cei doi procesoare schimbă mesaje la rândul lor, deoarece pierderea unui mesaj nu pune în discuție această definiție.
Ideea de superstabilizare, introdusă de Shlomi Dolev și Ted Herman, este să ia în considerare schimbarea topologiei, adică adăugarea sau eliminarea unei legături de comunicare în sistem, ca un eveniment special despre care este notificat orice proces afectat și care declanșează o procedură numită secțiunea de întrerupere . Prin aceasta, sistemul este capabil să se asigure că o anumită proprietate de siguranță , predicatul de trecere , rămâne întotdeauna verificat în timpul stabilizării atunci când are loc o schimbare de topologie dintr-o configurație sigură. Acest lucru întărește garanțiile date de sistem în fața unui tip de eșec care este foarte frecvent în practică. Mai multe probleme algoritmice de bază distribuite au fost rezolvate printr-un algoritm superstabilizant, de exemplu excluderea reciprocă, construirea unui copac întins și construcția unui copac Steiner .
În loc să lăsați sistemul să își aplice algoritmul și să se corecteze, dacă este necesar, este posibil să faceți invers: monitorizați constant sistemul pentru inconsecvențe și corectați-le imediat, înainte de a lăsa un pas. Astfel, sistemul se comportă întotdeauna conform specificațiilor sale: se auto-stabilizează în trepte zero. Prin urmare, un sistem de stabilizare instantaneu este perfect rezistent la eșecurile tranzitorii, fără ca observatorul să observe că au apărut.
Pentru moment, doar câțiva algoritmi de bază, de stabilizare instantanee, au fost dezvoltați, de exemplu pentru problema deplasării în profunzime a oricărei rețele identificate sau a comunicației punct la punct într-o rețea comutată . Este posibil să stabilizați instantaneu orice algoritm de auto-stabilizare în memoria partajată, dar transformarea are un cost ridicat. În cele din urmă, stabilizarea instantanee poate fi utilizată în sistemele de transmitere a mesajelor, dar din nou, la un cost suplimentar considerabil.
Într-o versiune extinsă a lucrării sale seminale, Dijkstra stabilește că nu poate exista un algoritm de inel de token auto-stabilizator în care toate procesele să fie aceleași, cu excepția cazului în care dimensiunea inelului este un număr prim . În 1990 , Ted Herman a adus o modalitate de a depăși această limitare: forțarea planificatorului să se comporte nu mai mult într-un mod nedeterminist, ci într-un mod probabilistic , având ca dovadă a conceptului următorul algoritm probabilistic de inel de token auto-stabilizator: numărul proceselor este ciudat, iar starea fiecărui proces este de un bit , care poate fi deci doar 0 sau 1. Un proces are un simbol dacă și numai dacă starea sa este aceeași cu cea a vecinului său din stânga. În configurația (1) de mai jos, procesul 0 are un token, deoarece starea sa este 1, la fel ca procesul 4, și niciun alt proces nu are un token. Orice proces care are un simbol este probabil să fie ales de planificator pentru a schimba starea. În acest caz, noua sa stare este trasată la întâmplare: 0 sau 1, cu probabilitate ½.
Configurare (1)
Configurare (2)
Interpretarea acestei reguli în practică este că procesul are o șansă una din două de a-și păstra simbolul și o șansă una din două de a o transmite la următorul proces pe ring. În configurația (1), dacă procesul care are simbolul trage starea 1, nimic nu se schimbă. Dacă trage starea 0, nu mai are jetoane, deoarece noua sa stare este identică cu cea a vecinului său din stânga. În schimb, procesul 1 are acum un simbol, deoarece are aceeași stare ca vecinul său din stânga.
În configurația (2), trei procese au un simbol. În funcție de procesul ales de planificator și de rezultatul extragerii, după un pas al execuției, pot rămâne trei jetoane sau doar unul. Astfel, dacă se alege procesul 1, acesta își poate păstra jetonul sau îl poate trece la procesul 2, care nu modifică numărul de jetoane. Dar dacă procesul 0 este ales și trage starea 0, nu numai că își pierde simbolul, dar și procesul 1 își pierde simbolul. Un planificator nedeterminist, precum cel folosit de Dijkstra, ar putea forța procesele să-și transmită jetoanele fără a le pierde vreodată, dar un planificator probabilist nu poate, deoarece pierderea jetonului are o probabilitate strict pozitivă: în timpul unei execuții infinite, deci are loc cu probabilitatea 1.
În cazul unui algoritm probabilistic, nu este posibil să se calculeze un timp de stabilizare, deoarece acest lucru depinde de extragerile aleatorii. Pe de altă parte, este posibil să-i calculăm așteptările . Inițial, Herman arată că așteptarea timpului de stabilizare a algoritmului său este O (n² log n) pași. Un calcul mai precis arată ulterior că această așteptare este exact Θ (n²) pași. Cercetări mai recente oferă un cadru general bazat pe teoria lanțului Markov pentru efectuarea acestor calcule de complexitate în modelul probabilistic.
: document utilizat ca sursă pentru acest articol.
De la ediția din 2003, lucrările conferinței SSS au fost publicate ca cărți în colecția Lecture Notes in Computer Science de Springer Verlag . Autostabilizarea a fost singura temă a conferinței până în 2005, una dintre temele principale de după aceea.