Jaka jest zaleta projektowania deterministycznych algorytmów rozproszonych?

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.

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).