Următorul conținut este furnizat sub o licență Creative Commons. Sprijinul dumneavoastră va ajuta MIT OpenCourseWare să continue să ofere gratuit resurse educaționale de înaltă calitate. Pentru a face o donație sau pentru a vedea materiale suplimentare din sute de cursuri MIT, vizitați MIT OpenCourseWare la ocw.mit.edu. PROFESORUL: Bine, bine ai revenit. Aceasta este a doua jumătate a celor două prelegeri ale noastre despre algoritmi distribuiți săptămâna aceasta. Aș putea activa asta, OK. În regulă, voi începe cu o previzualizare rapidă. Săptămâna aceasta, ne uităm doar la algoritmi distribuiți sincroni și asincroni , fără a ne îngrijora de lucruri interesante, cum ar fi eșecurile. Ultima dată ne-am uitat la alegerea liderului, setul independent maxim, copacii care se întind pe lățimea întâi și am început să ne uităm la copacii cu cele mai scurte căi. Vom termina asta astăzi și apoi vom trece la subiectul principal pentru astăzi, care este algoritmii distribuiți asincron, în care lucrurile încep să devină mult mai complicate, deoarece nu totul se întâmplă în runde sincrone. Și vom revedea aceleași două probleme, pe lățimea întâi și pe căile cele mai scurte care se întind pe copaci. Revizuire rapidă, toți algoritmii noștri folosesc un model care se bazează pe un grafic nedirecționat. Folosind această notație, gamma, pentru vecinii unui vârf. Vom vorbi despre gradul unui vârf. Avem, deci, un proces asociat cu fiecare vârf din grafic. Și asociem canale de comunicare în ambele direcții pe fiecare margine. Ultima dată ne-am uitat la algoritmi distribuiți sincroni în modelul sincron. Avem procesele vârfurilor solului, ele comunică folosind mesaje. Procesele au porturi locale pe care le cunosc după un fel de nume local, iar porturile se conectează la canalul lor de comunicare. Algoritmul se execută în runde sincrone în care, în fiecare împrejur, fiecare proces va decide ce să trimită pe toate porturile sale, iar mesajele sunt apoi introduse în canalul livrat proceselor de la celălalt capăt. Și toată lumea se uită la toate mesajele pe care le primește la acea rundă dintr-o dată și determină o nouă stare. Ei calculează o nouă stare pe baza tuturor acestor mesaje care sosesc. Am început cu alegerea liderului. Nu voi repeta definiția problemei, dar iată rezultatele pe care le-am obținut data trecută. Ne-am uitat la un caz special al unui grafic care este doar o simplă clică. Și dacă procesele nu au informații distinctive, cum ar fi identificatorii unici, și sunt deterministe, atunci nu există nicio modalitate de a rupe simetria și puteți dovedi un rezultat imposibil care spune că nu puteți... într-un determinist, caz indistinguibil, nu puteți garanta că alegeți un lider într-un astfel de grafic. Deoparte, ar trebui să spun că teoria calculatoarelor distribuite este plină de rezultate de imposibilitate și toate se bazează pe această limitare a calculului distribuit în care fiecare nod știe doar ce se întâmplă cu el însuși și în vecinătatea lui. Nimeni nu știe ce se întâmplă în întregul sistem. Aceasta este o limitare foarte puternică și, așa cum v-ați aștepta, ar face multe lucruri imposibile sau dificile. Apoi am continuat și am obținut două rezultate pozitive, o teoremă care... ei bine, un algoritm care este determinist, dar procesele au identificatori unici și apoi poți alege rapid un lider. Sau dacă nu aveți identificatori unici, dar aveți probabilitate, astfel încât să puteți face alegeri aleatorii, puteți alege în esență un identificator și apoi funcționează aproape la fel de bine cu acești identificatori. Apoi ne-am uitat la setul independent maxim. Amintiți-vă ce înseamnă, nu ar trebui să fie doi vecini în set, dar nu doriți să puteți adăuga mai multe noduri, păstrând aceste noduri independente. Cu alte cuvinte, fiecare nod este fie în mulțime, fie are un vecin în mulțime. Și am dat acest algoritm-- Îl includ aici doar ca o reamintire-- algoritmul lui Luby , care practic trece printr-un număr de faze. În fiecare fază, unele procese decid să se alăture MIS, iar vecinii lor decid să nu se alăture, iar tu doar repeți acest lucru. Faceți acest lucru pe baza alegerii ID-urilor aleatorii din nou. Și am demonstrat că teorema calculează corect un MIS și, cu o probabilitate bună, toate nodurile decid doar în faze logaritmice și aici este numărul de noduri. În regulă, apoi am trecut la copacii care se întind în lățime. Aici, avem acum un grafic care are deja un lider. Are un vârf distins. Iar procesul care stă acolo știe că este liderul. Procesele acum vor produce un arbore care se întinde pe lățimea întâi, înrădăcinat la acel vârf. Acum, pentru restul timpului, vom presupune identificatori unici, dar procesele nu știu nimic despre grafic, cu excepția propriului lor ID și a vecinilor lor. Și dorim ca procesele să scoată în cele din urmă ID-ul părintelui lor. Și iată, doar ca să repet, algoritmul simplu pe care l-am folosit. Practic, procesele se marchează pe măsură ce sunt incluse în arbore. Începe doar cu rădăcina marcată. El trimite un mesaj special de căutare vecinilor săi și, imediat ce îl primesc, sunt marcați și îl transmit mai departe. Toată lumea este marcată într-un număr de runde care corespunde adâncimii lor în-- distanța lor de la rădăcina copacului, [INAUDIBIL] de copac. Am vorbit despre corectitudine în termeni de invarianță. Ceea ce garantează acest algoritm este, la sfârșitul oricărui număr r de runde, exact procesele de la distanță până la r sunt marcate, iar procesele care sunt marcate au părinții definiți. Și dacă părinții tăi au definit-- este UID-ul unui proces care are distanța d minus 1 de la rădăcină. Dacă ești la distanța d, părintele tău ar trebui să fie cineva care are dreptate-- are distanța corectă d minus 1. Analizăm complexitatea. Timpul numără numărul de runde. Și acesta va fi, în cel mai rău caz, diametrul rețelei. Este într-adevăr distanța de la un anumit vârf, v 0. Și complexitatea mesajului - există un singur mesaj trimis în fiecare direcție pe fiecare muchie, așa că va fi doar ordinea numărului de muchii. Și am vorbit despre cum puteți obține indicații pentru copii. Acest lucru vă oferă doar părinți. Dar dacă vrei să-ți afli și copiii, atunci fiecare mesaj de căutare ar trebui să primească un răspuns fie că ești părintele meu, fie că nu ești părintele meu. Și putem face o terminare folosind convergecast și sunt câteva aplicații despre care am vorbit, de asemenea. Bine, și apoi, la sfârșitul orei, am început să vorbim despre o generalizare, un arbore care se întinde pe lățimea întâi, care adaugă greutăți, astfel încât să aveți cele mai scurte căi de copaci. Acum ai greutăți pe margini. Procesele au încă identificatori unici. Ei nu știu nimic despre grafic, cu excepția informațiilor din vecinătatea lor imediată. Și trebuie să producă un arbore care se întinde pe calea cea mai scurtă înrădăcinată la vârful v 0. Știți ce este un arbore care se întinde și cele mai scurte căi sunt în ceea ce privește greutatea totală a căii. Acum dorim ca fiecare nod, fiecare proces, să-și scoată părintele pe calea cea mai scurtă. Și, de asemenea, distanța de la vârful original v 0. La sfârșitul orei, ne-am uitat la o versiune a lui Bellman-Ford, pe care ați văzut-o deja ca un algoritm secvenţial. Dar, ca algoritm distribuit, toată lumea ține evidența cea mai bună estimare, cea mai bună estimare curentă, a distanței de la vârful inițial. Și țin evidența părintelui lor pe o cale care i-a dat această estimare a distanței și își păstrează identificatorul unic. Algoritmul complet acum este că toată lumea va continua să-și trimită distanța în jur... Vreau să spun că am putea optimiza asta, dar acest lucru este simplu. La fiecare rundă, toată lumea trimite estimarea actuală a distanței tuturor vecinilor. Ei colectează estimările de distanță de la toți vecinii lor, iar apoi fac un pas de relaxare. Dacă obțin ceva mai bun decât ceea ce au avut înainte, se uită la cea mai bună estimare nouă pe care ar putea-o obține. Ei iau minimul din vechea lor estimare - nu mai tremura, bine - și minimul tuturor estimărilor pe care le- ar obține uitându-se la informațiile primite plus adăugând greutatea marginii dintre expeditor și nodul însuși. În acest fel, puteți obține o estimare mai bună. Și dacă o faci, ți- ai reseta părintele să fie expeditorul acestor informații îmbunătățite. Și din nou, puteți alege -- dacă există o egalitate, puteți alege oricare dintre nodurile care simt -- informațiile care duc la cea mai bună presupunere nouă, puteți seta părintele dvs. la oricare dintre acestea. Și apoi asta doar se repetă. La sfârșitul orei, am arătat o animație, pe care nu o voi repeta acum, care arată, practic, cum puteți obține o mulțime de corecții. Puteți avea multe căi care sunt configurate care arată bine după o singură rundă, dar apoi sunt corectate pe măsură ce rundele continuă. Obțineți căi de greutate mult mai mici dacă aveți o cale giratorie, cu mai multe hop către un nod. Puteți obține un cost total mai bun. Iată unde am ajuns ultima dată. Acum de ce funcționează asta? Ei bine, ceea ce avem nevoie este, în cele din urmă, fiecare proces ar trebui să obțină distanța corectă. Și părintele ar trebui să fie predecesorul său pe calea cea mai scurtă . Pentru a demonstra că-- cauți întotdeauna un invariant, ceva care este adevărat, la pașii intermediari ai algoritmului pe care îi poți arăta prin inducție va ține-- și asta va implica rezultatul pe care îl vrei la sfârșit. Iată, care este cheia invariantă? La sfârșitul unui număr r de runde, ce au procesele? După ce au trecut r runde, în acest tip de algoritm, cum arată estimările? Ei bine, după o rundă, toată lumea are cea mai bună estimare care s-ar putea întâmpla pe un singur -- care ar putea rezulta dintr-o singură cale de salt de la v 0. După două runde, obțineți și cele mai bune presupuneri din două căi de salt și după r runde in general, ai distanta si parinte corespunzator unui drum cel mai scurt ales dintre cele care au cel mult hopurile noastre. Da? Are sens? Nu? Da? BINE. În regulă, și dacă nu există o cale de r salturi sau mai puține pentru a ajunge la un nod, distanța lor va fi estimată la infinit după r runde. Aceasta nu este o dovadă completă, dar este invariantul cheie care face ca acest lucru să funcționeze. Puteți vedea că, după suficiente runde corespunzătoare numărului de noduri, de exemplu, toată lumea va avea cea mai scurtă cale corectă de orice lungime. BINE? Numărul de runde până când fiecare estimare se stabilizează -- toate estimările se stabilizează, va fi n minus 1. Bine? Deoarece cea mai lungă cale simplă către orice nod va fi n minus 1, dacă trece prin toate nodurile rețelei înainte de a ajunge la ea. Are sens? Dacă doriți să vă asigurați că aveți cea mai bună estimare, trebuie să așteptați n minus 1 runde pentru a vă asigura că informațiile au ajuns la dvs. Complexitatea mesajului - ei bine, din moment ce există toate aceste estimări repetate, nu mai este doar proporțională cu numărul de margini, ci trebuie să țineți cont de faptul că pot fi multe estimări noi trimise pe fiecare margine. De fapt, așa cum am scris asta, pur și simplu tot trimiți distanța la fiecare rundă. Va fi numărul de margini înmulțit cu numărul de runde. Puteți face ceva mai bine decât asta, dar este mai rău decât simplul caz BFS. Acest lucru este mai scump, deoarece BFS avea doar runde de diametru și acum are n pentru n minus 1 runde, iar BFS doar a avut un mesaj trimis vreodată pe fiecare margine, iar acum trebuie să trimitem multe. Comentarii? Întrebări? Este clar că timpul legat într- adevăr depinde de n și nu de diametru? Pentru căutarea pe lățimea întâi, a fost suficient să aveți suficiente runde care să corespundă distanței reale și sărituri către fiecare nod, dar acum aveți nevoie de suficiente runde pentru a avea grijă de aceste căi indirecte care ar putea trece prin multe noduri, dar totuși ajung cu un mai scurt-- cu o greutate totală mai mică. Este clar pentru toată lumea de ce limita depinde de n? De fapt, animația pe care am avut-o data trecută a arătat că există o mulțime de corecții și ai avut destule-- ai avut runde care depindeau de numărul total de noduri. Da? BINE. Da? AUDIENTA: Dar ai putea tine evidenta fiecarei runde daca valorile-- daca vreuna dintre [INAUDIBLE]? Dacă... dacă totul se oprește după mai puțin de n runde, atunci s- ar putea să nu trebuiască să... PROFESORUL: Bine, deci întrebi despre terminare? PUBLIC: Da. PROFESORUL: Ah, bine, deci probabil acesta este următorul diapozitiv. Mai întâi, să ne ocupăm de indicatorii copii, apoi vom reveni la terminare. În primul rând, asta îți oferă doar părinții tăi. Dacă vrei copiii tăi, poți face același lucru pe care l-am făcut noi data trecută. Atunci când un proces primește un mesaj, iar mesajul nu îl face pe expeditor părinte, acest lucru nu îi oferă o distanță îmbunătățită. Apoi nodul poate doar să răspundă, non-părinte. Dar dacă un proces primește un mesaj care nu îmbunătățește distanța, acesta spune: OK, ești părintele meu, dar s-ar putea să-i fi spus și unui alt nod-- ar putea avea un alt părinte, un alt nod pe care anterior îl credea părinte. . Trebuie să lucreze mai mult , în acest caz, pentru a corecta informațiile eronate ale părintelui. Trebuie să trimită părintelui său anterior un mesaj non-părinte pentru a corecta mesajul părintelui anterior. Lucrurile devin puțin mai complicate aici. Pe de altă parte, dacă cineva urmărește copiii săi, trebuie să facă și ajustări, deoarece lucrurile se pot schimba în timpul algoritmului. Să presupunem că un proces își ține evidența copiilor într-un anumit set, are un set de copii. Dacă primește un mesaj non-părinte de la un copil, chiar dacă acel copil ar putea fi de la un vecin. Acel vecin ar putea fi în setul său de copii, iar aceasta ar putea fi o corecție, iar apoi procesul trebuie să scoată acel vecin din setul de copii. Și să presupunem că procesul își îmbunătățește propria distanță. Ei bine, acum, este un fel de început de la capăt. Va trimite din nou acea distanță tuturor vecinilor săi și va colecta noi informații despre dacă sunt copii sau nu. Lucrul simplu de făcut aici este pur și simplu gol: zero-ți setarea copiilor și o ia de la capăt. Acum trimiteți noile voastre mesaje vecinilor și așteptați să răspundă din nou. Există o contabilitate dificilă de făcut pentru a gestiona corecțiile pe măsură ce structura acestui arbore se schimbă, așa că obținerea de indicatori copii este puțin mai complicată decât înainte. Are sens? Bine, așa că acum revenim la întrebarea ta, rezilierea. Cum știu toate procesele când arborele este complet? De fapt, avem o problemă mai gravă. Cu această problemă am lovit prima căutare pe lățime, dar avem o problemă și mai gravă. Acum ce este asta? Da? PUBLIC: [INAUDIBIL]. PROFESORUL: Da, înainte să avem fiecare nod individual. Odată ce și-a dat seama cine este părintele său, ar putea pur și simplu să scoată asta. Și acum, poți să-ți dai seama de părintele tău, dar este doar o presupunere și nu știi când poți scoate asta. Cum poate un proces chiar -- un proces individual să- și dea seama de propriul părinte și de distanța? Există două aspecte aici în încheiere. Una este cum știi că s-a terminat totul, dar cealaltă este chiar cum știi când ai terminat cu propriul părinte și cu distanța? Ei bine, dacă știi ceva despre grafic, cum ar fi o limită superioară a numărului total de noduri, atunci ai putea doar să aștepți până la acel număr de runde și gata. Dar dacă nu aveți acele informații despre grafic? Ce ai putea face? Da? PUBLIC: Vrei să faci BFS în paralel și să filtrezi informațiile când ai atins dimensiunea graficului. PROFESORUL: Poate. Cred... care este strategia pe care o folosim pentru rezilierea BFS? Să începem cu acela. E puțin mai ușor. Ai făcut chestia subarboresc pe care noi o numim convergecast informațiile. Când aveam o frunză, el știa că este o frunză și putea trimite informațiile gata părintelui său, iar acestea au convergeat până în vârful copacului. Putem converge în acest cadru? Se pare că putem, dar din moment ce lucrurile se schimbă, vei trimite mesaje gata și apoi ceva s-ar putea schimba. Este posibil să participați la convergecast de mai multe ori. Deoarece structura arborelui se schimbă, ideea principală este că oricine poate trimite un mesaj gata către nodul actual -- nodul pe care îl crede că este părintele său, cu condiția să primească răspunsuri la toate mesajele sale la distanță, astfel încât să creadă că știe cine sunt toți copiii săi. . Are o estimare actuală a tuturor copiilor și... deci dacă îi cunoaște pe toți copiii și toți i-au trimis mesaje gata. Pentru toți copiii tăi actuali , credința ta actuală sau cine sunt copiii tăi , dacă toți ți-au trimis mesaje gata, atunci poți trimite un mesaj gata în sus. Dar acest lucru poate deveni puțin mai complicat decât pare, pentru că poți schimba cine sunt copiii tăi. Acest lucru înseamnă că același proces poate fi implicat de mai multe ori în convergecast, pe baza îmbunătățirii estimărilor. Iată un exemplu despre genul de lucru care se poate întâmpla. Să presupunem că începi, ai aceste greutăți uriașe și apoi ai un drum lung cu greutăți mici. i 0 pornește și trimite informații despre distanță pe cele trei noduri ale sale, către cei trei vecini. Și tipul ăsta din partea de jos are acum o distanță estimată de 100 și va decide că este o frunză. De ce? Pentru că atunci când trimite mesaje copiilor săi, vecinilor săi, aceștia nu sunt capabili să-și îmbunătățească estimările pe baza noilor informații pe care le trimite. Acest tip decide că este o frunză imediat și trimite acele informații înapoi la nodul i 0. Pe de altă parte, acest tip are aceeași estimare de 100. Și își trimite mesajele pentru a încerca să afle dacă este o frunză. , dar află când trimite un mesaj în acest fel că de fapt este capabil să îmbunătățească estimarea acelui vecin , pentru că până atunci era infinit. Nu crede că este o frunză. Avem un singur tip care crede că este o frunză și răspunde, așa că acesta stă acolo. Trebuie să aștepte să audă de la ceilalți copii ai săi. OK pana acum? În regulă, între timp, mesajele se vor strecura în cele din urmă și acest nod va primi o estimare mai mică bazată pe lungimea acelei căi lungi cu multe hop. Apoi va decide că nu este un copil al lui i 0. Va spune i 0 că nu sunt chiar copilul tău, ceea ce înseamnă că i 0 încetează să-l mai aștept. Dar, de asemenea, acest tip decide că nu este un copil. El devine un copil al nodului chiar deasupra lui. Așa că acum îmi voi da seama că are un singur copil, dar tipul ăsta crede că este din nou o frunză după ce a încercat din nou să găsească copii. Și acum informațiile realizate se propagă până în sus în copac, care acum este doar această cale lungă. Au început să încerce să converge, dar apoi, hopa, s-au înșelat. Ei trebuie să facă o corecție și formează un nou copac. În cele din urmă, arborele se va stabiliza și, în cele din urmă, informațiile realizate vor ajunge până la vârf, dar ar putea exista o mulțime de porniri false între timp. Este un fel de confuz, dar asta e genul de lucruri care se întâmplă. Da? PUBLIC: Poate exista un proces în care [INAUDIBIL] și apoi își schimbă mintea chiar la sfârșitul acestuia. Cum te asiguri că, acea propagare [INAUDIBILĂ]? PROFESORUL: Da, deci nodul rădăcină nu se va termina până când nu aude de la toată lumea. Trebuie oarecum să închei întregul proces. E mereu în așteptare, în așteptarea pe cineva, dacă nu a auzit de cineva. Dacă lucrurile se schimbă, se vor alătura unei alte părți a copacului. Cred că cel mai bun lucru de făcut aici este să construiești niște mici exemple manual. Vreau să spun că nu vom vorbi despre cum faci dovezi formale ale unor astfel de lucruri. Nici măcar nu avem în acest moment un simulator pe care să-l poți folosi pentru a te juca cu acești algoritmi. Deși, dacă este cineva interesat, unii studenți din clasa mea în ultimul trimestru, de fapt, au scris un simulator care ar putea fi disponibil. Bine, în regulă, deci asta e ceea ce obții pentru un sincron -- niște exemple de algoritmi distribuiți sincron . Acum să ne uităm la ceva mai complicat când intri în algoritmi asincroni. BINE. Până acum, complicațiile pe care le-ați văzut în restul acestui curs, aveți acum procese care acționează concomitent. Și am avut un pic de non-determinism, nimic important, dar acum lucrurile sunt pe cale să se înrăutățească mult. Nu mai avem runde. Acum vom avea procese care fac pași, mesajele vor fi livrate la momente absolut arbitrare, comenzi arbitrare. Procesele pot deveni complet desincronizate și, prin urmare, aveți mult și mult mai mult non-determinism în algoritm. Non-determinismul are de-a face cu cine face ce în ce ordine. Înțelegerea acestui tip de algoritm este cu adevărat diferită de înțelegerea algoritmilor pe care i-ați văzut pe toți algoritmii distribuiti pe termen lung și chiar sincron , pentru că nu există o singură modalitate de a se executa algoritmul. Execuția poate decurge în multe moduri diferite, doar în funcție de ordinea pașilor. Nu poți spera niciodată să înțelegi exact cum se execută acest tip de algoritm. Ce poti face? Ei bine, te poți juca cu el, dar în cele din urmă, trebuie să înțelegi câteva proprietăți abstracte. Unele proprietăți ale execuțiilor, mai degrabă decât exact ceea ce se întâmplă la fiecare pas, și asta este un salt. Este un nou mod de a gândi. Ne putem uita la chestii asincrone, dacă doriți, din cartea mea. Acum avem încă procese la nodurile unui graf. Și acum avem canale de comunicare asociate cu marginile. Acum, procesele vor fi un fel de automate, dar canalele vor fi, de asemenea, un fel de automate. Vom avea toate aceste componente și le vom modela pe toate. Procesele au încă porturile lor. În general, nu trebuie să aibă identificatori. Ce este un canal? Un canal este... este un fel de automat, automat cu stare infinită , care are intrări și unele ieșiri. Aici, aceasta este doar o imagine a unui canal de la nodul u la nodul v. Canalul uv este doar acest lucru în cloud care transmite mesaje. Are intrări. Intrările sunt: ​​mesajele sunt trimise pe canal. Puteți avea un proces la un capăt care trimite un mesaj m și ieșirile de la celălalt capăt sunt livrările, să spunem primirea mesajului m, la celălalt capăt, nodul v. Pentru a modela acest lucru, cel mai bun lucru este de fapt să... de a descrie doar ceea ce face, pentru a oferi un model explicit al stării sale și a ceea ce se întâmplă atunci când apar intrările și ieșirile. Dacă doriți ca aceste mesaje să fie livrate, să spunem în ordine FIFO, bine. Puteți face ca starea canalului să fie un q real. mq ar fi doar o coadă de mesaje FIFO. Începe gol, iar când mesajele sunt trimise, sunt adăugate până la sfârșit și sunt livrate, sunt eliminate de la început. Tot ce trebuie să descriem... acesta este un fel de pseudo-cod. Tot ce trebuie să descriem - să scriem pentru a descrie ce face acest canal, este ce se întâmplă atunci când are loc o trimitere și când poate acest canal să livreze un mesaj și ce se întâmplă când face asta. O trimitere, care poate veni în orice moment, iar efectul este doar de a adăuga acest mesaj la sfârșitul cozii. Cel care primește... nu te mai mișcă. Primirea... asta nu poate fi o construcție. Am auzit zgomot. Sunt gremlins. Avem-- o recepție poate apărea numai atunci când acest mesaj este în capul cozii și, atunci când apare, este eliminat din coadă. Are acest sens ca descriere a ceea ce face un canal? Mesajele vin, sunt adăugate la ele, apoi mesajele pot fi livrate în anumite situații și sunt eliminate. Aceasta este o descriere a canalului. să folosească un sistem asincron. Un proces - restul sistemului constă din procese asociate cu vârfurile graficului. Să presupunem că pu este un proces care este asociat cu vârful u. Dar scriu asta doar ca o prescurtare, pentru că u este vârful din grafic, iar procesul nu știe de fapt numele vârfului. Are doar propriul său ID unic sau ceva de genul ăsta, dar acum voi fi puțin neglijent cu asta. Procesul pe care la vertex u puteți efectua trimite ieșiri pentru a pune mesaje pe canal și va primi intrări pentru mesajele care vor veni pe canal. Dar procesele ar putea avea, de asemenea, o interfață externă în care cineva trimite unele intrări procesului, iar procesul trebuie să producă o ieșire la sfârșit. Pot exista și alte intrări și ieșiri. Și îl vom modela cu variabile de stare. Procesul ar trebui să continue să facă pași. Canalul ar trebui să continue să livreze mesaje. Este o proprietate numită liveness. Vrei să te asiguri că toate componentele din sistemul tău continuă să facă lucruri. Ei nu fac doar niște pași și apoi se opresc. Iată un exemplu simplu. Un proces care amintește numărul maxim pe care l-a văzut vreodată. Există un automat de proces maxim. Primește niște mesaje m, ceva valoare și le va trimite. Ține evidența max-- aceasta este variabila de stare max. începe cu propriile valori inițiale, deci x pentru u. x din u este valoarea sa inițială. Și apoi are-- pentru fiecare vecin, are o mică coadă-- aici, este doar un boolean-- întreabă dacă ar trebui să-i trimită vecinului respectiv. Acesta este pseudocodul pentru acel proces maxim. Ce face atunci când primește un mesaj? Ei bine, vede dacă acea valoare este mai mare decât a avut înainte și, dacă da, resetează valoarea maximă. Și menționează, de asemenea, că ar trebui să trimită asta tuturor vecinilor săi. Ori de câte ori primește informații noi, va dori să le propagă vecinilor săi. Vezi cum este scris asta? Spuneți doar, resetați valoarea maximă și apoi pregătește-te să trimiți tuturor vecinilor tăi, iar ultima parte este doar un fel de cod trivial. Spune, dacă sunteți gata să trimiteți, atunci puteți trimite și apoi ați terminat și puteți seta semnalizatoarele de trimitere la false. Da? PUBLIC: Ce studiu? PROFESORUL: Pentru fiecare vecin. Oh, am mai scris vecinului v , apoi am... da. Am scris vecinului... oh, știu de ce am scris w. Aici, vorbesc despre dacă primești un mesaj de la un anumit vecin v, atunci trebuie să-l trimiți tuturor vecinilor tăi. Înainte, foloseam v pentru a desemna un vecin generic, dar acum nu mai pot face asta, pentru că v este expeditorul mesajului. Doar tehnic... OK? Avem aceste automate de proces. Avem acest canal automat. Acum, vrem să construim sistemul. Le lipim împreună. Cum le lipim este doar că avem ieșiri din procese care se pot potrivi cu intrările către canale și invers. Dacă un proces are o ieșire de trimitere, să spunem trimite de la u la v, care se va potrivi cu canalul care a trimis uv ca intrare. Și recepția de la canal se potrivește cu procesul care are acea recepție ca intrare. Tot ce fac este să potrivesc aceste componente. Conectez aceste componente prin potrivirea numelor lor de acțiuni. Are sens? Spun cum construiesc un sistem din toate aceste componente și am doar un mod sintactic de a spune ce acțiuni se potrivesc în diferite componente. Întrebări? Toate acestea sunt noi. Când acest sistem face un pas, ei bine, dacă cineva efectuează o acțiune și altcineva are aceeași acțiune - să presupunem că un proces face o trimitere. Canalul are o trimitere. Amândoi își iau tranzițiile în același timp. Procesul trimite un mesaj, acesta este introdus în canal la sfârșitul cozii. Are sens? BINE. Cum se execută chestia asta? Ei bine, nu există runde sincrone, așa că sistemul funcționează doar prin procese, iar canalele își fac pașii în orice ordine. Pe rând, dar poate fi în orice ordine, deci este un model de secvență. Aveți doar o secvență de pași individuali. Nu există concurență aici. În modelul sincron, am avut pe toți să-și facă pașii într-un singur bloc mare. Și aici, doar că fac pași pe rând, dar ar putea fi în orice ordine. Și trebuie să ne asigurăm că toată lumea continuă să facă pași. Că fiecare canal continuă să transmită mesaje și fiecare proces efectuează întotdeauna un pas care este activat. Pentru procesele maxime, ei bine, putem avea doar o grămadă de procese, fiecare începând acum cu valoarea sa inițială. Și ce se întâmplă când le conectăm împreună cu toate canalele dintre ele? Corespunzător oricărui grafic se află. Au doar canale pe margini. Care este comportamentul asta? Dacă toate procesele sunt ca cele pe care tocmai ți le-am arătat, ei așteaptă până aud un nou max și apoi îl trimit. Da? PUBLIC: Toate procesele au în cele din urmă o valoare maximă globală. PROFESORUL: Da, toți vor obține până la urmă maximul global. Vor continua să se propage până când toată lumea o va primi. Iată o animație dacă toată lumea începe cu valorile care sunt scrise în aceste cercuri. Acum, amintiți-vă, înainte să-l trimită toți o dată, acum nu mai mult. Să spunem că primul lucru care se întâmplă este procesul care a început cu cinci și-și trimite mesajul pe unul dintre canalele sale, așa că cinci se stinge. Următorul lucru care s-ar putea întâmpla este celălalt proces cu cei șapte care ar putea trimite cei șapte pe unul dintre canalele sale. Și aceștia sunt încă trei pași. Cineva trimite un 10. Cineva trimite un șapte. Cineva a primit un mesaj și și-a actualizat valoarea ca urmare, iar noi continuăm. Înfățișez mai mulți pași deodată, pentru că e plictisitor să- i faci pe rând, dar modelul chiar spune că fac pași într-o anumită ordine. Toată lumea propagă cel mai mare lucru văzut și, în cele din urmă, ajungi cu toată lumea să aibă valoarea maximă, 10. Bine, așa funcționează un sistem asincron. Putem analiza complexitatea mesajului. Numărul total de mesaje trimise pe parcursul întregii execuții, în cel mai rău caz, pe fiecare margine. Puteți trimite estimarea îmbunătățită succesiv, astfel încât aceasta este, din nou, cât sunt de n ori numărul de muchii. Complexitatea timpului este o problemă. Când aveam algoritmi sincroni, am numărat doar numărul de runde și asta a fost ușor. Dar ce măsurăm acum? Cum numărăm timpul în care toate aceste procese și canale iau pași oricând doresc? Da, deci asta chiar nu este evident. Există o soluție care este folosită în mod obișnuit, care este... OK, vom folosi timpul real. Și vom face câteva presupuneri cu privire la anumiți pași de bază, luând, cel mult, o anumită perioadă de timp. Să presupunem că timpul de calcul local pentru ca un proces să efectueze următorul pas, este mic. Dați doar o limită de oră locală. Și apoi aveți d pentru ca un canal să livreze un mesaj. Primul mesaj care se află în prezent pe canal. Dacă aveți astfel de presupuneri, le puteți folosi pentru a deduce o limită superioară în timp real pentru rezolvarea întregii probleme. Adică, dacă știi că nu durează mai mult de d pentru a livra un mesaj, atunci poți limita cât de mult durează pentru a livra -- pentru a goli o coadă, un canal și cât durează mesajele să se propagă prin rețea. Este dificil, dar acesta este cam singurul lucru pe care îl poți face într-un cadru în care de fapt nu ai runde de măsurat. Atunci pentru sistemul max, cât durează? Ei bine, să ignorăm timpul local de procesare. De obicei, se presupune că este foarte mic, deci să presupunem că este 0. Putem obține o limită superioară foarte simplă, pesimistă, care spune că timpul real pentru finalizarea întregului lucru este de ordinul diametrului rețelei înmulțit cu numărul de noduri ori mic d este timpul necesar unei coade de mesaje pentru a livra primul mesaj. Ca mod naiv de a analiza acest lucru, trebuie doar să luați în considerare cât timp durează maximul pentru a ajunge la un anumit vârf u de-a lungul drumului cel mai scurt. Ei bine, trebuie să treacă prin toate hopurile de pe potecă, așa că acesta ar fi diametrul. Și cât timp trebuie să aștepte în fiecare canal înainte de a ajunge să miște un alt hop? Ei bine, s-ar putea să fie la sfârșitul unei cozi. Cât de mare poate fi coada? Ei bine, în cel mai rău sfârșit pentru estimările îmbunătățite. Să presupunem că este de n ori timpul de livrare pe canal, doar pentru a traversa un canal. Ceea ce fac este să modelez o posibilă congestie în coadă pentru a vedea cât timp durează un mesaj pentru a traversa un canal. Da? PUBLIC: Presupunem doar că procesele procesează lucrurile, iar mesajele sunt livrate de îndată ce le pot avea? PROFESORUL: Bine. Da, în mod normal avem... Am sărit peste unele lucruri din model, dar aveți o presupunere de viață care spune că procesul continuă să ia pași atâta timp cât are ceva de făcut și așa am pune limite de timp pentru cât timp durează între acești pași. Acesta va fi timpul local de procesare, aici. Spun că este 0. PUBLIC: Tu faci asta... nu ai fi capabil să obții o cantitate de informații despre ce s-au întâmplat lucrurile? PROFESORUL: Ah, bine. Iată... acesta este un punct foarte subtil. Ce crezi că, dacă fac toate aceste ipoteze de timp, procesele ar trebui să poată înțelege asta. Dar, de fapt, nu vă puteți da seama de nimic doar pe baza acestor presupuneri despre aceste limite superioare. Punerea unor limite superioare pentru timpul dintre pași nu limitează în niciun fel ordinele. Mai aveți aceleași ordine posibile de pași. Nimeni nu poate vedea nimic diferit. Aceste vremuri nu sunt vizibile în niciun sens. Nu sunt marcate nicăieri pentru ca procesele să poată fi citite. Sunt doar ceva pe care îl folosim pentru a evalua costul, costul timpului, al execuției. Și nu restricționați execuția punând doar limite superioare ale timpului. Dacă restricționați execuția, așa cum ați avut limite superioare și limite inferioare la timp, atunci procesele ar putea ști mult mai multe. Ar putea, de fapt, să acționeze mai mult ca un sistem sincron. Acestea sunt vremuri care sunt folosite doar pentru analiza complexității. Nu sunt nimic cunoscut proceselor din sistem. BINE? În regulă. Acum să revedem problema arborelui care se întinde pe lățimea întâi . Dorim să calculăm acum un arbore care se întinde pe lățimea întâi într-o rețea asincronă. Graficul conectat, distinge vârful rădăcină, procesele nu au cunoștințe despre grafic. Au UID-urile tale. Toate acestea sunt la fel ca înainte în cazul sincron. Toată lumea ar trebui să scoată informațiile sale părinte când s-a terminat. Iată o idee. Să presupunem că luăm acel algoritm sincron simplu și frumos, pe care l-am revizuit la începutul orei, în care toată lumea trimite un mesaj de căutare imediat ce îl primește și adoptă primul părinte pe care îl văd. Ce se întâmplă dacă îl rulez asincron? Îl trimit și primesc un mesaj de căutare. Apoi le trimit părinților mei oricând și toată lumea face asta. Ori de câte ori primesc primul lor mesaj de căutare, ei decid că expeditorul este părintele său. Da? PUBLIC: Ați putea avea un nivel frontal care să nu se extindă în continuare -- să nu se supună proprietății definitorii a BFS? PROFESOR: Da, s-ar putea ca, pentru că nu avem nicio restricție cu privire la cât de repede pot fi trimise mesajele și ordinea pașilor, s- ar putea ca unele mesaje să fie trimise foarte repede pe o cale lungă. Cineva care se află la capătul îndepărtat al rețelei poate primi un mesaj mai întâi pe o cale lungă și mai târziu pe o cale scurtă, iar primul care îl primește decide că acesta este părintele său, apoi rămâne blocat. Acesta nu este un algoritm care face corecții. BINE? În regulă, ei bine, înainte aveam un pic de non-determinism când aveam acest algoritm în cazul sincron, pentru că puteam primi două mesaje deodată, iar tu trebuie să alegi unul pentru a fi părintele tău. Acum asta nu se întâmplă, pentru că primești doar un mesaj la un moment dat, dar acum ai mult mai mult non-determinism. Acum aveți tot acest non-determinism din ordinea în care mesajele sunt trimise și procesele își fac pașii. Există o mulțime de non-determinism și nu uitați, modul în care tratăm non-determinismul pentru algoritmii distribuiți este că ar trebui să funcționeze indiferent de modul în care sunt făcute acele alegeri nedeterministe . Cum am descrie noi? Voi scrie aici niște pseudo-cod pentru un proces care doar imită algoritmul banal. Poate primi un mesaj de căutare, acestea sunt intrările, și poate trimite un mesaj de căutare ca ieșire. De asemenea, poate afișa părinte atunci când este gata să facă asta. Ce trebuie să țină evidența? Ei bine, ține evidența părintelui său, ține evidența dacă a raportat părintele său și are niște buffere de trimitere cu mesaje pe care este gata să le trimită vecinilor săi, ar putea fi mesaje de căutare sau nimic. Acest simbol de jos este doar un simbol substituent. Ce se întâmplă când procesul primește un mesaj de căutare, doar urmând algoritmul simplu? Ei bine, dacă nu are încă un părinte, atunci își setează părintele să fie expeditorul acelui mesaj de căutare și se pregătește să trimită mesajul de căutare tuturor vecinilor săi. Acesta este cu adevărat inima algoritmului pe care l-ați văzut pentru algoritmul simplu, deoarece este cazul sincron, deci este același cod. Restul codului este că trimite mesajele de căutare atunci când le primește în bufferele de trimitere și își poate anunța părintele odată ce părintele este setat, iar apoi nu-- acest indicator înseamnă doar că nu continuă să-l anunțe iar și iar. Este logic că acest lucru descrie acel algoritm simplu. Este destul de concis, exact ce face în toți acești pași diferiți. BINE? Acum, dacă rulați acest lucru asincron, așa cum ați observat deja, nu va funcționa neapărat corect. Îl poți lăsa pe acest tip să trimită mesaje de căutare, dar unele vor ajunge mai repede decât altele. Și vezi că poți avea mesajele de căutare să se strecoare pe o cale indirectă, ceea ce face ca un arbore care se întinde ca acesta să fie creat, care cu siguranță nu este un arbore care se întinde pe lățime. Arborele de lățimea întâi este acesta - un copac de lățimea întâi. Aveți aceste poteci giratorii. Acest lucru nu funcționează. Ce facem? Da? PUBLIC: Ai putea avea un copil [INAUDIBIL]. PROFESOR: O să încercați să le sincronizați, practic. PUBLIC: [INAUDIBIL]. PROFESORUL: Asta este legat de o întrebare pentru acasă săptămâna aceasta. Foarte bun. Vom face ceva diferit. Alte sugestii? Da? Publicul: Am putea păstra o variabilă în fiecare proces care... poți face ceva ca Bellman-Ford. PROFESOR: Da, așa că puteți face ceea ce am făcut noi pentru Bellman-Ford, dar acum decorul este complet diferit. Am făcut-o pentru Bellman-Ford când era sincron și aveam greutăți. Acum, este asincron și nu există greutăți. BINE? Oh, sunt câteva remarci despre câteva diapozitive aici. Acest lucru este doar să discute ideea, că căile pe care le obțineți de acest algoritm pot fi mai lungi decât cele mai scurte căi și-- da, puteți analiza mesajul și complexitatea timpului. Complexitatea aici este ordinea diametrului înmulțit cu întârzierea mesajului pe o legătură. Și de ce este diametrul, chiar dacă unele căi pot fi foarte lungi? Aceasta este o limită superioară în timp real care depinde de diametrul real al graficului, nu de numărul total de noduri. De ce o limită superioară a timpului de rulare pentru algoritmul simplu ar depinde de diametru? Da? PUBLIC: Pentru că ai o cale mai lungă doar dacă este mai rapidă decât... PROFESORUL: Exact. Felul în care îl modelăm-- este puțin ciudat, poate-- dar spunem că ceva poate călători pe o cale lungă doar dacă merge foarte repede. Dar cele mai scurte căi reale se deplasează în continuare, în cel mai rău caz, la d timp per hop. În cel mai rău caz, informațiile despre calea cea mai scurtă ar ajunge acolo în timp d. Ceva va ajunge acolo în timpul d, chiar dacă altceva ar putea ajunge acolo mai repede. BINE? În regulă. Da, putem configura un pointer copil și putem face terminarea folosind convergecast. Este doar un copac. Nu se schimbă nimic aici. Și aplicații, la fel ca înainte. Dar asta nu a funcționat, așa că vom reveni la punctul despre care vorbeam acum un minut, vom folosi un algoritm de relaxare precum Bellman-Ford. În cazul sincron, am corectat pentru căi care au avut multe salturi, dar greutate mică, dar acum vom corecta erorile de asincronie. Toate erorile pe care le primești din cauza lucrurilor care călătoresc rapid pe căi lungi, le vom corecta pentru cei care folosesc aceeași strategie. Toată lumea va ține evidența distanței de hop. Fără greutăți acum, doar distanța hop și vor schimba părintele atunci când vor afla despre o cale mai scurtă. Și apoi vor propaga distanța îmbunătățită, așa că este exact ca Bellman-Ford. Și în cele din urmă, acest lucru se va stabiliza la un arbore care se întinde pe lățimea întâi. Iată o descriere a acestui nou algoritm. Toată lumea își ține evidența părinților, iar acum își ține evidența distanței de hop și au canalele lor. Iată cheia, când primiți informații noi - primiți niște informații noi, acest m este un număr de hop pe care vi le spune vecinul. Ei bine, dacă m plus 1, care ar fi noua dvs. estimare pentru un număr de hop-- dacă aceasta este mai bună decât ceea ce aveți deja, atunci trebuie doar să înlocuiți estimarea cu acest nou număr de hopuri. Și ți-ai stabilit... unui nou părinte. Setați indicatorul părinte la expeditor și propagați aceste informații. Este exact la fel cu ceea ce aveam înainte, dar acum corectăm pentru asincronie. Avem trasee mai scurte mai târziu. Are sens? Și restul este doar tu trimiteți mesajul. Și observați că nu avem acțiuni de terminare. De ce? Pentru că avem aceeași problemă pe care am avut-o înainte, când procesele știe când s-au terminat. Dacă tot primești corecții, de unde știi când ai terminat? Și de unde știi că asta va funcționa? În cazul sincron, am putea obține o caracterizare exactă a situației exacte după orice număr de runde. Și nu putem face asta acum, pentru că lucrurile se pot întâmpla în atâtea ordine. În schimb, trebuie să menționăm unele proprietăți abstracte de nivel superior, fie în variație, fie veți vedea și alte tipuri de proprietăți. Am putea spune, de exemplu, ca invariant, că toate informațiile despre distanță pe care le obțineți sunt corecte. Dacă ai setat vreodată distanța la ceva, aceasta este distanța reală pe o cale și părintele tău este setat corect să fie predecesorul tău pe o astfel de cale. Asta înseamnă doar că orice vei obține este o informație corectă. Totuși, asta nu înseamnă că în cele din urmă vei termina. Spune doar că ceea ce primești este corect. Dacă vrei să arăți că, în cele din urmă, obții răspunsul corect, trebuie să faci ceva cu sincronizarea. Trebuie să spui ceva de genul cu un anumit timp care depinde de distanță. Dacă există... și cel mult calea noastră de salt către un nod, atunci va afla despre asta într-un anumit timp, dar asta depinde de lungimea căii și de timpul de livrare a mesajului. Și numărul de noduri, pentru că pot fi aglomerate. Trebuie să nu spuneți doar că lucrurile sunt corecte, dar trebuie să spuneți că, în cele din urmă, obțineți rezultatul corect și aici se va spune că, într- un anumit timp, obțineți rezultatul potrivit. Are sens? Așa ați înțelege un algoritm ca acesta. Complexitatea mesajului. Deoarece există toate aceste corecții, te-ai întors în număr de margini ori, probabil, numărul de noduri. Iar complexitatea timpului, până când toate distanțele și valorile părinte se stabilizează, ar putea fi - asta este din nou pesimist -- diametrul multiplicat cu numărul de noduri ori d, deoarece poate exista congestionare în fiecare dintre legături din cauza corecțiilor. De unde știi când se face asta? Cum poate un proces să știe când se poate termina? Idee? Înainte să spunem, ei bine, dacă ai ști n, dacă ai ști numărul de noduri, ai putea pondera acel număr de runde. Asta nici măcar nu te ajută aici. Chiar dacă știi... ai o limită superioară bună a numărului de noduri din rețea, nu există runde de numărat. Nu poți spune. Chiar și știind numărul de noduri pe care nu le puteți spune, deci cum ați putea detecta terminarea? Da? PUBLIC: S-ar putea lega de diametrul [INAUDIBIL]. PROFESORUL: Da, bine, dar chiar dacă știi asta, nu poți număra timpul. Vezi că acesta este treaba cu algoritmii asincroni, tu nu ai... deși folosim timpul pentru a măsura cât timp durează terminarea, noi... procesele de acolo nu au asta. Sunt doar acești tipi asincroni care fac doar pașii lor. Ei nu știu nimic de-a face cu timpul. Alte idei? Da. PUBLIC: Nu ați putea folosi același tip de convergență... PROFESOR: Același lucru. Vom folosi din nou convergecast, aceeași idee. Tu doar calculezi și reputația ta indicatorii copilului tău. Trimiți un gata părintelui dvs. actual , după ce ați primit răspunsuri la toate mesajele dvs., astfel încât să credeți că vă cunoașteți copiii. Și toți ți-au spus că au terminat și... dar atunci s-ar putea să fii nevoit să faci corecții, așa că, ca în ceea ce am văzut înainte, poți fi implicat în această convergecast de mai multe ori până când ajunge în sfârșit până la rădăcină. . Odată ce le aveți, le puteți folosi în același mod ca înainte. Acum aveți costuri care sunt mai bune decât acest arbore simplu care nu a avut căi cele mai scurte , deoarece acum vă ia mai puțin timp să utilizați arborele pentru funcții de calcul sau pentru diseminarea informațiilor, deoarece arborele este mai puțin adânc. În cele din urmă, ce se întâmplă atunci când vrem să găsim arbori cu cele mai scurte căi într-un cadru asincron? Acum, vom adăuga la complicațiile pe care tocmai le-am văzut cu toată asincronia. Complicațiile de a avea greutăți pe margini. În regulă, problema este să obțineți un arbore care se întinde pe calea cea mai scurtă, acum într-o rețea asincronă, grafic ponderat, procesele nu știu din nou despre grafic. Au UID-uri și toată lumea ar trebui să-și scoată distanța și părintele în arbore. Vom folosi un alt algoritm de relaxare. Acum gândește-te la ce va face relaxarea pentru tine. Avem de făcut două tipuri de corecții. Ai putea avea drumuri lungi care au greutate mică. Acest lucru a apărut pentru Bellman-Ford în setarea sincronă, așa că trebuie să le corectăm. Dar ați putea avea, de asemenea, din cauza asincroniei, ați putea avea informații care călătoresc rapid pe multe hop și trebuie să corectați și pentru asta. Există două tipuri de lucruri pentru care veți fi corectate într-un singur algoritm. Acest lucru va -- și este destul de surprinzător -- va duce la o complexitate ridicol de mare, mesaj și complexitate de timp. Dacă aveți într-adevăr o asincronie și ponderi nelimitate, acest lucru vă va oferi un algoritm foarte costisitor. Veți vedea că o oarecare exponențială se va strecura acolo. Iată algoritmul pentru algoritmul asincron Bellman-Ford . Toată lumea își ține evidența părintelui. Conjectura lor distanță și au, acum, mesaje pe care urmează să le trimită vecinilor. Să presupunem că aveți o coadă pentru că ar putea exista estimări succesive. Vom avea o coadă acolo. Pasul cheie, pasul de relaxare, este ceea ce se întâmplă atunci când primești o nouă estimare a celei mai bune distanțe. Aceasta este distanța ponderată, acum, de la un vecin. Ei bine, te uiți la acea distanță plus greutatea marginii dintre ele și vezi dacă aceasta este mai bună decât distanța ta actuală, la fel ca Bellman-Ford sincron. Și dacă este, atunci vă îmbunătățiți distanța, vă resetați părintele și trimiteți distanța vecinilor. Este exact ca cazul sincron, dar o vom rula asincron. Și din moment ce veți corecta de fiecare dată când vedeți o nouă estimare, aceasta va gestiona de fapt ambele tipuri de corecții, fie că vine din cauza unui traseu cu mai multe hop cu o greutate mai mică , fie că vine doar din cauza asincronie. Ori de câte ori obțineți o estimare mai bună, veți face corectarea. Este clar că asta este tot ce trebuie să faci în algoritm, doar ce este în acest cod? Acesta este primit, iar restul algoritmului este doar că îl trimiteți când sunteți gata să trimiteți. Și atunci avem aceeași problemă cu rezilierea, nu există acțiuni de terminare. Vom reveni la asta. Este foarte greu să veniți cu invarianți și proprietăți de sincronizare, acum, pentru această setare. Cu siguranță puteți avea un invariant ca cel pe care tocmai l-am avut pentru căutarea asincronă pe lățimea întâi . Puteți spune că în orice moment, indiferent de distanța pe care o aveți este o distanță reală care poate fi atinsă pe o anumită cale, iar părintele are dreptate. Dar ne-ar plăcea să avem și ceva care să spună că, în cele din urmă, vei obține distanța potrivită. Doriți să precizați o proprietate de sincronizare care spune, bine, dacă aveți o cale de cel mult r hop, până la un anumit timp, ați dori să știți că distanța dvs. este cel puțin la fel de bună ca ceea ce ați putea obține pe acea cale. Problema este ce vei avea aici pentru o perioadă de timp? Cât timp ar dura pentru a obține cea mai bună estimare posibilă pentru o cale de cel mult r hop? O presupunere? Am reușit să calculez ceva rezonabil pentru cazul căutării pe lățimea întâi, dar acum acest lucru va fi mult, mult mai rău. Nu este deloc evident. De fapt, va depinde de câte mesaje s-ar putea aduna într-un canal, și asta poate fi foarte mult, un număr exponențial - exponențial în numărul de noduri din rețea. O să vă produc o execuție care poate genera un număr mare de mesaje, care apoi va dura mult timp pentru a livra și a întârzia terminarea algoritmului. Mai întâi, să ne uităm la o limită superioară. Ce putem spune pentru o limită superioară? Ei bine, există multe căi diferite de la v 0 la orice alt nod anume. Poate că trebuie să parcurgem toate căile simple din grafic . Și câți sunt? Ei bine, ca limită superioară, ați putea spune ordinul n factorial pentru numărul de căi diferite pe care le puteți parcurge pentru a ajunge de la v 0 la un alt nod anume. Este exponențial în n. Desigur, este ordinul de la n la n. Aceasta spune că numărul de mesaje pe care le-ați putea trimite pe orice canal ar putea corespunde efectuării atât de multe corecții. Acest lucru vă poate ridica complexitatea mesajului în n până la de n ori numărul de margini și complexitatea dvs. de timp de n la n ori, de n ori d, pentru că pe fiecare margine ar putea fi nevoit să așteptați atâtea mesaje, mesaje corectate, stând. în fața dumneavoastră. Asta pare destul de groaznic. Se întâmplă cu adevărat? Puteți construi o execuție a acestui algoritm în care să obțineți limite exponențiale așa? Și vom vedea că, da, poți. Aveți întrebări până acum? Iată un exemplu prost. Aceasta este o rețea, constă dintr-o succesiune de, să spunem, k plus 1-- k plus 2, cred, noduri, într-o linie. Și voi introduce câteva noduri de ocolire între fiecare pereche consecutivă de noduri din acest grafic și acum lasă-mă să mă joc cu greutățile. Să spunem pe această cale, această cale directă de la v 0 la vk plus 1, toate greutățile sunt 0. Aceasta va fi cea mai scurtă cale, cea mai bună cale de greutate, de la v 0 la vk plus 1. Dar acum mă duc sa aiba niste ocoliri. Și pe ocoliri am două muchii, una de greutate 0 și cealaltă de greutate care este o putere de 2. O să încep cu puteri mari de 2, 2 la k minus 1 și cobor la 2 la k minus 2, până la 2 din 1, până la 0. Vedeți ce face acest grafic? Are o cale foarte rapidă în partea de jos, despre care ați dori să auziți cât mai curând posibil. Dar, de fapt, există ocoluri care ți-ar putea oferi drumuri mult mai proaste. Să vedem cum se poate executa acest lucru pentru a face o mulțime de mesaje să se adune într-un canal. Pretenția mea este că există o execuție a acelei rețele în care ultimul nod, bk, trimite 2 la k mesaje către următorul nod vk plus 1. El chiar va trimite un număr exponențial de mesaje corespunzător corecțiilor sale. Va continua să facă corecturi pentru estimări din ce în ce mai bune. Și dacă toate acestea se întâmplă relativ repede, asta înseamnă doar că aveți un canal cu un număr exponențial de mesaje în el, golirea care va dura un timp exponențial. Ai idee cum s-ar putea întâmpla asta? Cum a putut acest nod, bk, să obțină atât de multe estimări îmbunătățite succesiv , una după alta? Ei bine, care este cea mai mare estimare pe care o poate obține? Da? PUBLIC: 2 la k minus 1. PROFESORUL: Ar putea ajunge 2 la k minus 1? Ei bine, să vedem. PUBLIC: Sau [INAUDIBIL]. PROFESORUL: Ar putea face asta. PUBLIC: Atunci este 2 la k. PROFESORUL: Și ar putea face asta. PUBLIC: Plus 2 la k. PROFESOR: Plus 2 la k minus 2, plus până la plus 2 la 0. Ați putea urma această cale cu adevărat ineficientă, doar toate ocolirile, înainte ca mesajele să ajungă efectiv pe marginile coloanei vertebrale. PUBLIC: [INAUDIBIL]. PROFESORUL: Da, deci urmați toate... oh, ați spus 2 la k, minus 1, paranteză. Da, exact așa este. PUBLIC: E în regulă. [INAUDIBIL]. PROFESORUL: Nu ne putem pune în paranteză discursul. În regulă, deci estimările posibile pe care le poate lua bk sunt de fapt 2 la k-- așa cum ai spus, 2 la k minus 1, pe care le- ai obține dacă luăm toate ocolirile și adunăm puterile lui 2. Dar ar putea avea, de asemenea, o estimare, care este 2 la k minus 2 sau 2 la k minus 3. Toate acestea sunt posibile. Mai mult, puteți avea o singură execuție a acestui algoritm asincron în care nodul bk achiziționează de fapt toate acele estimări în succesiune, pe rând. Cum ar putea funcționa? În primul rând, mesajele parcurg toate ocolurile. Bine, bk primește 2 la k minus 1. Apoi, există un mesaj care călătorește - ei bine, tipul ăsta trimite un mesaj pe linkul de jos. Tipul ăsta a auzit doar de mesajele de pe ocoliri până în acel moment. Dar el trimite asta pe legătura inferioară, ceea ce înseamnă că ocoliți această greutate a unuia. bk primește un pic de îmbunătățire, ceea ce îi dă 2 la k minus 2 ca estimare. Ce se întâmplă în continuare? Ei bine, facem un pas înapoi, iar nodul de la nodul k minus 2 poate trimite un mesaj pe legătura inferioară, care are greutatea 0, către bk minus unu. Dar acea estimare corectată ar putea apoi traversa ocolul pentru a ajunge la nodul bk. Dacă obțineți corecția pentru nodul bk minus 1, dar apoi urmați ocolul, nu v-ați îmbunătățit atât de mult. Tocmai te-ai îmbunătățit cu una. În acest fel, obțineți 2 la k minus 3 ca noua estimare. Dar apoi, din nou, pe linkul de jos, în cele din urmă sosește mesajul, care îți oferă 2 la k minus 4. Vedeți un fel de model? Veți face numărătoarea inversă în binar, având succesiv noduri mai în stânga să-și livreze mesajele, dar apoi fac cel mai rău lucru posibil de a aduce informațiile către bk. El trebuie să se ocupe de toate celelalte estimări dintre ele. Dacă acest lucru se întâmplă rapid, ceea ce primești este o grămadă de un număr exponențial de mesaje de căutare într-un canal. Și apoi aceste informații trebuie să treacă la următorul nod sau la restul rețelei, indiferent. Va dura o perioadă exponențială de timp, în cel mai rău caz, pentru a goli totul. Acest lucru este destul de rău, dar algoritmul este corect. Și așadar, cum înveți când totul este terminat și cum știe un proces când poate scoate propriile informații corecte despre distanță? Cum ne putem da seama când totul este stabilizat? Același lucru ca înainte, putem face doar o convergecast. Vreau să spun că acestea sunt mai multe corecții, dar sunt tot același tip de corecții. Putem converge și, în cele din urmă, aceasta va converge până la rădăcină. Și atunci rădăcina știe că este gata și poate spune tuturor celorlalți. O morală aici-- ai avut o doză rapidă de multă asincronie-- da, dacă nu faci nimic în privința asta și folosești pur și simplu asincronia nerestricționată, în cel mai rău caz, vei avea ceva drăguț. performanță proastă. Întrebarea este, ce faci în privința asta? Există diverse tehnici. Și dacă vrei să-mi urmezi cursul în toamna viitoare, vom acoperi câteva dintre acestea. Voi spune puțin despre curs. Este un curs de bază -- este un nivel TQE, curs de bază. Facem lucruri sincrone, asincrone și alte lucruri în care nodurile știu cu adevărat ceva despre timp. Iată câteva dintre problemele sincrone -- unele precum cele pe care le- ați văzut deja. Construim multe alte tipuri de structuri în grafice și apoi intrăm în toleranța la erori. Există o mulțime de întrebări despre ce se întâmplă atunci când unele componente pot eșua sau sunt chiar rău intenționate și trebuie să faceți față efectelor proceselor rău intenționate din sistemul dumneavoastră. Și apoi, pentru algoritmii asincroni, nu vom face doar probleme individuale precum cele pe care tocmai le-ați văzut, ci și câteva tehnici generale, cum ar fi sincronizatorii, noțiunea de timp logic -- aceasta este prima și cea mai mare contribuție a lui Leslie Lamport. A primit premiul Turing anul trecut -- alte tehnici, cum ar fi realizarea de instantanee globale ale întregului sistem în timp ce acesta funcționează. Pe lângă faptul că vorbim despre rețele, așa cum am făcut săptămâna aceasta, vom vorbi despre memoria partajată, multi-procesoare care accesează memoria partajată. Și rezolvarea problemelor care sunt utile în multiprocesoare, cum ar fi excluderea reciprocă. Și din nou, toleranța la greșeală. Toleranța la erori ne duce apoi într-un studiu al obiectelor de date cu condiții de consistență, care este genul de lucruri care sunt utile în cloud computing. Dacă doriți să aveți acces coerent la datele care sunt stocate în multe locații, trebuie să aveți niște algoritmi distribuiți interesanți. Auto-stabilizare -- dacă vă scufundați sistemul într-o stare arbitrară și ați dori ca acesta să converge către o stare bună, acesta este subiectul auto- stabilizării. Și în funcție de timp, există lucruri care folosesc timpul în algoritmi, iar munca mai nouă la care lucrăm în cercetare este foarte dinamică. Ai distribuiți algoritmi în care rețeaua în sine se schimbă în timpul execuției. Acest lucru apare în rețelele fără fir și, în ultimul timp, ne uităm de fapt la algoritmi de colonii de insecte. Ce algoritmi distribuiți folosesc furnicile pentru a decide cum să selecteze un nou cuib atunci când cercetătorii își sparg vechiul cuib în laborator? Genul ăsta de întrebare. Asta e tot pentru săptămâna algoritmilor distribuiți. Și ne vedem... săptămâna viitoare este securitatea? OK, da.