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

Другой открытой проблемой является вопрос о том, существует ли рандомизированная реализация 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> все еще остается проблемой.