Clasificarea protocoalelor Gossip și Epidemic

Ajay Rathore
Java Software Engineer @ Accesa

Protocolul Gossip sau Epidemic reprezintă o clasă de algoritmi, care facilitează comunicarea într-o rețea distribuită, având aplicații multiple - de la comunicarea în rețelele de registre distribuite și rețele IOT, la sincronizarea actualizărilor prin replicarea bazei de date și nu numai.

Articolul curent se concentrează pe clasificarea protocoalelor - pentru a înțelege aplicațiile acestora - și pe analiza avantajelor și dezavantajelor lor. Cu toate că există diverse lucrări care documentează metodele de implementare și criteriile de clasificare, pentru acest studiu, materialele au fost selectate numai dacă au prezentat date de performanță relevante pentru implementările discutate în cele ce urmează.

Cele două protocoale urmează o abordare similară cu cea a răspândirii epidemiilor în lumea reală sau a răspândirii zvonurilor. În implementările acestor algoritmi, accentul se pune, de obicei, pe comunicarea de date către noduri selectate aleatoriu, așteptarea fiind de a ajunge la toate nodurile din rețea.

Pentru a clasifica protocolul Gossip, primul lucru care trebuie analizat este originea acestui tip de protocol în lucrarea publicată de Alan Demers et al. [1], unde autorii abordează problema replicării actualizărilor bazei de date la mii de site-uri diferite. Provocarea a fost de a realiza acest lucru pe o rețea nu tocmai sigură și aflată într-o schimbare lentă, într-un mod eficient și scalabil.

Au fost analizate trei abordări:

1. Direct mail. Intuitiv, poate fi înțeleasă ca trimiterea unei actualizări către toate nodurile. Iar fiecare nod din rețea trimite actualizarea lui către celelalte noduri. În acest fel, pentru n actualizări, vom genera m mesaje, unde m este numărul de noduri. Astfel, în orice moment este posibil să existe mn* mesaje în rețea. De asemenea, în cazul unei rețele instabile, acest lucru poate însemna că actualizările nu sunt trimise tuturor nodurilor.

2. Anti-entropy. Se rezolvă diferențele de stare dintre diversele locații, selectându-se o pereche aleatorie și analizându-se întreaga bază de date. Deoarece analiza delta a întregii stări nu este promptă, această abordare este mult mai lentă decât prima. Cu toate acestea, este mult mai fiabilă. În cadrul acestei abordări, generăm un număr mic de mesaje, în timp ce două noduri fac schimb de stări care ar putea conține mai multe actualizări. Este posibil chiar să fi primit actualizări de la alte noduri și, într-un singur schimb, să transmită și aceste actualizări, existând un schimb de date al întregii baze de date.

3. Rumor Mongering. Fiecare actualizare este tratată ca o informație crucială. Un nod care primește o informație selectează un alt nod și o împărtășește cu un nod aleatoriu. Același comportament continuă până când se atinge scopul de a comunica cu fiecare nod. Deoarece această metodă trimite numai actualizări noi, dimensiunea mesajelor este redusă, cu toate că există o probabilitate non-zero ca o informație ,,să moară" înainte de a ajunge la toate nodurile.

Anti-entropy și Rumor Mongering sunt variații ale protocoalelor epidemice, care definesc performanța acestor protocoale prin analiza a trei criterii [1]:

• Reziduuri. Câte noduri nu au primit o actualizare atunci când nu mai sunt transmise informații.

• Trafic. Numărul mesajelor de actualizare trimise pe site.

• Întârziere. Timpul mediu necesar pentru ca o actualizare să ajungă la un nod după introducerea inițială în rețea și timpul în care mesajul ajunge la ultimul nod.

Clasificarea protocoalelor din clasa Epidemic

Diseminare și agregare

Încă de la punctul de origine al unui astfel de protocol, putem observa că s-a încercat răspândirea informațiilor (diseminare) și, în același timp, procesarea informațiilor pe măsură ce actualizările sunt agregate (agregare). Putem spune că primele două clasificări pot fi făcute pe baza acestor două sarcini. Vom împărți algoritmii în aceste două secțiuni cu intenția de a diferenția care implementări/strategii sunt bune pentru diseminare, respectiv, agregare.

