Pr-1st-1.1-m12-Slajd43

Probabilistyczne rozgłaszanie niezawodne: Specyfikacja

Problem implozji potwierdzeń wymusił poszukiwanie rozwiązań lepiej skalowalnych niż rozważane poprzednio. Interesującą propozycją jest podejście probabilistyczne, oparte na przykładach zaczerpniętych z rzeczywistości – takich jak szerzenie się chorób zakaźnych albo rozpowszechnianie plotek. Stąd tego typu mechanizmy (algorytmy) nazwano algorytmami epidemicznymi (ang. epidemic ) czy też plotkarskimi (ang. gossiping, rumor mongering ). Korzystają one z abstrakcji komunikacyjnej (mechanizmu) określanej jako probabilistyczne rozgłaszanie niezawodne (ang. probabilistic reliable broadcast ).

Mechanizmy probabilistycznego rozgłaszania niezawodnego charakteryzują się, podobnie jak poprzednie mechanizmy rozgłaszania, własnościami ważności, braku powielania i braku samogeneracji. Zupełnie inaczej jest tu zdefiniowana własność ważności (ang. validity ) oznaczająca, że dane jest prawdopodobieństwo, takie że jeżeli procesy $P_i$ oraz $P_j$ są poprawne, to każda wiadomość rozgłaszana przez proces $P_i$ jest ostatecznie dostarczona do $P_j$ z tym prawdopodobieństwem. Dopuszczalne (choć oczywiście niepożądane) są zatem sytuacje, w których wiadomość rozgłaszana nie jest dostarczona do wszystkich poprawnych procesów, nawet jeżeli nadawca wiadomości był poprawny. Widać tutaj podobieństwo do podstawowego rozgłaszania niezawodnego. W pewnym sensie podstawowe rozgłaszanie niezawodne również można by określić mianem probabilistycznego. W przypadku probabilistycznego rozgłaszania niezawodnego prawdopodobieństwo nie jest jednak bezpośrednio powiązane z możliwością awarii procesu.

Pozostałe dwie własności nie różnią się od odpowiednich własności uprzednio przedstawionych mechanizmów rozgłaszania:

Własność braku powielania (ang. no duplication ) oznacza, że jeżeli wiadomość jest dostarczona to jest dostarczona co najwyżej raz.

Własność braku samogeneracji (ang. no creation ) oznacza, że jeżeli jakaś wiadomość jest dostarczona do procesu $P_j$, to została wcześniej rozgłoszona przez jakiś proces $P_i$.

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