Algoritmul LeLann

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson
Download our mobile app to listen on the go
Get App

Questions and Answers

Ce rol are nodul cu ID maxim în algoritmul LeLann?

  • Propagă informația către celelalte noduri
  • Devine liderul (correct)
  • Se pierde această identitate
  • Se sincronizează cu celelalte noduri

În care direcție sunt transmise mesajele în algoritmul Lelann-Chang-Roberts?

  • Aleatoriu
  • În sensul acelor de ceasornic (correct)
  • În linie dreaptă
  • În sens invers acelor de ceasornic

Care este informația acumulată de un nod pe parcursul execuției algoritmului?

  • Timpul de execuție
  • ID-urile nodurilor colectate (correct)
  • Starea nodurilor vecine
  • Condiția de rețea

Ce se întâmplă cu starea unui nod dacă acesta nu are ID maxim?

<p>Se declară pierdut (B)</p> Signup and view all the answers

Ce structură de date este utilizată pentru a stoca ID-urile colectate de noduri?

<p>Listă (D)</p> Signup and view all the answers

Care este principalul rol al procesului care primește un id în Algoritmul LeLann?

<p>Colectează identificatorii de la celelalte procese. (B)</p> Signup and view all the answers

Ce se întâmplă atunci când un proces află că numărul său este maximul?

<p>Își schimbă starea în 'leader'. (C)</p> Signup and view all the answers

În contextul Algoritmului LeLann, care dintre următoarele afirmații este corectă?

<p>Fiecare proces poate păstra o listă cu identificatorii primiți. (C), Canalele utilizate sunt de tip FIFO. (D)</p> Signup and view all the answers

Ce tip de stare are un proces la începutul Algoritmului LeLann?

<p>Candidat (D)</p> Signup and view all the answers

Ce trebuie să facă un proces dacă primește propriul id în Algoritmul LeLann?

<p>Să considere că a văzut toate celelalte id-uri. (C)</p> Signup and view all the answers

Care este numărul maxim de mesaje care pot fi inițiate de un proces care declanșează o cale de lungime $2^i$?

<p>4 mesaje (A)</p> Signup and view all the answers

Care este complexitatea totală a mesajelor într-un sistem cu n procese?

<p>$O(n imes log(n))$ (B)</p> Signup and view all the answers

Dacă $n$ este o putere a lui 2, care este timpul necesar pentru transmiterea mesajelor?

<p>$4n - 2$ (C)</p> Signup and view all the answers

Care este numărul maxim de procese care pot iniția căi de lungime 4 într-un grup de $n$ procese?

<p>$ ext{sup}[n/3]$ (A)</p> Signup and view all the answers

Ce tip de algoritmi sunt menționați în sumarele procesului de alegere a liderului?

<p>Algoritmi undă (B)</p> Signup and view all the answers

Câte pași sunt necesari pentru a lua prima și ultima decizie în cazul unei alegeri de lider în topologia inel?

<p>3D + 1 pași (B)</p> Signup and view all the answers

Ce se întâmplă cu nodurile după ce primesc un token?

<p>Nu mai pot să inițieze un mesaj (B)</p> Signup and view all the answers

Care este scopul desemnării liderului în topologia inel?

<p>Să se desemneze procesul cu id maxim (A)</p> Signup and view all the answers

Ce condiție trebuie să respecte aranjamentul circular de procese?

<p>Procesele trebuie să aibă numere distincte (C)</p> Signup and view all the answers

Care este o caracteristică a nodurilor în timpul alegerii liderului?

<p>Nodurile pot iniția mesaje doar înainte de a primi un token (C)</p> Signup and view all the answers

Care este natura controlului în topologia inel?

<p>Controlul este descentralizat (D)</p> Signup and view all the answers

Cum se numește procesul prin care nodurile își transmit identitatea în topologia inel?

<p>Token passing (D)</p> Signup and view all the answers

Ce se întâmplă dacă niciun nod nu are id maxim?

<p>Procesul de alegere nu va avea loc (B)</p> Signup and view all the answers

Care dintre următoarele afirmații este corectă?

<p>Nodurile nu pot iniția mesaje după primirea unui token. (C)</p> Signup and view all the answers

Care este rolul unui token în procesul de inițiere a mesajelor?

<p>Blochează inițierea mesajelor de către noduri. (D)</p> Signup and view all the answers