Iată câteva implementări și categoriile în care se pot încadra:

Tabelul 1. Clasificarea algoritmilor pe baza accentului pe care îl pun pe procesarea datelor față de răspândirea mai rapidă/cu costuri reduse a informațiilor

Algoritmii P-Q epidemic, epidemic with immunity and epidemic with TTL au fost studiați printr-un studiu unificat care a adus îmbunătățiri ale acestora [2].

Această clasificare subliniază accentul pus de protocol în furnizarea de agregări informaționale bune în rețea vs. concentrarea pe transferul rapid de informații. Se poate observa un compromis oblic între acestea pe baza informațiilor privind întârzierea [1].

Tabelul 2. Compararea performanțelor pentru diferiți algoritmi

Se poate observa că algoritmii axați pe diseminare lucrează la reducerea timpului de întârziere. Prin urmare, putem rezuma avantajele și dezavantajele acestei clasificări după cum urmează:

Tabelul 3. Pro și contra diseminării și agregării

Comunicare sincronă și asincronă

Următorul criteriu de clasificare poate fi văzut ca fiind tipul de comunicare utilizat între noduri. Aceeași clasificare este utilizată de Bunsel, Yann & Bertier [8], care definesc comunicarea sincronă astfel: "o comunicare sincronă este modelată printr-o întârziere de transmisie limitată"[8], iar pe cea asincronă: "o comunicare asincronă nu impune o limită asupra întârzierii de transmisie a unui mesaj". [8]

Iată câteva implementări care se pot încadra în această clasificare:

Tabelul 4. Clasificarea algoritmilor în funcție de modelul lor de comunicare

Dintre cei patru algoritmi specifici prezenți în tabelul de mai sus, orice implementare de algoritm care se finalizează într-un timp delimitat va fi considerată sincronă, iar opusul, asincronă. Un exemplu este MFWF, care a fost considerat sincron pentru acest studiu, deoarece în algoritmii prezentați nu există dovezi legat de existența vreunui mecanism care să asigure o procesare asincronă.

Tabelul 5. Descrierea performanțelor algoritmilor

Performanțele algoritmilor selectați nu sunt exprimate în aceleași unități, mai jos fiind prezentat tabelul cu unitățile propuse în implementări și valorile acestora.

Unul dintre avantajele majore pentru comunicarea asincronă care poate fi observat în aceste implementări este posibilitatea implementării consensului fără selectarea liderului.

În Tabelul 6 sunt prezentate avantajele și dezavantajele pentru fiecare categorie.

Tabelul 6

Comunicarea anonimă și non-anonimă

Definiția acestor categorii este, de asemenea, studiată inspirându-ne din Busnel, Yann et al. [8], unde autorii definesc protocoalele de zvonuri anonime (AGP) ca fiind "protocoale care nu necesită cunoașterea identității niciunui element pentru niciuna dintre cele trei funcții ale protocolului generic". [8] și protocolul de zvon non-anonim (NGP) ca fiind "inconștient de identitățile elementelor cu care comunică sau ale oricărui alt element"[8].

Având în vedere aceste definiții, putem găsi următoarele implementări de protocoale în fiecare categorie:

Utilizarea generală a AGP pare aplicabilă cazurilor în care protocolul de gossip este utilizat atât pentru diseminare, cât și pentru agregare, iar NGP este utilizat în scopul construirii de topologii.

Performanțele Rumor Mongering și Anti-Entropy au fost discutate mai sus. Performanța celor trei algoritmi rămași poate fi observată folosind viteza de convergență. Chiar dacă convergența poate avea semnificații diferite, în acest caz, ne vom referi la convergența spre obiectivul algoritmului.

Este de remarcat faptul că conștientizarea topologică necesită mecanisme speciale pentru a partaja omologii cunoscuți în NGP. Nu există argumente clare pro și contra în acest caz, deoarece această clasă de algoritmi este implementată în scopuri foarte diferite.

