4817
правок
Рандомизация в распределенных вычислениях: различия между версиями
Перейти к навигации
Перейти к поиску
м
Рандомизация в распределенных вычислениях (посмотреть исходный код)
Версия от 05:06, 29 июня 2025
, 29 июнь→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 55: | Строка 55: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Данный результат оставляет открытыми несколько вопросов. Во-первых, остается нерешенным вопрос о количестве шагов на процесс, необходимых для достижения рандомизированного консенсуса с использованием мультирайтерных мультиридерных регистров против сильного соперника. Недавний результат Аттии и Сенсор демонстрирует нижнюю границу | Данный результат оставляет открытыми несколько вопросов. Во-первых, остается нерешенным вопрос о количестве шагов на процесс, необходимых для достижения рандомизированного консенсуса с использованием мультирайтерных мультиридерных регистров против ''сильного'' соперника. Недавний результат Аттии и Сенсор демонстрирует нижнюю границу <math>\Omega(n^2)</math> суммарного количества шагов для всех процессоров с мультирайтерными мультиридерными регистрами (подразумевая <math>\Omega(n)</math> шагов на процесс) [3]. Авторы также доказали соответствующую верхнюю границу <math>O(n^2)</math> суммарного количества шагов. Однако вопрос о том, как преодолеть разрыв в количестве шагов на каждый процесс, остается открытым. | ||
Другой открытой проблемой является вопрос о том, существует ли рандомизированная реализация ID-консенсуса с использованием мультирайтерных мультиридерных регистров, которая была бы устойчивой к промежуточному сопернику и у которой ожидаемое число шагов на процессор было бы лучше, чем O( | Другой открытой проблемой является вопрос о том, существует ли рандомизированная реализация ID-консенсуса с использованием мультирайтерных мультиридерных регистров, которая была бы устойчивой к промежуточному сопернику и у которой ожидаемое число шагов на процессор было бы лучше, чем <math>O(log^2 \; n)</math>. В частности, возможно ли константное время выполнения? Ауманн в продолжении этой работы смог улучшить ожидаемое время выполнения на процесс до <math>O(log \; n)</math> [4]. Однако, насколько известно авторам статьи, дальнейших улучшений не было. | ||
Третьей нерешенной задачей является сокращение времени, необходимого нахождения бинарного консенсуса против сильного соперника с однорайтерными мультиридерными регистрами. Самый быстрый из известных рандомизированных алгоритмов в этом сценарии требует O( | Третьей нерешенной задачей является сокращение времени, необходимого нахождения бинарного консенсуса против сильного соперника с однорайтерными мультиридерными регистрами. Самый быстрый из известных рандомизированных алгоритмов в этом сценарии требует <math>O(n \; log^2 \; n)</math> шагов на процессор [2]. Тривиальная нижняя граница количества шагов на процессор при использовании однорайтерных регистров равна <math>\Omega(n)</math>. Тем не менее, разрыв с <math>O(log^2 \; n)</math> все еще остается проблемой. | ||
Наконец, последней открытой темой является ликвидация разрыва в суммарном объеме работы, необходимой для решения задачи о консенсусе с использованием однорайтерных одноридерных регистров против забывчивого соперника. Ауманн и Капах-Леви описали алгоритмы для этого сценария, которые требуют O( | Наконец, последней открытой темой является ликвидация разрыва в суммарном объеме работы, необходимой для решения задачи о консенсусе с использованием однорайтерных одноридерных регистров против забывчивого соперника. Ауманн и Капах-Леви описали алгоритмы для этого сценария, которые требуют <math>O(n \; log \; n \; exp(2 \sqrt{ln \; n \; ln(c \; log \; n \; log^* \; n)}</math> ожидаемой суммарной работы для некоторой постоянной <math>c</math> [5]. В частности, суммарный объем работы меньше <math>O(n^{1 + \epsilon})</math> для любого <math>\epsilon > 0</math>. Тривиальная нижняя граница суммарной работы равна <math>\Omega(n)</math>, но разрыв остается. | ||
== См. также == | == См. также == | ||