Ce se întâmplă cu nodul descris ca 'inițiator'?

<p>Devine nefuncțional după ce primește un token. (D)</p> Signup and view all the answers

Ce lucru este interzis pentru noduri după primirea unui token?

<p>Să inițieze un mesaj. (A)</p> Signup and view all the answers

Cum poate influența primirea unui token comportamentul nodurilor?

<p>Le limitează capacitatea de a trimite mesaje. (A)</p> Signup and view all the answers

Ce consecință are primirea unui token pentru un nod care inițiază mesaje?

<p>Nu poate mai mult să inițieze un mesaj. (D)</p> Signup and view all the answers

În ce condiții un nod devine inițiator?

<p>Când nu a primit încă un token. (B)</p> Signup and view all the answers

Ce reprezintă starea inițială în execuția algoritmului Hirschberg-Sinclair?

<p>candidate (B)</p> Signup and view all the answers

Ce se întâmplă când un proces primește un mesaj de tip 'no'?

<p>Starea devine 'lost'. (B)</p> Signup and view all the answers

Ce condiție trebuie să îndeplinească un proces pentru a trimite un mesaj 'pass'?

<p>Dacă numărul este mai mic decât maxnum. (A), Dacă valoarea procesului este mai mare decât valoarea sursei. (D)</p> Signup and view all the answers

Ce se întâmplă cu un proces care devine 'candidate' la primirea unui mesaj?

<p>Își compară valoarea cu cea a sursei mesajului. (B)</p> Signup and view all the answers

Care este finalitatea unui mesaj de tip 'ok' primit de un proces?

<p>Se finalizează alegerea. (D)</p> Signup and view all the answers

Care este rolul mesajului de tip 'echo' în algoritm?

<p>Confirmă pierderea procesului. (A)</p> Signup and view all the answers

Cum afectează complexitatea numărul de mesaje trimise de un proces?

<p>Trebuie să primească mesaj 'ok' pentru distanța 2i-1. (C)</p> Signup and view all the answers

Ce se întâmplă la primirea unui mesaj de tip 'no' într-un proces care așteaptă un răspuns?

<p>Procesul devine 'lost'. (D)</p> Signup and view all the answers

Flashcards

Algoritmul LeLann

Acest algoritm este utilizat pentru a găsi nodul cu cea mai mare valoare dintr-un inel de procese distribuite.

Transmisie circulară în algoritmul LeLann

Mesajele sunt transmise în jurul inelului, de la un nod la altul, într-o singură direcție.

Colectara și compararea ID-urilor în algoritmul LeLann

Fiecare nod colectează și compară ID-urile primite, actualizând starea sa în funcție de valoarea maximă identificată.

Starea "leader" în algoritmul LeLann

Nodul care deține cea mai mare valoare își stabilește starea ca "leader".

Signup and view all the flashcards

Algoritmul LeLann-Chang-Roberts

Algoritmul LeLann-Chang-Roberts îmbunătățește algoritmul original, reducând numărul de mesaje transmise.

Signup and view all the flashcards

Ce se întâmplă cu un nod care a primit un token?

Nodurile din rețea nu mai pot trimite mesaje după ce au primit un token.

Signup and view all the flashcards

Ce este un nod inițiator?

Un nod poate fi desemnat ca nod inițiator, care are dreptul să trimită primul mesaj în rețea.

Signup and view all the flashcards

Ce se întâmplă cu un nod care nu este inițiator?

Un nod care nu este nodul inițiator nu are voie să trimită un mesaj înainte de a primi un token.

Signup and view all the flashcards

Ce este un token?

Token-ul este un semnal care permite unui nod ne-inițiator să trimită un mesaj.

Signup and view all the flashcards

Ce e important de reținut despre noduri și inițiatorul ?

Toate nodurile din rețea (cu excepția inițiatorului) trebuie să aștepte un token înainte de a putea trimite un mesaj.

Signup and view all the flashcards

Ce se întâmplă cu numărul token-ului?

Numărul token-ului este unic și este asociat cu un nod specific.

Signup and view all the flashcards

De ce este important token-ul pentru un nod?

Un nod are dreptul de a trimite un mesaj doar după ce a primit un token.

Signup and view all the flashcards

Ce se întâmplă cu token-ul în rețea?

Token-ul se transmite de la un nod la altul, astfel asigurând o ordine în trimiterea mesajelor.