Corecția erorilor vs. corecția fără erori

Aceasta este o categorie inspirată de faptul că algoritmi precum Rumor Mongering au o probabilitate diferită de zero de a nu răspândi toate actualizările [14] [1], implicând faptul că pot exista noduri în sistem care nu au primit actualizări. În schimb, Anti-Entropy este un algoritm fiabil, care asigură că toate actualizările ajung în tot sistemul.

Avantajul algoritmului de corecție fără erori, cum ar fi Rumor Mongering, este rapiditatea. Același lucru lipsește în cazul algoritmilor de corecție ale erorilor, cum ar fi Anti-Entropy.

Alte considerații

Multe alte clasificări pot fi construite prin luarea în considerare a combinațiilor dintre aceste clase diferite, spre exemplu Anonymous Synchronized Gossip Protocol [8].

Alte clase de protocoale de gossip se bazează pe criterii de localizare și alte criterii [7] precum:

• Location based gossiping protocol;

• chance-based gossiping protocol;

• Fair Efficient Location-based Gossiping;

• Fuzzy-Gossip;

• Fitness-Gossiping (FGP).

Mențiuni

Acest raport a fost elaborat sub îndrumarea doamnei dr. conf. Elena Simona Apostol, din cadrul Universității Politehnice din București, ca parte a cursului Distributed Algorithms.

Bibliografie

[1] Alan Demers, Mark Gealy, Dan Greene et al, Epidemic Algorithms for Replicated Database Maintenance, Palo Alto Research Center 1989

[2] Feng, Zuyong și Chin, Kwan-Wu: A unified study of epidemic routing protocols and their enhancements 2012, 1484-1493

[3] T. Matsuda și T. Takine, "(p,q)-epidemic routing for sparsely populated mobile ad hoc networks," IEEE JSAC, vol. 26, nr. 5, pp. 783-793, iunie 2008

[4] P. Mundur, M. Seligman și J. N. Lee, "Immunity-based epidemic routing in intermittent networks", în IEEE SECON, California, SUA, 16-20 iunie 2008, pp. 609-611

[5] J. Davis, A. Fagg și B. Levine, "Wearable computers as packet transport mechanisms in highly partitioned ad-hoc networks", în Proceedings of Fifth International Symposium on Wearable Computers (ISWC), Zurich, Elveția, 18-21 octombrie 2001, pp. 141-148

[6] R. Karp, C. Schindelhauer, S. Shenker și B. Vocking: Randomized Rumor Spreading

[7] Altoaimy L, Alromih A, Al-Megren S, Al-Hudhud G, Kurdi H, Youcef-Toumi K. Context-Aware Gossip-Based Protocol for Internet of Things Applications. Sensors (Basel). 2018 iul. 11; 18(7):2233. doi: 10.3390/s18072233. PMID: 29997354; PMCID: PMC6068978

[8] Busnel, Yann & Bertier, Marin & Kermarrec, Anne-Marie. (2008). Bridging the Gap between Population and Gossip-based Protocols

[9] David Picard, Jerome Fellus, Stephane Garnier 2021. Non asymptotic bounds in asynchronous sum-weight gossip protocols

[10] Georgiou, Chryssis & Gilbert, Seth & Guerraoui, Rachid & Kowalski, Dariusz. (2008). On the Complexity of Asynchronous Gossip. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. 10.1145/1400751.1400771

[11] M. Jelasity, A. Montresor și O. Babaoglu. Gossip-based aggregation in large dynamic networks. ACM Transactions on Computer Systems, 23(3):219-252, 2005

[12] M. Jelasity și O. Babaoglu. T-Man: Fast gossip-based construction of largescale overlay topologies. Raport tehnic UBLCS-2004-7, Universitatea din Bologna, Departamentul de Informatică, Bologna, Italia, mai 2004

[13] M. Jelasity, A. Montresor și O. Babaoglu. Gossip-based aggregation in large dynamic networks. ACM Transactions on Computer Systems, 23(3):219-252, 2005

[14] Márk Jelasity Universitatea din Szeged și Academia Maghiară de Științe, Gossip 2011