Pr-1st-1.1-m11-Slajd60

Problem wyboru lidera

W systemach rozproszonych bywają sytuacje, w których problemem nie jest wykrycie, które procesy uległy awarii, ale wspólne uzgodnienie wyboru jednego procesu, który wciąż jest poprawny i któremu wszystkie inne procesy ufają. Detektor wspomagający wybór jednego zaufanego procesu określany jest jako detektor lidera $\Omega$. Taki zaufany proces może działać jako koordynator, niezbędny w pewnych rozproszonych algorytmach. Stąd też problem ten nazywa się problemem wyboru lidera (ang. eventual leader election ).

Wprowadzimy teraz abstrakcję detektora $\Omega$, inaczej detektora ostatecznego lidera (ang. eventual leader detector ), wykonującego algorytm wyboru lidera. Mechanizm ten ma zapewniać, że wszystkie poprawne procesy zgodzą się ostatecznie na wybór tego samego procesu.

Mechanizm wyboru ostatecznego lidera posiada własności ostatecznej dokładności i ostatecznej zgodności.

Własność ostatecznej dokładności (ang. eventual accuracy ) oznacza, że istnieje pewna chwila czasu, po której wszystkie poprawne procesy ufają (nie podejrzewają) pewnemu poprawnego procesu.

Własność ostateczna zgodność (ang. eventual agreement ) oznacza, że istnieje pewna chwila czasu, po której nie ma dwóch takich poprawnych procesów, które by ufały dwóm różnym procesom.

Własności te oznaczają, że chociaż w czasie działania algorytmu lider może się zmieniać w dowolny sposób, jednakże ostatecznie wszystkie procesy zaczynają ufać jednemu liderowi i wyboru swojego już nie zmieniają – wybór lidera stabilizuje się.

<< Poprzedni slajd | Spis treści | Następny slajd >>