Распределенные алгоритмы, которые устойчивы к сбоям, могут быть либо детерминированными, либо вероятностными. Возьмите для примера проблему консенсуса.
Paxos является детерминированным в том смысле, что, учитывая допущение, оно всегда работает.
В противоположность этому рандомизированный консенсус работает с заданной вероятностью.
В чем преимущество разработки и использования детерминированного алгоритма?
Предположения, на которые опираются детерминированные алгоритмы, также имеют вероятность того, что они сохранятся в реальности (то, что называется их охватом предположений ). Следовательно, всегда существует вероятность того, что детерминистический алгоритм не работает в реальности.
Ответы:
Я отвечу на это с точки зрения алгоритмов распределенных графов (распределенных алгоритмов, которые решают проблему графов, связанную со структурой сети связи).
Вот несколько неочевидных причин для разработки детерминированных распределенных алгоритмов в этой настройке:
Подпрограммы в рандомизированных алгоритмах . На стр. 12–13 из этих слайдов Элкин описывает метод проектирования алгоритма, в котором вы можете использовать быстрые детерминированные распределенные алгоритмы в качестве подпрограммы для построения быстрого рандомизированного распределенного алгоритма. Интересно, что это не возможно использовать типичный вероятностный алгоритм в качестве подпрограммы в том же контексте (вероятность ошибки будет слишком высока).
Отказоустойчивость . Существует механический перевод, который позволяет вам преобразовать быстрый детерминированный распределенный алгоритм в быстрый самостабилизирующийся распределенный алгоритм (см., Например, раздел 2.4 этого обзора ). Подобное преобразование не известно для рандомизированных алгоритмов (и я думаю, что оно вряд ли будет существовать в общем случае).
источник