Signup and view all the flashcards

Mesaj cu ID-ul procesului

Un mesaj transmis de fiecare proces pentru a-și anunța ID-ul celorlalte procese din sistem.

Signup and view all the flashcards

Lista ID-urilor primite

O colecție de ID-uri primite de către un proces în timpul algoritmului LeLann, care include inițial propriul ID al procesului.

Signup and view all the flashcards

Liderul

Nodul care are cel mai mare ID din sistem după ce procesul de colectare a ID-urilor este finalizat.

Signup and view all the flashcards

Starea procesului

Starea procesului în algoritmul LeLann. Posibile valori: 'candidate' (înainte de a fi ales liderul), 'leader' (după ce a fost ales lider) sau 'lost' (după ce a pierdut alegerea liderului).

Signup and view all the flashcards

Algoritmul Hirschberg-Sinclair

Algoritmul care presupune că numai unul din procesele participante are identitate maximă și alege pentru această identitate

Signup and view all the flashcards

Starea "candidate"

Starea în care un proces se află în timp ce participă la alegerea identității maxime.

Signup and view all the flashcards

Variabila maxnum

Variabila care ține evidența numărului maxim de procese care au participat la o rundă de alegere.

Signup and view all the flashcards

Mesajul "no"

Un mesaj trimis de un proces care nu a fost ales ca identitate maximă.

Signup and view all the flashcards

Mesajul "ok"

Un mesaj trimis de un proces care a fost ales ca identitate maximă.

Signup and view all the flashcards

Trimiterea unui mesaj "no" mai departe

Când un proces primește un mesaj "no", el trimite mesajul mai departe către procesul următor în lanț.

Signup and view all the flashcards

Returnarea mesajului "ok" către inițiator

Când un proces primește un mesaj "ok", el trimite mesajul înapoi către procesul inițiator.

Signup and view all the flashcards

Participanți non-inițiatori

Un proces non-inițiator poate participa la alegerea identității maxime dacă identitatea sa este mai mare decât procesul care a trimis ultima dată un mesaj "no".

Signup and view all the flashcards

Alegerea liderului în topologia inel

În topologia inel, procesul cu id-ul maxim este desemnat ca lider prin consens, fără un control centralizat.

Signup and view all the flashcards

Rolul liderului în sistemele distribuite

Un proces este responsabil pentru coordonarea și administrarea altor procese într-un sistem distribuit.

Signup and view all the flashcards

Token în topologia inel

Un proces trimite un mesaj care conține propriul său id, care circulă de-a lungul inelului.

Signup and view all the flashcards

Acțiunea unui proces după primirea unui token

Un proces nu poate iniția un mesaj după ce a primit un token cu un id mai mare decât propriul id.

Signup and view all the flashcards

Circulația token-ului în topologia inel

Se trimite un token de la un proces la altul de-a lungul inelului.

Signup and view all the flashcards

Efectul primirea unui token

Primirea unui token de către un proces oprește procesul respectiv din a iniția mesaje.

Signup and view all the flashcards

Procesul inițiator în alegerea liderului

Procesul care trimite un token cu propriul său id este procesul inițiator.

Signup and view all the flashcards

Numărul de pași implicați în alegerea liderului

Numărul total de pași implicați în alegerea liderului este 3D+1, unde D este numărul de pași necesari pentru ca un token să circule o dată prin inel.

Signup and view all the flashcards

Limitați procesele de inițiere pe căi de lungime 2i

Numărul maxim de procese care pot iniția mesaje pe căi de lungime 2i dintr-un grup de 2i-1 + 1 procese consecutive.

Signup and view all the flashcards

Număr de mesaje pe cale de lungime 2i

Fiecare proces inițiază maximum 4 mesaje pentru o cale de lungime 2i (două dus, două întors).

Signup and view all the flashcards

Complexitatea algoritmului de alegere a liderului

Complexitatea totală a algoritmului este determinată de suma produsului dintre lungimea căii și numărul maxim de procese care pot iniția mesaje pe acea cale.

Signup and view all the flashcards

Complexitatea timpului de alegere a liderului

Timpul necesar pentru transmiterea mesajelor este determinat de timpul necesar transmiterii unui singur mesaj și de numărul maxim de mesaje care pot fi transmise în paralel.

Signup and view all the flashcards

