Pr-1st-1.1-m13-Slajd62

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Potrzeba randomizacji

Potrzeba randomizacji


Można sobie zadać pytanie, dlaczego w wierszu 37 algorytmu występuje losowe wybranie wartości, zamiast dokonania wyboru za pomocą ściśle określonej, deterministycznej funkcji. Uzasadnienie przedstawia rysunek obrazujący przykładowe wykonanie algorytmu. Wyobraźmy sobie, że każdy monitor, zamiast w wierszu 37 losować wartość, wybiera pierwszą wartość różną od wyróżnionej wartości pustej.


Monitor dostaje wartość od . Ponieważ obie wartości się różnią (), więc zgodnie z wierszem 19, wybierze wartość pustą jako propozycję wartości do uzgodnienia. Identyczna sytuacja zajdzie w monitorze , natomiast monitor otrzyma propozycję wartości 2, i ponieważ wszystkie otrzymane wartości są identyczne, zaproponuje dalej 2.


W drugiej fazie może z kolei zajść sytuacja, w której otrzymałby wartość pustą od i dlatego deterministycznie (zamiast losowo) wybrałby wartość 1. Monitor natomiast otrzymałby wartość 2 od i ponieważ jest ona różna od wartości pustej, przyjąłby ją jako swoją propozycję. z kolei otrzymuje od wartość pustą, ale ponieważ sam wcześniej zaproponował wartość różną od wartości pustej, przyjmuje ją jako podstawę do kolejnej rundy. Jak widać, w kolejnej rundzie wszystkie procesy proponują dokładnie takie same wartości jak poprzednio – a ponieważ taka sytuacja może się powtarzać, skutkuje to niebezpieczeństwem, że algorytm nigdy by się nie zakończył. Stąd właśnie wynika potrzeba randomizacji.


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