Algoritmi undă
Un algoritm undă este un tip de algoritm distribuit folosit pentru propagarea informațiilor în cadrul unei rețele distribuite de noduri.
Un algoritm undă este caracterizat de următoarele trăsături:
- există un proces inițiator (sau mai multe), care declanșează trimiterea de mesaje în cadrul rețelei
- fiecare proces trimite informații către vecinii săi, cu excepția părintelui, de la care a primit informația pe care o pasează mai departe
- fiecare proces primește informații de la vecini (cu excepția părintelui) și o trimite părintelui
- la final se ia o decizie în legătură cu informațiile primite
Alegerea liderului
Clusterele de noduri pot sa fie ierarhizate sau nu. În cadrul clusterelor bazate pe noduri autonome, nu există un lider bine stabilit, ci contracte clare de comunicare între noduri. Pe de altă parte, în clusterele care au lider, unul sau mai multe noduri îndeplinesc funcții elevate. Printre funcțiile elevate se numără și stabilirea și distribuirea topologiei către celelalte noduri.
Liderul reprezintă un nod sau un grup de noduri ales pe baza unei euristici. Euristica poate ține cont de resursele nodului respectiv, de numărul sau de natura proceselor care rulează pe el sau pur și simplu de lucruri simple, precum identificatorul său.
În cadrul acestui laborator vom explora alegerea liderului bazat pe rangul cel mai mare al unui nod. Alegerea liderului se va face pe baza unui algoritm de tipul heartbeat (algoritmul pulsațiilor).
Alegerea liderului. Heartbeat
Funcționarea unui algoritm heartbeat se aseamănă cu bătăile inimii:
- sistola → partea de "expandare". Informația este transmisă către nodurile vecine.
- diastola → partea de "contracție". Informația este receptată înapoi de la nodurile vecine.
În cadrul alegerii liderului, algoritmul heartbeat va fi aplicat în felul următor:
- nodurile vor trimite rangul lor către vecini
- fiecare nod va calcula liderul local în funcție de maximul dintre rangul propriu și informația primită de la vecin
- vecinii vor trimite înapoi liderul lor local către nodurile de la care au primit mesaj
- nodurile care au trimis mesajul inițial își vor actualiza valoarea liderului local
Algoritmul se repetă de un număr suficient de ori ca să se asigure convergența informației.
Pseudocod:
lider = rang; // la început, fiecare nod se consideră lider
for (pas = 0; pas < convergență; pas++) {
for (i = 0 to nr_vecini) {
trimite lider către vecin[i]
primește lider_vecin de la oricare vecin
lider = max(lider_vecin, lider);
}
}
Un exemplu de rulare a acestui algoritm poate fi observat aici.
Construirea arborelui de acoperire
După ce liderul a fost ales, acesta va iniția construirea arborelui de acoperire.
Scopul arborelui de acoperire este ca fiecare nod să știe, în orice moment de timp, cum să ajungă către lider.
Arborele de acoperire se reprezintă, cel mai ușor, printr-un array de părinți. Construirea acestui arbore se realizează printr-un algoritm de tip undă - ecou.
Construirea arborelui de acoperire. Undă - ecou
Algoritmul undă are două părți:
- unda → toate nodurile, cu excepția liderului, așteaptă să primească un mesaj. Liderul inițiază unda. La primirea primei sonde, fiecare nod își notează părintele și trimite un mesaj tuturor vecinilor, mai puțin celui de la care a primit (părintele său)
- ecou → se așteaptă primirea unui mesaj de la toți vecinii, mai puțin de la părinte. Informațiile primite de la vecini sunt agregate într-un array de părinți și acesta este trimis către părinte.
La final, liderul va deține array-ul de părinți final, care reprezintă arborele de acoperire. Arborele de acoperire este apoi distribuit întregului sistem.
Pseudocod:
if (rank != lider) {
primește sondă de la oricare vecin
parinte[rank] = rank_vecin
}
// Dăm mai departe sonda către toți ceilalți vecini
for (i = 0; i < nr_vecini; i++) {
// Sonda nu se trimite și către cel de la care am primit-o
if (vecin[i] != parinte[rank]) {
trimite sondă către vecin[i]
}
}
// Așteptăm ecou de la fiecare vecin, mai puțin de la părinte
for (i = 0; i < nr_vecini; i++) {
// vedem dacă vecinul curent nu este părintele nodului
if (vecin[i] != parinte[rank]) {
primește array-ul de părinți (parinteRecv[]) sau sonda de la vecin[i]
if (am_primit_sonda) { // sondă de la un vecin al cărui tată nu sunt în DST
// Sondele le ignor
continue;
}
else { // ecou de la un copil al meu
// Îmi completez topologia locala cu ce gasesc nou in ecou
for (j = 0; j < nr_procese; j++) {
// dacă nodul j are părinte
// (parinte[j] == -1 => nodul j nu are părinte)
// se completează array-ul de părinți
// (bottom - top, de la frunze până în rădăcină)
if (parinteRecv[j] != -1) {
parinte[j] = parinteRecv[j];
}
}
}
}
}
// În acest punct, nodul curent are topologia formată de nodurile copii
// până la nivelul curent și trebuie să o trimită părintelui său
if (rank != lider) {
// fiecare proces care nu e lider trimite topologia curentă
// către părintele său, care o va completa
trimite array de părinți (parinti[]) catre parinte[rank]
}
/// ----------------------------------------------------------
// De aici începe etapa (opțională) de broadcast a topologiei
// (de tip arbore de acoperire) către toate nodurile.
// În acest punct, rădăcina cunoaște arborele de acoperire.
/// ----------------------------------------------------------
if (rank != lider) {
// Fiecare nod (mai puțin rădăcina,
// care are deja toată informația necesară) așteaptă topologia de
// la părintele său
primește array de părinți (parinti[]) de la parinte[rank]
}
// Dăm mai departe topologia completă către copiii nodului curent
for (i = 0; i < nr_proc; i++) {
if (parinte[i] == rank) {
trimite array de părinți (parinti[] către nodul i
}
}
Un exemplu de rulare a acestui algoritm poate fi observat aici.