Complexitatea algoritmului de alegere a liderului

Numărul total de mesaje este de ordinul O(n log n), unde n este numărul de procese. Timpul de execuție este de ordinul O(n).

Signup and view all the flashcards

Study Notes

Algoritmi Paraleli și Distribuiți - Alegerea unui Lider

  • Multe sisteme distribuite se bazează pe paradigma client-server: un server/coordonator (lider) și mai mulți clienți.
  • Dacă liderul se defectează, este nevoie de un nou lider.

Alegerea unui lider

  • Fiecare proces își cunoaște propria identitate și identitatea vecinilor săi.
  • Identitățile proceselor formează o mulțime ordonată.
  • Alegerea liderului se realizează prin determinarea procesului cu identitatea cea mai mică (sau cea mai mare).
  • Acest proces se face folosind algoritmi descentralizați, cu participarea tuturor proceselor din colecție.

Alegerea Liderului cu ajutorul Algoritmilor Undă

  • Toate procesele folosesc același algoritm local.
  • Algoritmul este descentralizat (poate fi inițiat de orice subgrup de procese).
  • În fiecare calcul algoritmul atinge o configurație în care un proces este lider iar restul au pierdut.

Algoritmi Undă pentru Alegerea Liderului

  • Algoritmii undă posedă proprietăți de terminare, decizie și consistență.
  • Proprietatea de terminare garantează că algoritmul se completează într-un număr finit de pași.
  • Proprietatea de decizie asigură că cel puțin un nod execută un eveniment decide.
  • Proprietatea de consistență garantează că orice proces execută cel puțin un eveniment ce precedă cauzal evenimentul decide.

Utilizarea Algoritmilor Undă pentru Alegerea Liderului

  • Fiecare proces are atașată o identitate.
  • Un nod decide atunci când un eveniment precedent cauzal a precedat fiecare eveniment prin care procesele au adăugat identitatea respectivă într-un vector al identităților cunoscute.
  • Procesul care decide va cunoaște identitatea tuturor proceselor.
  • Se alege procesul cu identitatea cea mai mică ca nou lider.
  • Se anunță (broadcast) identitatea liderului tuturor proceselor.

Algoritmul Arbore

  • Algoritmul impune ca toate frunzele să fie inițiatori.
  • Procesele folosesc variabile ws (boolean - asigură că fiecare proces transmite mesaj wakeup cel mult o dată) și wr (întreg - contorizează mesajele de wakeup recepționate.).
  • Atunci când un proces a primit un wakeup de fiecare canal, algoritmul de alegere începe.
  • Procesul care decide află identitatea liderului și trece într-o stare (leader sau lost).

Algoritmul LeLann

  • Fiecare proces difuzează celorlalte procese un mesaj cu id-ul său.
  • Fiecare proces colectează numerele celorlalte procese.
  • Fiecare proces află maximul.
  • Procesul cu id-ul maxim devine lider.

Algoritmul LeLann-Chang-Roberts

TIMP - O(N)

NR. MESAJE - caz cel mai bun 2N - 1

                          - caz cel mai rau N(N + 1) / 2
  • Mesajele sunt transmise în inel în sensul acelor de ceasornic.
  • Fiecare proces transmite procesului din dreapta un mesaj cu identificatorul său.
  • Un proces care primește un mesaj îl compară cu identificatorul propriu.
  • Dacă id-ul mesajului este mai mare decât al procesului, el transmite mesajul mai departe.
  • Dacă id-ul mesajului este mai mic, îl elimină.
  • Dacă id-ul mesajului este egal, procesul devine lider.
  • Algoritmul detectează un singur id maxim.

Algoritmul Hirschberg-Sinclair

TIMP - O(N logN) - cel mai defavorbail caz (nr mesaje la fel)

         - O(N) - general
  • Complexitatea algoritmului este O(N log N) în cel mai defavorabil caz .
  • Algoritmul lucrează pe un inel bidirecțional.
  • Procesele pot detecta din ce direcție vine un mesaj și pot trimite un răspuns în acea direcție folosind sendboth, sendpass și sendecho.
  • Algoritmul operează în faze, transmițând mesaje pe căi de lungime 2^k.
  • Procesele analizează mesaje, trecând prin stări de candidat sau pierdut.
  • Un proces care primește mesajul propriu devine lider, apoi anunță celelalte procese .

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser