Sr-3-wyk-2.0-Slajd35

Algorytm Czasowy-RB

Powyższy algorytm będzie w definicji algorytmów oznaczany przez R?. Oparte na nim algorytmy gwarantujące dodatkowo własności uporządkowania FIFO oraz przyczynowego, będą oznaczane kolejno przez F? i C?.

Załóżmy, że podsieć komunikacyjna ma następujące właściwości:

1. Co najwyżej f procesów może ulec awarii.

2. Każde dwa poprawne procesy są połączone ścieżką długości co najwyżej d , złożonej wyłącznie z poprawnych

procesów i łączy komunikacyjnych.

3. Maksymalne opóźnienie wiadomości jest ograniczone stałą ? .

4. Czas wykonania lokalnej operacji jest zerowy.

Można udowodnić następujące twierdzenie :

Przy założeniach 1-4, algorytm niezawodnego rozesłania RB zachowuje ?-uporządkowanie (w czasie rzeczywistym ) ze stałą ? =( f+d ) ? .

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