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

'''Теорема 1. Предполагая существование мультирайтерных мультиридерных регистров, существует рандомизированный алгоритм решения задачи двоичного консенсуса против промежуточного соперника с O(1) ожидаемых шагов на процессор.'''

Оба этих результата предполагают, что каждый процессор имеет уникальный идентификатор. До получения этого результата самый быстрый из известных рандомизированных алгоритмов для двоичного консенсуса использовал однорайтерные мультиридерные регистры, был устойчив относительно сильного соперника и требовал <math>O(n \; log^2 \; n)</math> шагов на процессор [2]. Таким образом, вышеуказанные улучшения получены за счет ослабления соперника и усиления модели системы по сравнению с [2].

Бинарный консенсус является одной из наиболее фундаментальных проблем в распределенных вычислениях. Примером ее важности может служить следующий результат, полученный Херлихи [8]. Если абстрактный тип данных X вместе с общей памятью являются достаточно мощными для реализации консенсуса без ожидания, то X вместе с общей памятью является достаточно мощным для реализации без ожидания любой другой структуры данных Y. Таким образом, используя этот результат, можно создать версию любой структуры данных без ожидания, используя в качестве строительного блока только мультирайтерные мультиридерные регистры без ожидания.

Другой открытой проблемой является вопрос о том, существует ли рандомизированная реализация ID-консенсуса с использованием мультирайтерных мультиридерных регистров, которая была бы устойчивой к промежуточному сопернику и у которой ожидаемое число шагов на процессор было бы лучше, чем <math>O(log^2 \; n)</math>. В частности, возможно ли константное время выполнения? Ауманн в продолжении этой работы смог улучшить ожидаемое время выполнения на процесс до <math>O(log \; n)</math> [4]. Однако, насколько известно авторам статьи, дальнейших улучшений не было.

Третьей нерешенной задачей является сокращение времени, необходимого нахождения бинарного консенсуса против сильного соперника с однорайтерными мультиридерными регистрами. Самый быстрый из известных рандомизированных алгоритмов в этом сценарии требует <math>O(n \; log^2 \; n)</math> шагов на процессор [2]. Тривиальная нижняя граница количества шагов на процессор при использовании однорайтерных регистров равна <math>\Omega(n)</math>. Тем не менее, разрыв с <math>O(log^2 \; n)</math> все еще остается проблемой.