4824
правки
Топологический подход в распределенных вычислениях: различия между версиями
Материал из WEGA
Топологический подход в распределенных вычислениях (посмотреть исходный код)
Версия от 15:35, 19 февраля 2025
, 19 февраль→Литература
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Переименование без ожидания (''Wait-free renaming'') == Постановка задачи == Применение методов комбинаторной и алгебраической топологии позволило успешно решить ряд проблем в области распределенных вычислений. В 1993 году три незави...») |
Irina (обсуждение | вклад) м (→Литература) |
||
| (не показано 11 промежуточных версий этого же участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Применение методов комбинаторной и алгебраической топологии позволило успешно решить ряд | Применение методов комбинаторной и алгебраической топологии позволило успешно решить ряд задач в области распределенных вычислений. В 1993 году три независимые команды [3, 15, 17], используя различные способы обобщения классической теоретико-графовой модели распределенных вычислений, смогли решить ''задачу согласования множеств'', которая долгое время не поддавалась стандартным подходам. Позднее, в 2004 году, журнальные статьи Херлихи и Шавита [15] и Сакса и Захароглу [17] были удостоены престижной премии Гёделя. Ниже описывается подход, примененный в статье Херлихи и Шавита, в которой впервые была установлена связь между алгебраической и комбинаторной топологией и распределенными вычислениями. | ||
Первые исследователи этой области, такие как Биран, Моран и Закс [2], использовали теоретико-графовую нотацию для моделирования неопределенности и смогли сформулировать определенные нижние границы в терминах связности графов. Однако у этого подхода есть | Первые исследователи этой области, такие как Биран, Моран и Закс [2], использовали теоретико-графовую нотацию для моделирования неопределенности и смогли сформулировать определенные нижние границы в терминах связности графов. Однако у этого подхода есть некоторые ограничения. В частности, в его рамках трудно учесть влияние множественных отказов или проанализировать проблемы разрешимости, отличные от задачи о консенсусе. | ||
Комбинаторная топология обобщает понятие графа до понятия симплициального комплекса – структуры, которая уже более века активно изучается в «большой» математике. Одним из наиболее интересующих топологов свойств было отсутствие в симплициальном комплексе «дыр» ниже определенной размерности k – свойство, известное как k-связность. Нижние границы, которые ранее выражались в терминах связности графов, можно обобщить, переформулировав их в терминах k-связности симплициальных комплексов. Используя это представление, удалось разрешить некоторые открытые вопросы (такие как [[Согласование множеств|согласование k множеств]] или [[переименование]]), поставить и решить несколько новых задач ([ ]), а также унифицировать ряд разрозненных результатов и моделей [14]. | Комбинаторная топология обобщает понятие графа до понятия ''симплициального комплекса'' – структуры, которая уже более века активно изучается в «большой» математике. Одним из наиболее интересующих топологов свойств было отсутствие в симплициальном комплексе «дыр» ниже определенной размерности k – свойство, известное как ''k-связность''. Нижние границы, которые ранее выражались в терминах связности графов, можно обобщить, переформулировав их в терминах k-связности симплициальных комплексов. Используя это представление, удалось разрешить некоторые открытые вопросы (такие как [[Согласование множеств|согласование k множеств]] или [[переименование]]), поставить и решить несколько новых задач ([13]), а также унифицировать ряд разрозненных результатов и моделей [14]. | ||
== Основные результаты == | == Основные результаты == | ||
Вершина v представляет собой точку в Евклидовом пространстве высокой размерности. Вершины | ''Вершина'' <math>\vec{v}</math> представляет собой точку в Евклидовом пространстве высокой размерности. Вершины <math>\vec{v_0}, ..., \vec{v_n}</math> ''аффинно независимы'', если <math>\vec{v_1} - \vec{v_0}, ..., \vec{v_n} - \vec{v_{n - 1}}</math> линейно независимы. ''n-мерный симплекс'' (или ''n-симплекс'') <math>S^n = (\vec{s_0}, ..., \vec{s_n})</math> – это выпуклая оболочка множества n + 1 аффинно независимых вершин. Например, 0-симплекс – это вершина, 1-симплекс – отрезок прямой, 2-симплекс – сплошной треугольник, а 3-симплекс – сплошной тетраэдр. Там, где это удобно, надстрочные знаки обозначают размерности симплексов. Мы говорим, что <math>\vec{s_0}, ..., \vec{s_n}</math> ''охватывают'' <math>S^n</math>. Согласно условию, симплекс размерности d < 0 является пустым. | ||
''Симплициальный комплекс'' (или ''комплекс'') представляет собой множество симплексов, замкнутое относительно операций включения и пересечения. ''Размерность'' комплекса равна наибольшей размерности любого из его симплексов. <math>\mathcal{L}</math> является ''подкомплексом'' <math>\mathcal{K}</math>, если каждый симплекс из <math>\mathcal{L}</math> является симплексом из <math>\mathcal{K}</math>. Отображение <math>\mu : \mathcal{K} \to \mathcal{L}</math>, переводящее вершины в вершины, является ''симплициальным'', если оно также порождает отображение симплексов в симплексы. | |||
'''Определение 1'''. Комплекс <math>\mathcal{K}</math> является ''k-связным'', если каждое непрерывное отображение k-сферы на <math>\mathcal{K}</math> может быть расширено до непрерывного отображения (k + 1)-диска. Согласно условию, комплекс является ''(-1)-связным'' тогда и только тогда, когда он непуст, и каждый комплекс ''k-связен'' при k < -1. | |||
Комплекс 0-связен, если он является связным в теоретико-графовом смысле; комплекс k-связен, если он не имеет дыр в размерности k или более низких. Определение k-связности может показаться сложным, но, к счастью, рассуждения о связности можно проводить в комбинаторных терминах, используя следующее элементарное следствие из последовательности Майера-Вьеториса. | |||
'''Теорема 2. Если K и L – комплексы, такие, что K и L k-связны, | |||
'''Теорема 2. Если <math>\mathcal{K}</math> и <math>\mathcal{L}</math> – комплексы, такие, что <math>\mathcal{K}</math> и <math>\mathcal{L}</math> k-связны, а <math>\mathcal{K} \cap \mathcal{L}</math> (k-1)-связно, то <math>\mathcal{K} \cup \mathcal{L}</math> k-связно.''' | |||
| Строка 29: | Строка 30: | ||
Множество n + 1 последовательных процессов взаимодействует между собой, посылая друг другу сообщения или выполняя операции над общими объектами. В любой момент процесс может претерпеть сбой: он останавливается и больше не делает никаких шагов. Существует ограничение f на количество процессов, которые могут окончиться сбоями. Разные модели различаются по своим предположениям о времени. На одном конце спектра находится синхронная модель, в которой вычисления производятся в виде последовательности раундов. В каждом раунде процесс отправляет сообщения другим процессам, получает сообщения, отправленные ему другими процессами в этом раунде, и меняет свое состояние. (Либо не обменивается сообщениями, а | Множество n + 1 последовательных ''процессов'' взаимодействует между собой, посылая друг другу сообщения или выполняя операции над общими объектами. В любой момент процесс может претерпеть ''сбой'': он останавливается и больше не делает никаких шагов. Существует ограничение <math>f</math> на количество процессов, которые могут окончиться сбоями. Разные модели различаются по своим предположениям о времени. На одном конце спектра находится ''синхронная модель'', в которой вычисления производятся в виде последовательности раундов. В каждом раунде процесс отправляет сообщения другим процессам, получает сообщения, отправленные ему другими процессами в этом раунде, и меняет свое состояние. (Либо не обменивается сообщениями, а выполняет операции над общими объектами). Все процессы выполняют шаги с одинаковой скоростью, все сообщения доставляются за одно и то же время. На противоположном конце располагается ''асинхронная модель'', в которой нет ограничений на время, которое может пройти между шагами процесса, и на время, которое может потребоваться для доставки сообщения. Между этими крайностями находится ''полусинхронная модель'', в которой время выполнения шагов процесса и время доставки сообщений могут меняться, но ограничены постоянными верхней и нижней границами. Доказательство нижней границы в любой из этих моделей требует глубокого понимания глобальных состояний, которые могут возникнуть в ходе выполнения протокола, и того, как эти глобальные состояния связаны между собой. | ||
Каждый процесс | |||
Каждый процесс начинает с ''входного значения'', взятого из множества V, а затем выполняет детерминированный ''протокол'', в котором он неоднократно получает одно или несколько сообщений, изменяет свое локальное состояние и отправляет одно или несколько сообщений. После конечного числа шагов каждый процесс выбирает ''значение решения'' и останавливается. | |||
В задаче согласования k множеств [ ] процессы должны (1) выбрать значение решения после конечного числа шагов, (2) выбрать в качестве значения решения | В задаче согласования k множеств [5] процессы должны: (1) выбрать значение решения после конечного числа шагов, (2) выбрать в качестве значения решения входное значение некоторого процесса и (3) коллективно выбрать не более k различных значений решения. При k = 1 эта задача обычно называется ''задачей о консенсусе'' [16]. | ||
Между топологическими моделями и вычислениями имеется следующая связь. Начальное локальное состояние процесса P моделируется как вершина v = | Между топологическими моделями и вычислениями имеется следующая связь. Начальное локальное состояние процесса <math>P</math> моделируется как вершина <math>\vec{v} = \langle P, v \rangle</math>, помеченная идентификатором процесса <math>P</math> и начальным значением <math>v</math>. Начальное глобальное состояние моделируется как n-симплекс <math>S^n = ( \langle P_0, v_0 \rangle , ..., \langle P_n, v_n \rangle )</math>, где все <math>P_i</math> различны. За <math>ids(S^n)</math> обозначается множество идентификаторов процессов, связанных с <math>S^n</math>, а за <math>vals(S^n)</math> – множество значений. Множество всех возможных начальных глобальных состояний образует комплекс, называемый ''входным комплексом''. | ||
Любой протокол имеет связанный с ним протокольный комплекс P, определяемый следующим образом. Каждая вершина помечена идентификатором процесса и возможным локальным состоянием этого процесса. Множество вершин | Любой протокол имеет связанный с ним ''протокольный комплекс'' <math>\mathcal{P}</math>, определяемый следующим образом. Каждая вершина помечена идентификатором процесса и возможным локальным состоянием этого процесса. Множество вершин <math>\langle P_0, v_0 \rangle , ..., \langle P_d, v_d \rangle</math> охватывает симплекс <math>\mathcal{P}</math> тогда и только тогда, когда существует некоторое выполнение протокола, при котором <math>P_0, ..., P_d</math> завершают его с соответствующими локальными состояниями <math>v_0, ..., v_d</math>. Таким образом, каждый симплекс соответствует классу эквивалентности выполнений, которые «выглядят одинаково» для процессов в его вершинах. За <math>\mathcal{P}(S^m)</math> обозначается подкомплекс <math>\mathcal{P}</math>, соответствующий выполнениям, в которых участвуют только процессы из <math>ids(S^n)</math> (остальные завершаются сбоями, не отправив ни одного сообщения). Если <math>m < n - f</math>, то таких выполнений не существует, и подкомплекс <math>\mathcal{P}(S^m)</math> пуст. Структура протокольного комплекса <math>\mathcal{P}</math> зависит как от протокола, так и от временных характеристик и характеристик отказов модели. Часто <math>\mathcal{P}</math> обозначает и протокол, и его комплекс; различие между ними проводится, исходя из контекста. | ||
Протокол решает задачу о согласовании k множеств, если существует симплициальное отображение | Протокол ''решает'' задачу о согласовании k множеств, если существует симплициальное отображение <math>\delta</math>, называемое ''картой решений'', которое отображает вершины <math>\mathcal{P}</math> на значения в <math>V</math> таким образом, что если <math>\vec{p} \in \mathcal{P} (S^n)</math>, то <math>\delta(\vec{p}) \in vals(S^n)</math>, и <math>\delta</math> отображает вершины любого данного симплекса в <math>\mathcal{P}(S^n)</math> на не более чем k различных значений. | ||
== Применение == | == Применение == | ||
| Строка 55: | Строка 58: | ||
== Литература == | == Литература == | ||
Вероятно, первой работой, в которой исследовалась разрешимость распределенных задач, была основополагающая статья Фишера, Линч и Патерсона 1985 года [6], в которой было показано, что ''консенсус'', считавшийся в то время абстракцией задачи внесения данных в базу данных, не имеет 1-устойчивого решения с передачей сообщений. Внимание исследователей также привлекли другие задачи, такие как ''переименование'' [1, 12, 15] и ''согласование множеств'' [3, 5, 12, 10, 15, 17]. | |||
В 1988 году Биран, Моран и Закс [2] представили теоретико-графовую характеризацию проблем разрешимости, которые могут быть решены при наличии одного сбоя в системе передачи сообщений. Этот результат не был существенно улучшен до 1993 года, когда трем независимым исследовательским группам удалось применить комбинаторные методы к протоколам, допускающим задержки более чем у одного процессора: Боровски и Гафни [3], Сакс и Захароглу [ ], Херлихи и Шавит [15]. | В 1988 году Биран, Моран и Закс [2] представили теоретико-графовую характеризацию проблем разрешимости, которые могут быть решены при наличии одного сбоя в системе передачи сообщений. Этот результат не был существенно улучшен до 1993 года, когда трем независимым исследовательским группам удалось применить комбинаторные методы к протоколам, допускающим задержки более чем у одного процессора: Боровски и Гафни [3], Сакс и Захароглу [17], Херлихи и Шавит [15]. | ||
| Строка 64: | Строка 67: | ||
Биран, Моран и Закс [ ] представили первый результат о разрешимости задач на принятие решений, показав, что эти задачи разрешимы в 1-устойчивой модели передачи сообщений. Гафни и Кутсупиас [7] первыми сделали важное замечание о том, что задача о стягиваемости может быть использована для доказательства неразрешимости задач, и предложили стратегию сведения конкретной не требующей ожидания задачи для трех процессов к задаче о стягиваемости. Херлихи и Райсбаум [ ] предоставили более обширную коллекцию результатов о разрешимости. | Биран, Моран и Закс [2] представили первый результат о разрешимости задач на принятие решений, показав, что эти задачи разрешимы в 1-устойчивой модели передачи сообщений. Гафни и Кутсупиас [7] первыми сделали важное замечание о том, что задача о стягиваемости может быть использована для доказательства неразрешимости задач, и предложили стратегию сведения конкретной не требующей ожидания задачи для трех процессов к задаче о стягиваемости. Херлихи и Райсбаум [11] предоставили более обширную коллекцию результатов о разрешимости. | ||
Боровски и Гафни [ ] определили модель | Боровски и Гафни [3] определили модель итеративного моментального снимка, имеющую рекурсивную структуру. Чаудхури, Херлихи, Линч и Таттл [4] предложили индуктивное построение синхронной модели, и хотя полученный «бермудский треугольник» визуально привлекателен и представляет собой элегантную комбинацию методов доказательства из литературы, формальное описание этого построения выглядит весьма сложным. В этом смысле формальное представление более поздних построений оказалось значительно лаконичнее. | ||
