4824
правки
Рандомизация в распределенных вычислениях: различия между версиями
Материал из WEGA
Рандомизация в распределенных вычислениях (посмотреть исходный код)
Версия от 12:18, 29 июня 2025
, 29 июнь→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 5 промежуточных версий этого же участника) | |||
| Строка 37: | Строка 37: | ||
'''Соперник''' | '''Соперник''' | ||
Решение описанных выше задач осложняется тем, что программист слабо контролирует скорость выполнения у отдельных процессоров. Чтобы смоделировать этот факт, предполагается, что расписание работы процессоров выбирает | Решение описанных выше задач осложняется тем, что программист слабо контролирует скорость выполнения у отдельных процессоров. Чтобы смоделировать этот факт, предполагается, что расписание работы процессоров выбирает соперник. Хорошо известно, что не существует детерминированного алгоритма, способного решить задачу бинарного или ID-консенсуса в этой модели с соперником, если число процессоров больше 1 [6, 7]. Поэтому для решения этой задачи исследователи обратились к использованию рандомизированных алгоритмов [1]. Такие алгоритмы имеют доступ к результатам случайного подбрасывания монет. Для рандомизированных алгоритмов рассматриваются три типа соперников. Предполагается, что ''сильный соперник'' знает результат подбрасывания монеты сразу после того, как она подброшена, и может соответствующим образом изменить свое расписание. ''Забывчивый соперник'' должен зафиксировать расписание до того, как будет подброшена какая-либо из монет. ''Промежуточному сопернику'' не разрешается видеть результат подбрасывания монеты до тех пор, пока какой-либо процесс не сделает выбор на основе этого подбрасывания. В частности, процесс может подбросить монету и записать результат в глобальный регистр, но промежуточный соперник не будет знать результат подбрасывания монеты, пока какой-либо процесс не прочитает значение, записанное в регистре. | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1. Предполагая существование мультирайтерных мультиридерных регистров, существует рандомизированный алгоритм решения задачи | '''Теорема 1. Предполагая существование мультирайтерных мультиридерных регистров, существует рандомизированный алгоритм решения задачи бинарного консенсуса против промежуточного соперника с O(1) ожидаемых шагов на процессор.''' | ||
Теорема 2. Предполагая существование мультирайтерных мультиридерных регистров, существует рандомизированный алгоритм решения задачи ID-консенсуса против промежуточного соперника с O( | '''Теорема 2. Предполагая существование мультирайтерных мультиридерных регистров, существует рандомизированный алгоритм решения задачи ID-консенсуса против промежуточного соперника с <math>O(log^2 \; n)</math> ожидаемых шагов на процессор.''' | ||
Оба этих результата предполагают, что каждый процессор имеет уникальный идентификатор. До получения этого результата самый быстрый из известных рандомизированных алгоритмов для | Оба этих результата предполагают, что каждый процессор имеет уникальный идентификатор. До получения этого результата самый быстрый из известных рандомизированных алгоритмов для бинарного консенсуса использовал однорайтерные мультиридерные регистры, был устойчив относительно сильного соперника и требовал <math>O(n \; log^2 \; n)</math> шагов на процессор [2]. Таким образом, вышеуказанные улучшения получены за счет ослабления соперника и усиления модели системы по сравнению с [2]. | ||
== Применение == | == Применение == | ||
Бинарный консенсус является одной из наиболее фундаментальных проблем в распределенных вычислениях. Примером ее важности может служить следующий результат, полученный Херлихи [8]. Если абстрактный тип данных X вместе с общей памятью являются достаточно мощными для реализации консенсуса без ожидания, то X вместе с общей памятью является достаточно мощным для реализации без ожидания любой другой структуры данных Y. Таким образом, используя этот результат, можно создать версию любой структуры данных без ожидания, используя в качестве | Бинарный консенсус является одной из наиболее фундаментальных проблем в распределенных вычислениях. Примером ее важности может служить следующий результат, полученный Херлихи [8]. Если абстрактный тип данных X вместе с общей памятью являются достаточно мощными для реализации консенсуса без ожидания, то X вместе с общей памятью является достаточно мощным для реализации без ожидания любой другой структуры данных Y. Таким образом, используя этот результат, можно создать версию любой структуры данных без ожидания, используя в качестве строительных блоков только мультирайтерные мультиридерные регистры без ожидания. | ||
| Строка 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>, но разрыв остается. | ||
== См. также == | == См. также == | ||
