Algoritm distribuit - Distributed algorithm

Un algoritm distribuit este un algoritm conceput pentru a rula pe hardware-ul computerului construit din procesoare interconectate . Algoritmii distribuiți sunt utilizați în diferite domenii de aplicații ale calculelor distribuite , cum ar fi telecomunicațiile , calculul științific , procesarea informațiilor distribuite și controlul proceselor în timp real . Problemele standard rezolvate prin algoritmi distribuiți includ alegerea liderilor , consensul , căutarea distribuită , generarea arborelui , excluderea reciprocă șialocarea resurselor .

Algoritmii distribuiți sunt un subtip de algoritm paralel , de obicei executat concomitent , cu părți separate ale algoritmului rulate simultan pe procesoare independente și având informații limitate despre ceea ce fac celelalte părți ale algoritmului. Una dintre provocările majore în dezvoltarea și implementarea algoritmilor distribuiți este coordonarea cu succes a comportamentului părților independente ale algoritmului în fața eșecurilor procesorului și a legăturilor de comunicații nesigure. Alegerea unui algoritm distribuit adecvat pentru a rezolva o anumită problemă depinde atât de caracteristicile problemei, cât și de caracteristicile sistemului pe care algoritmul va funcționa, cum ar fi tipul și probabilitatea eșecurilor procesorului sau legăturii, tipul de comunicare între procese care poate fi realizat și nivelul de sincronizare sincronizare între procese separate.

Probleme standard

Comitere atomică

Un commit atomic este o operație în care se aplică un set de modificări distincte ca o singură operație. Dacă comisia atomică reușește, înseamnă că toate modificările au fost aplicate. Dacă există un eșec înainte de a putea fi finalizată comisia atomică, „comiterea” este întreruptă și nu se vor aplica modificări.

Algoritmii pentru rezolvarea protocolului de confirmare atomică includ protocolul de confirmare în două faze și protocolul de confirmare în trei faze .

Consens

Algoritmii de consens încearcă să rezolve problema unui număr de procese care convin asupra unei decizii comune.

Mai precis, un protocol de consens trebuie să îndeplinească cele patru proprietăți formale de mai jos.

• Încheiere : fiecare proces corect decide o anumită valoare.
• Valabilitate : dacă toate procesele propun aceeași valoare , atunci fiecare proces corect decide .${\ displaystyle v}$${\ displaystyle v}$
• Integritate : fiecare proces corect decide cel mult o valoare, iar dacă decide o anumită valoare , atunci trebuie să fi fost propus de un proces.${\ displaystyle v}$${\ displaystyle v}$
• Acord : dacă decide un proces corect , atunci decide fiecare proces corect .${\ displaystyle v}$${\ displaystyle v}$

Algoritmii obișnuiți pentru rezolvarea consensului sunt algoritmul Paxos și algoritmul Raft .

Căutare distribuită

Alegerea liderului

Alegerea liderului este procesul de desemnare a unui singur proces ca organizator al unei sarcini distribuite între mai multe computere (noduri). Înainte de începerea sarcinii, toate nodurile de rețea nu știu care nod va servi ca „lider” sau coordonator al sarcinii. Cu toate acestea, după executarea algoritmului de alegere a liderilor, fiecare nod din rețea recunoaște un anumit nod unic ca lider de sarcină.

Excludere mutuala

Structuri de date care nu blochează

Difuzare de încredere

Difuzarea fiabilă este o primitivă de comunicare în sistemele distribuite. O transmisie de încredere este definită de următoarele proprietăți:

• Valabilitate - dacă un proces corect trimite un mesaj, atunci un proces corect va transmite în cele din urmă acel mesaj.
• Acord - dacă un proces corect transmite un mesaj, atunci toate procesele corecte transmit în cele din urmă acel mesaj.
• Integritate - fiecare proces corect transmite același mesaj cel mult o dată și numai dacă acel mesaj a fost trimis de un proces.

O transmisie de încredere poate avea o ordonanță secvențială, cauzală sau totală.

Replicare

Alocare resurselor

Generarea copacului

Ruperea simetriei, de exemplu colorarea vertexului

Referințe

Lecturi suplimentare

• Christian Cachin; Rachid Guerraoui; Luís Rodrigues (2011), Introducere în programarea distribuită fiabilă și sigură (2. ed.), Springer, ISBN 978-3-642-15259-7
• C. Rodríguez, M. Villagra și B. Barán, Asynchronous team algorithms for Boolean Satisfiability, Bionetics2007, pp. 66-69, 2007.

linkuri externe

• Medii legate de algoritmi distribuiți la Wikimedia Commons
• MIT Open Courseware - Algoritmi distribuiți