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

Материал из WEGA
Перейти к навигации Перейти к поиску

Ключевые слова и синонимы

Соглашение (Agreement); византийское соглашение (византийский консенсус) (Byzantine Agreement)

Постановка задачи

Эта задача связана с использованием примитива мультирайтерного и мультиридерного регистра в модели с общей памятью для разработки быстрой, не требующей ожидания реализации консенсуса. Далее приводятся подробные описания каждого из этих терминов.


Задачи о консенсусе

Имеется n процессоров; цель заключается в разработке распределенных алгоритмов для решения следующих двух задач о консенсусе для этих процессоров.


Задача 1 (бинарный консенсус)

Дано: процессор [math]\displaystyle{ i }[/math] имеет входной бит [math]\displaystyle{ b_i }[/math].

Результат: каждый процессор [math]\displaystyle{ i }[/math] имеет выходной бит [math]\displaystyle{ b'_i }[/math], такой, что: 1) все выходные биты [math]\displaystyle{ b_i' }[/math] равны одному и тому же значению [math]\displaystyle{ v }[/math]; и 2) [math]\displaystyle{ v = b_i }[/math] для некоторого процессора [math]\displaystyle{ i }[/math].


Задача 2 (консенсус идентификаторов, ID-консенсус)

Дано: процессор [math]\displaystyle{ i }[/math] имеет уникальный идентификатор [math]\displaystyle{ u_i }[/math].

Результат: каждый процессор [math]\displaystyle{ i }[/math] имеет выходное значение [math]\displaystyle{ u'_i }[/math], такое, что: 1) все выходные значения [math]\displaystyle{ u_i' }[/math] равны одному и тому же значению [math]\displaystyle{ u }[/math]; и 2) [math]\displaystyle{ u = u_i }[/math] для некоторого процессора [math]\displaystyle{ i }[/math].


Без ожидания

Этот результат опирается на обширную предшествующую работу по модели параллельных вычислений с общей памятью. Типы совместно используемых объектов включают структуры данных, такие как регистры чтения/записи, и примитивы синхронизации, такие как «проверка и установка». Совместно используемый объект называется объектом без ожидания, если он гарантирует, что каждый вызов объекта получает ответ за конечное время, даже если некоторые или все остальные процессоры в системе претерпевают сбой. В этой задаче предполагается существование регистров без ожидания, а целью является создание быстрого, не требующего ожидания алгоритма для решения задачи о консенсусе. В дальнейшем изложении «реализации без ожидания» будут называться просто «реализациями», т. е. уточнение «без ожидания» будет опущено.


Мультирайтерный мультиридерный регистр

Многие результаты, полученные в прошлом при решении задачи о консенсусе в модели с общей памятью, предполагают существование однорайтерного мультиридерного регистра. Для такого регистра существует один клиент-писатель и несколько клиентов-читателей. К сожалению, легко показать, что сложность на шаг процессора при любой реализации консенсуса на основе однорайтерных мультиридерных регистров будет по меньшей мере линейной от числа процессоров. Таким образом, для достижения эффективной по времени реализации консенсуса необходимо использовать более мощный примитив мультирайтерного мультиридерного регистра. Мультирайтерный мультиридерный регистр предполагает наличие у него нескольких клиентов-писателей и клиентов-читателей. Хорошо известно, что такой регистр можно реализовать в модели общей памяти.


Соперник

Решение описанных выше задач осложняется тем, что программист слабо контролирует скорость выполнения у отдельных процессоров. Чтобы смоделировать этот факт, предполагается, что расписание работы процессоров выбирает противник. Хорошо известно, что не существует детерминированного алгоритма, способного решить задачу бинарного или ID-консенсуса в этой модели с с соперником, если число процессоров больше 1 [6, 7]. Поэтому для решения этой задачи исследователи обратились к использованию рандомизированных алгоритмов [1]. Такие алгоритмы имеют доступ к случайным подбрасываниям монет. Для рандомизированных алгоритмов рассматриваются три типа соперников. Предполагается, что сильный соперник знает результат подбрасывания монеты сразу после того, как она подброшена, и может соответствующим образом изменить свое расписание. Забывчивый соперник должен зафиксировать расписание до того, как будет подброшена какая-либо из монет. Промежуточному сопернику не разрешается видеть результат подбрасывания монеты до тех пор, пока какой-либо процесс не сделает выбор на основе этого подбрасывания. В частности, процесс может подбросить монету и записать результат в глобальный регистр, но промежуточный соперник не будет знать результат подбрасывания монеты, пока какой-либо процесс не прочитает значение, записанное в регистре.

