В чем преимущество разработки детерминированных распределенных алгоритмов?

10

Распределенные алгоритмы, которые устойчивы к сбоям, могут быть либо детерминированными, либо вероятностными. Возьмите для примера проблему консенсуса.

  • Paxos является детерминированным в том смысле, что, учитывая допущение, оно всегда работает.

  • В противоположность этому рандомизированный консенсус работает с заданной вероятностью.

В чем преимущество разработки и использования детерминированного алгоритма?

Предположения, на которые опираются детерминированные алгоритмы, также имеют вероятность того, что они сохранятся в реальности (то, что называется их охватом предположений ). Следовательно, всегда существует вероятность того, что детерминистический алгоритм не работает в реальности.

danyhow
источник
Paxos / wikipedia, семейство протоколов
vzn
1
Можете ли вы быть более конкретным с вашим комментарием?
Danyhow
1
Хорошо отметить, что рандомизация обычно используется для свойств живучести, а не для свойств безопасности. Свойства безопасности всегда сохраняются, однако есть вероятность, что алгоритм не завершится (что обычно уменьшается с течением времени).
Каве

Ответы:

10

Я отвечу на это с точки зрения алгоритмов распределенных графов (распределенных алгоритмов, которые решают проблему графов, связанную со структурой сети связи).

Вот несколько неочевидных причин для разработки детерминированных распределенных алгоритмов в этой настройке:

  • Подпрограммы в рандомизированных алгоритмах . На стр. 12–13 из этих слайдов Элкин описывает метод проектирования алгоритма, в котором вы можете использовать быстрые детерминированные распределенные алгоритмы в качестве подпрограммы для построения быстрого рандомизированного распределенного алгоритма. Интересно, что это не возможно использовать типичный вероятностный алгоритм в качестве подпрограммы в том же контексте (вероятность ошибки будет слишком высока).

  • Отказоустойчивость . Существует механический перевод, который позволяет вам преобразовать быстрый детерминированный распределенный алгоритм в быстрый самостабилизирующийся распределенный алгоритм (см., Например, раздел 2.4 этого обзора ). Подобное преобразование не известно для рандомизированных алгоритмов (и я думаю, что оно вряд ли будет существовать в общем случае).

Юкка Суомела
источник