Algorytmy rozproszone odporne na awarie mogą być deterministyczne lub probabilistyczne. Weźmy na przykład problem konsensusu.
Paxos jest deterministyczny w tym sensie, że biorąc pod uwagę przyjęte założenie, zawsze działa.
Natomiast randomizowany konsensus działa z określonym prawdopodobieństwem.
Jaka jest zaleta projektowania i stosowania algorytmu deterministycznego?
Założenia, na których opierają się algorytmy deterministyczne, mają również prawdopodobieństwo utrzymania się w rzeczywistości (tzw. Zasięg ich założenia ). Dlatego zawsze istnieje prawdopodobieństwo, że algorytm deterministyczny nie działa w rzeczywistości.
Odpowiedzi:
Odpowiem na to z perspektywy algorytmów grafów rozproszonych ( algorytmy rozproszone, które rozwiązują problem grafów związany ze strukturą sieci komunikacyjnej).
Oto kilka nieoczywistych powodów projektowania deterministycznych algorytmów rozproszonych w tym ustawieniu:
Podprogramy w algorytmach losowych . Na str. 12–13 z tych slajdów Elkin przedstawia technikę projektowania algorytmów, w której można użyć szybkich deterministycznych algorytmów rozproszonych jako podprogramu w celu skonstruowania szybkiego randomizowanego algorytmu rozproszonego. Co ciekawe, w tym samym kontekście nie można zastosować typowego algorytmu losowego jako podprogramu (prawdopodobieństwo błędu byłoby zbyt wysokie).
Odporność na awarie . Istnieje translacja mechaniczna, która pozwala przekształcić szybki deterministyczny algorytm rozproszony w szybki samostabilizujący się algorytm rozproszony (patrz np. Sekcja 2.4 niniejszego badania ). Podobna konwersja nie jest znana w przypadku algorytmów randomizowanych (i myślę, że w ogólnym przypadku jest mało prawdopodobne).
źródło