4817
правок
Рандомизация в распределенных вычислениях: различия между версиями
Перейти к навигации
Перейти к поиску
м
Рандомизация в распределенных вычислениях (посмотреть исходный код)
Версия от 05:00, 29 июня 2025
, 29 июнь→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
'''Задача 1 (бинарный консенсус)''' | '''Задача 1 (бинарный консенсус)''' | ||
Дано: процессор i имеет входной бит | Дано: процессор <math>i</math> имеет входной бит <math>b_i</math>. | ||
Результат: каждый процессор i имеет выходной бит | Результат: каждый процессор <math>i</math> имеет выходной бит <math>b'_i</math>, такой, что: 1) все выходные биты <math>b_i'</math> равны одному и тому же значению <math>v</math>; и 2) <math>v = b_i</math> для некоторого процессора <math>i</math>. | ||
'''Задача 2 (консенсус идентификаторов, ID-консенсус)''' | '''Задача 2 (консенсус идентификаторов, ID-консенсус)''' | ||
Дано: процессор i имеет уникальный идентификатор | Дано: процессор <math>i</math> имеет уникальный идентификатор <math>u_i</math>. | ||
Результат: каждый процессор i имеет выходное значение | Результат: каждый процессор <math>i</math> имеет выходное значение <math>u'_i</math>, такое, что: 1) все выходные значения <math>u_i'</math> равны одному и тому же значению <math>u</math>; и 2) <math>u = u_i</math> для некоторого процессора <math>i</math>. | ||
'''Без ожидания''' | '''Без ожидания''' | ||
Этот результат опирается на обширную предшествующую работу по модели параллельных вычислений с общей памятью. Типы совместно используемых объектов включают структуры данных, такие как регистры чтения/записи, и примитивы синхронизации, такие как «проверка и установка». Совместно используемый объект называется объектом без ожидания, если он гарантирует, что каждый вызов объекта получает ответ за конечное время, даже если некоторые или все остальные процессоры в системе претерпевают сбой. В этой задаче предполагается существование регистров без ожидания, а целью является создание быстрого, не требующего ожидания алгоритма для решения задачи о консенсусе. В дальнейшем изложении «реализации без ожидания» будут называться просто «реализациями», т. е. уточнение «без ожидания» будет опущено. | Этот результат опирается на обширную предшествующую работу по модели параллельных вычислений с общей памятью. Типы совместно используемых объектов включают структуры данных, такие как регистры чтения/записи, и примитивы синхронизации, такие как «проверка и установка». Совместно используемый объект называется ''объектом без ожидания'', если он гарантирует, что каждый вызов объекта получает ответ за конечное время, даже если некоторые или все остальные процессоры в системе претерпевают сбой. В этой задаче предполагается существование регистров без ожидания, а целью является создание быстрого, не требующего ожидания алгоритма для решения задачи о консенсусе. В дальнейшем изложении «реализации без ожидания» будут называться просто «реализациями», т. е. уточнение «без ожидания» будет опущено. | ||
| Строка 37: | Строка 37: | ||
'''Соперник''' | '''Соперник''' | ||
Решение описанных выше задач осложняется тем, что программист слабо контролирует скорость выполнения у отдельных процессоров. Чтобы смоделировать этот факт, предполагается, что расписание работы процессоров выбирает противник. Хорошо известно, что не существует детерминированного алгоритма, способного решить задачу бинарного или ID-консенсуса в этой модели с с соперником, если число процессоров больше 1 [6, 7]. Поэтому для решения этой задачи исследователи обратились к использованию рандомизированных алгоритмов [1]. Такие алгоритмы имеют доступ к случайным подбрасываниям монет. Для рандомизированных алгоритмов рассматриваются три типа соперников. Предполагается, что сильный соперник знает результат подбрасывания монеты сразу после того, как она подброшена, и может соответствующим образом изменить свое расписание. Забывчивый соперник должен зафиксировать расписание до того, как будет подброшена какая-либо из монет. Промежуточному сопернику не разрешается видеть результат подбрасывания монеты до тех пор, пока какой-либо процесс не сделает выбор на основе этого подбрасывания. В частности, процесс может подбросить монету и записать результат в глобальный регистр, но промежуточный соперник не будет знать результат подбрасывания монеты, пока какой-либо процесс не прочитает значение, записанное в регистре. | Решение описанных выше задач осложняется тем, что программист слабо контролирует скорость выполнения у отдельных процессоров. Чтобы смоделировать этот факт, предполагается, что расписание работы процессоров выбирает противник. Хорошо известно, что не существует детерминированного алгоритма, способного решить задачу бинарного или ID-консенсуса в этой модели с с соперником, если число процессоров больше 1 [6, 7]. Поэтому для решения этой задачи исследователи обратились к использованию рандомизированных алгоритмов [1]. Такие алгоритмы имеют доступ к случайным подбрасываниям монет. Для рандомизированных алгоритмов рассматриваются три типа соперников. Предполагается, что ''сильный соперник'' знает результат подбрасывания монеты сразу после того, как она подброшена, и может соответствующим образом изменить свое расписание. ''Забывчивый соперник'' должен зафиксировать расписание до того, как будет подброшена какая-либо из монет. ''Промежуточному сопернику'' не разрешается видеть результат подбрасывания монеты до тех пор, пока какой-либо процесс не сделает выбор на основе этого подбрасывания. В частности, процесс может подбросить монету и записать результат в глобальный регистр, но промежуточный соперник не будет знать результат подбрасывания монеты, пока какой-либо процесс не прочитает значение, записанное в регистре. | ||
== Основные результаты == | == Основные результаты == | ||
Теорема 1. Предполагая существование мультирайтерных мультиридерных регистров, существует рандомизированный алгоритм решения задачи двоичного консенсуса против промежуточного соперника с O(1) ожидаемых шагов на процессор. | Теорема 1. Предполагая существование мультирайтерных мультиридерных регистров, существует рандомизированный алгоритм решения задачи двоичного консенсуса против промежуточного соперника с O(1) ожидаемых шагов на процессор. | ||