Jaka jest zaleta projektowania deterministycznych algorytmów rozproszonych?

10

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.

danyhow
źródło
Paxos / wikipedia, rodzina protokołów
od
1
Czy możesz być bardziej szczegółowy w swoim komentarzu?
danyhow
1
Warto zauważyć, że randomizacja jest zwykle stosowana do właściwości żywotności, a nie właściwości bezpieczeństwa. Właściwości bezpieczeństwa są zawsze aktualne, jednak istnieje szansa, że ​​algorytm się nie zakończy (co zwykle maleje w miarę upływu czasu).
Kaveh

Odpowiedzi:

10

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

Jukka Suomela
źródło