Топологический подход в распределенных вычислениях
Ключевые слова и синонимы
Переименование без ожидания (Wait-free renaming)
Постановка задачи
Применение методов комбинаторной и алгебраической топологии позволило успешно решить ряд проблем в области распределенных вычислений. В 1993 году три независимые команды [3, 15, 17], используя различные способы обобщения классической теоретико-графовой модели распределенных вычислений, смогли решить задачу согласования множеств, которая долгое время не поддавалась стандартным подходам. Позднее, в 2004 году, журнальные статьи Херлихи и Шавита [15] и Сакса и Захароглу [17] были удостоены престижной премии Гёделя. Ниже описывается подход, примененный в статье Херлихи и Шавита, в которой впервые была установлена связь между алгебраической и комбинаторной топологией и распределенными вычислениями.
Первые исследователи этой области, такие как Биран, Моран и Закс [2], использовали теоретико-графовую нотацию для моделирования неопределенности и смогли сформулировать определенные нижние границы в терминах связности графов. Однако у этого подхода есть свои ограничения. В частности, в его рамках трудно учесть влияние множественных отказов или проанализировать проблемы разрешимости, отличные от задачи о консенсусе.
Комбинаторная топология обобщает понятие графа до понятия симплициального комплекса – структуры, которая уже более века активно изучается в «большой» математике. Одним из наиболее интересующих топологов свойств было отсутствие в симплициальном комплексе «дыр» ниже определенной размерности k – свойство, известное как k-связность. Нижние границы, которые ранее выражались в терминах связности графов, можно обобщить, переформулировав их в терминах k-связности симплициальных комплексов. Используя это представление, удалось разрешить некоторые открытые вопросы (такие как согласование k множеств или переименование), поставить и решить несколько новых задач ([13]), а также унифицировать ряд разрозненных результатов и моделей [14].
Основные результаты
Вершина [math]\displaystyle{ \vec{v} }[/math] представляет собой точку в Евклидовом пространстве высокой размерности. Вершины [math]\displaystyle{ \vec{v_0}, ..., \vec{v_n} }[/math] аффинно независимы, если [math]\displaystyle{ \vec{v_1} - \vec{v_0}, ..., \vec{v_n} - \vec{v_{n - 1}} }[/math] линейно независимы. n-мерный симплекс (или n-симплекс) [math]\displaystyle{ S^n = (\vec{s_0}, ..., \vec{s_n}) }[/math] – это выпуклая оболочка множества n + 1 аффинно независимых вершин. Например, 0-симплекс – это вершина, 1-симплекс – отрезок прямой, 2-симплекс – сплошной треугольник, а 3-симплекс – сплошной тетраэдр. Там, где это удобно, надстрочные знаки обозначают размерности симплексов. Считается, что симплекс [math]\displaystyle{ \vec{s_0}, ..., \vec{s_n} }[/math] охватывает [math]\displaystyle{ S^n }[/math]. Согласно условию, симплекс размерности d < 0 является пустым.
Симплициальный комплекс (или комплекс) – это множество симплексов, замкнутых относительно операций вложения и пересечения. Размерность комплекса равна наибольшей размерности любого из его симплексов. [math]\displaystyle{ \mathcal{L} }[/math] является подкомплексом [math]\displaystyle{ \mathcal{K} }[/math], если каждый симплекс из [math]\displaystyle{ \mathcal{L} }[/math] является симплексом из [math]\displaystyle{ \mathcal{K} }[/math]. Отображение [math]\displaystyle{ \mu : \mathcal{K} \to \mathcal{L} }[/math], переводящее вершины в вершины, является симплициальным, если оно также порождает отображение симплексов в симплексы.
Определение 1. Комплекс [math]\displaystyle{ \mathcal{K} }[/math] является k-связным, если каждое непрерывное отображение k-сферы на [math]\displaystyle{ \mathcal{K} }[/math] может быть расширено до непрерывного отображения (k + 1)-диска. Согласно условию, комплекс является (-l)-связным тогда и только тогда, когда он непуст, и каждый комплекс k-связен при k < - 1.
Комплекс 0-связен, если он является связным в теоретико-графовом смысле; комплекс k-связен, если он не имеет дыр в размерности k или более низких. Определение k-связности может показаться сложным, но, к счастью, рассуждения о связности можно проводить комбинаторно, используя следующее элементарное следствие из последовательности Майера-Вьеториса.
Теорема 2. Если [math]\displaystyle{ \mathcal{K} }[/math] и [math]\displaystyle{ \mathcal{L} }[/math] – комплексы, такие, что [math]\displaystyle{ \mathcal{K} }[/math] и [math]\displaystyle{ \mathcal{L} }[/math] k-связны, а [math]\displaystyle{ \mathcal{K} \cap \mathcal{L} }[/math] (k-1)-связен, то [math]\displaystyle{ \mathcal{K} \cup \mathcal{L} }[/math] k-связен.
Эта теорема, а также замечание о том, что любой непустой симплекс является k-связным для всех k, позволяет рассуждать о связности комплекса индуктивно в терминах связности его компонентов.
Множество n + 1 последовательных процессов взаимодействует между собой, посылая друг другу сообщения или выполняя операции над общими объектами. В любой момент процесс может претерпеть сбой: он останавливается и больше не делает никаких шагов. Существует ограничение f на количество процессов, которые могут окончиться сбоями. Разные модели различаются по своим предположениям о времени. На одном конце спектра находится синхронная модель, в которой вычисления производятся в виде последовательности раундов. В каждом раунде процесс отправляет сообщения другим процессам, получает сообщения, отправленные ему другими процессами в этом раунде, и меняет свое состояние. (Либо не обменивается сообщениями, а выполняет операции над общими объектами). Все процессы выполняют шаги с одинаковой скоростью, все сообщения доставляются за одно и то же время. На противоположном конце располагается асинхронная модель, в которой нет ограничений на время, которое может пройти между шагами процесса, и на время, которое может потребоваться для доставки сообщения. Между этими крайностями находится полусинхронная модель, в которой время выполнения шагов процесса и время доставки сообщений могут меняться, но ограничены постоянными верхней и нижней границами. Доказательство нижней границы в любой из этих моделей требует глубокого понимания глобальных состояний, которые могут возникнуть в ходе выполнения протокола, и того, как эти глобальные состояния связаны между собой.
Каждый процесс начинает с входного значения, взятого из множества V, а затем выполняет детерминированный протокол, в котором он неоднократно получает одно или несколько сообщений, изменяет свое локальное состояние и отправляет одно или несколько сообщений. После конечного числа шагов каждый процесс выбирает значение решения и останавливается.
В задаче согласования k множеств [5] процессы должны: (1) выбрать значение решения после конечного числа шагов, (2) выбрать в качестве значения решения некоторое входное значение процесса и (3) коллективно выбрать не более k различных значений решения. При k = 1 эта задача обычно называется задачей о консенсусе [16].
Между топологическими моделями и вычислениями имеется следующая связь. Начальное локальное состояние процесса P моделируется как вершина [math]\displaystyle{ \vec{v} = \langle P, v \rangle }[/math], помеченная идентификатором процесса P и начальным значением v. Начальное глобальное состояние моделируется как n-симплекс [math]\displaystyle{ S^n = ( \langle P_0, v_0 \rangle ,..., \langle P_n, v_n \rangle ) }[/math], где все [math]\displaystyle{ P_i }[/math] различны. Терм [math]\displaystyle{ ids(S^n) }[/math] обозначает множество идентификаторов процессов, связанных с [math]\displaystyle{ S^n }[/math], а [math]\displaystyle{ vals(S^n) }[/math] – множество значений. Множество всех возможных начальных глобальных состояний образует комплекс, называемый входным комплексом.
Любой протокол имеет связанный с ним протокольный комплекс P, определяемый следующим образом. Каждая вершина помечена идентификатором процесса и возможным локальным состоянием этого процесса. Множество вершин hP0; v0i - - - h Pd; vdi охватывает симплекс P тогда и только тогда, когда существует некоторое выполнение протокола, при котором P0;::::; Pd завершают его с соответствующими локальными состояниями v0... ; vd. Таким образом, каждый симплекс соответствует классу эквивалентности выполнений, которые «выглядят одинаково» для процессов в его вершинах. Термин P(Sm) обозначает подкомплекс P, соответствующий исполнениям, в которых участвуют только процессы из ids(Sm) (остальные завершаются сбоями, не отправив ни одного сообщения). Если m < n - f, то таких исполнений не существует, и подкомплекс P(Sm) пуст. Структура протокольного комплекса P зависит как от протокола, так и от временных характеристик и характеристик отказов модели. Часто P обозначает и протокол, и его комплекс; различие между ними проводится, исходя из контекста.
Протокол решает задачу о согласовании k множеств, если существует симплициальное отображение 8, называемое картой решений, которое отображает вершины P на значения в V таким образом, что если p € T(S"), то S(p) 2 vals(Sn), и S отображает вершины любого данного симплекса в P (Sn) на не более чем k различных значений.
Применение
Задача переименования является ключевым инструментом для понимания возможностей различных асинхронных моделей вычислений.
Открытые вопросы
Определение всех возможностей топологического подхода для доказательства нижних границ остается нерешенной задачей.
См. также
Литература
Пожалуй, первой работой, в которой исследовалась разрешимость распределенных задач, была основополагающая статья Фишера, Линч и Патерсона 1985 года [ ], в которой было показано, что консенсус, считавшийся в то время абстракцией задачи внесения данных в базу данных, не имеет 1-устойчивого решения с передачей сообщений. Внимание исследователей также привлекли другие задачи, такие как переименование [1, 12, 15] и согласование множеств [3, 5, 12, 10, 15, 17].
В 1988 году Биран, Моран и Закс [2] представили теоретико-графовую характеризацию проблем разрешимости, которые могут быть решены при наличии одного сбоя в системе передачи сообщений. Этот результат не был существенно улучшен до 1993 года, когда трем независимым исследовательским группам удалось применить комбинаторные методы к протоколам, допускающим задержки более чем у одного процессора: Боровски и Гафни [3], Сакс и Захароглу [ ], Херлихи и Шавит [15].
Позже Херлихи и Райсбаум использовали теорию гомологий для получения дальнейших результатов о невозможности согласования множеств и для объединения различных известных результатов о невозможности в терминах теории цепных карт и цепных комплексов [12], используя ту же симплициальную модель.
Биран, Моран и Закс [ ] представили первый результат о разрешимости задач на принятие решений, показав, что эти задачи разрешимы в 1-устойчивой модели передачи сообщений. Гафни и Кутсупиас [7] первыми сделали важное замечание о том, что задача о стягиваемости может быть использована для доказательства неразрешимости задач, и предложили стратегию сведения конкретной не требующей ожидания задачи для трех процессов к задаче о стягиваемости. Херлихи и Райсбаум [ ] предоставили более обширную коллекцию результатов о разрешимости.
Боровски и Гафни [ ] определили модель итертативного моментального снимка, имеющую рекурсивную структуру. Чаудхури, Херлихи, Линч и Таттл [ ] предложили индуктивное построение синхронной модели, и хотя полученный «бермудский треугольник» визуально привлекателен и представляет собой элегантную комбинацию методов доказательства из литературы, формальное описание этого построения выглядит весьма сложным. В этом смысле формальное представление более поздних построений оказалось значительно лаконичнее.
Более поздние работы в этой области включают результаты разделения [8] и нижние границы сложности [9].
1. Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuk, R.: Renaming in an asynchronous environment. J. ACM 37(3), 524-548 (1990)
2. Biran, O., Moran, S., Zaks, S.: A combinatorial characterization of the distributed 1-solvable tasks. J. Algorithms 11(3), 420-440 (1990)
3. Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: Proceedings of the 25th ACM Symposium on Theory of Computing, May 1993
4. Chaudhuri, S., Herlihy, M., Lynch, N.A., Tuttle, M.R.: Tight bounds for k-set agreement. J. ACM 47(5), 912-943 (2000)
5. Chaudhuri, S.: More choices allow more faults: Set consensus problems in totally asynchronous systems. Inf. Comp. 105(1), 132-158(1993) A preliminary version appeared in ACM PODC 1990
6. Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty processor. J. ACM 32(2), 374-382(1985)
7. Gafni, E., Koutsoupias, E.: Three-processor tasks are undecidable. SIAM J. Comput. 28(3), 970-983 (1999)
8. Gafni, E., Rajsbaum, S., Herlihy, M.: Subconsensus tasks: Renaming is weaker than set agreement. In: Lecture Notes in Computer Science, pp. 329-338. (2006)
9. Guerraoui, R., Herlihy, M., Pochon, B.: A topological treatment of early-deciding set-agreement. In: OPODIS, pp. 20-35, (2006)
10. Herlihy, M., Rajsbaum, S.: Set consensus using arbitrary objects. In: Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 324-333, August (1994)
11. Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks (extended abstract). In: STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp. 589-598. ACM Press, New York (1997)
12. Herlihy, M., Rajsbaum, S.: Algebraic spans. Math. Struct. Comput. Sci. 10(4), 549-573 (2000)
13. Herlihy, M., Rajsbaum, S.: A classification of wait-free loop agreement tasks. Theor. Comput. Sci. 291 (1), 55-77 (2003)
14. Herlihy, M., Rajsbaum, S., Tuttle, M.R.: Unifying synchronous and asynchronous message-passing models. In: PODC '98: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, pp. 133-142. ACM Press, New York (1998)
15. Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858-923 (1999)
16. Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27(2), 228-234 (1980)
17. Saks, M., Zaharoglou, F.: Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput. 29(5),1449-1483(2000)