Основные результаты

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


Теорема 2. Предполагая существование мультирайтерных мультиридерных регистров, существует рандомизированный алгоритм решения задачи ID-консенсуса против промежуточного соперника с [math]\displaystyle{ O(log^2 \; n) }[/math] ожидаемых шагов на процессор.


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

Применение

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


Бинарный консенсус находит практическое применение во многих областях, включая управление базами данных, многопроцессорные вычисления, диагностику неисправностей и критически важные системы, такие как управление полетами. Книга Линч содержит обширное обсуждение некоторых из этих областей применения [9].

Открытые вопросы

Данный результат оставляет открытыми несколько вопросов. Во-первых, остается нерешенным вопрос о количестве шагов на процесс, необходимых для достижения рандомизированного консенсуса с использованием мультирайтерных мультиридерных регистров против сильного соперника. Недавний результат Аттии и Сенсор демонстрирует нижнюю границу Q(n2) суммарного количества шагов для всех процессоров с мультирайтерными мультиридерными регистрами (подразумевая Q(n) шагов на процесс) [ ]. Авторы также доказали соответствующую верхнюю границу O(n2) суммарного количества шагов. Однако вопрос о том, как преодолеть разрыв в количестве шагов на каждый процесс, остается открытым.


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


Третьей нерешенной задачей является сокращение времени, необходимого нахождения бинарного консенсуса против сильного соперника с однорайтерными мультиридерными регистрами. Самый быстрый из известных рандомизированных алгоритмов в этом сценарии требует O(nlog2 n) шагов на процессор [ ]. Тривиальная нижняя граница количества шагов на процессор при использовании однорайтерных регистров равна Q(n). Тем не менее, разрыв с O(log2 n) все еще остается проблемой.


Наконец, последней открытой темой является ликвидация разрыва в суммарном объеме работы, необходимой для решения задачи о консенсусе с использованием однорайтерных одноридерных регистров против забывчивого соперника. Ауманн и Капах-Леви описали алгоритмы для этого сценария, которые требуют O(nlog nexp(2ln nln(clog "log* n) ожидаемой суммарной работы для некоторой постоянной c [ ]. В частности, суммарный объем работы меньше O(n1+€) для любого e > 0. Тривиальная нижняя граница суммарной работы равна Q{n), но разрыв остается открытым.

См. также

Литература

1. Aspnes, J.: Randomized protocols for asynchronous consensus. Distrib.Comput. 16(2-3), 165-175 (2003)

2. Aspnes, J., Waarts, O.: Randomized consensus in expected o(n log2 n) operations per processor. In: Proceedings of the 33rd Symposium on Foundations of Computer Science. 24-26 October 1992, pp. 137-146. IEEE Computer Society, Pittsburgh (1992)

3. Attiya, H., Censor, K.: Tight bounds for asynchronous randomized consensus. In: Proceedings of the Symposium on the The ory of Computation. San Diego, 11-13 June 2007 ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) (2007)

4. Aumann, Y.: Efficient asynchronous consensus with the weak adversary scheduler. In: Symposium on Principles of Distrib. Comput.(PODC) Santa Barbara, 21-24 August 1997, pp. 209-218. ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) (1997)

5. Aumann, Y., Kapach-Levy, A.: Cooperative sharing and asynchronous consensus using single-reader/single-writer registers. In: Proceedings of 10th Annual ACM-SIAM Symposium of Discrete Algorithms (SODA) Baltimore, 17-19 January 1999, pp. 61-70. Society for Industrial and Applied Mathematics (SIAM) (1999)

6. Dolev, D., Dwork, C., Stockmeyer, L.: On the minimal synchronism needed for distributed consensus. J. ACM (JACM) 34(1), 77-97(1987)

7. Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. In: Proceedings of the 2nd ACM SIGACT-SIGMOD Symposium on Principles of Database System (PODS) Atlante, 21-23 March, pp. 1 -7. Association for Computational Machinery (ACM) (1983)

8. Herlihy, M.: Wait-free synchronization. ACM Trans. Programm. Lang. Syst. 13(1), 124-149 (1991)

9. Lynch, N.: Distributed Algorithms. Morgan Kaufmann, San Mateo(1996)

Источник — http://pco.iis.nsk.su/wega/index.php?title=Рандомизация_в_распределенных_вычислениях&oldid=16002