Рандомизация в распределенных вычислениях: различия между версиями

Решение описанных выше задач осложняется тем, что программист слабо контролирует скорость выполнения у отдельных процессоров. Чтобы смоделировать этот факт, предполагается, что расписание работы процессоров выбирает противник. Хорошо известно, что не существует детерминированного алгоритма, способного решить задачу бинарного или ID-консенсуса в этой модели с с соперником, если число процессоров больше 1 [6, 7]. Поэтому для решения этой задачи исследователи обратились к использованию рандомизированных алгоритмов [1]. Такие алгоритмы имеют доступ к случайным подбрасываниям монет. Для рандомизированных алгоритмов рассматриваются три типа соперников. Предполагается, что ''сильный соперник'' знает результат подбрасывания монеты сразу после того, как она подброшена, и может соответствующим образом изменить свое расписание. ''Забывчивый соперник'' должен зафиксировать расписание до того, как будет подброшена какая-либо из монет. ''Промежуточному сопернику'' не разрешается видеть результат подбрасывания монеты до тех пор, пока какой-либо процесс не сделает выбор на основе этого подбрасывания. В частности, процесс может подбросить монету и записать результат в глобальный регистр, но промежуточный соперник не будет знать результат подбрасывания монеты, пока какой-либо процесс не прочитает значение, записанное в регистре.