Почему мы не смогли разработать единую теорию сложности распределенных вычислений?

41

Область распределенных вычислений оказалась крайне неудачной в разработке единой математической теории для описания распределенных алгоритмов. Существует несколько «моделей» и структур распределенных вычислений, которые просто не совместимы друг с другом. Абсолютный взрыв различных временных свойств (асинхронность, синхронность, частичная синхронность), различных примитивов связи (передача сообщений по сравнению с общей памятью, широковещательная или одноадресная передача), модели множественных сбоев (аварийный останов, аварийное восстановление, пропуск отправки, византийский и т. Д.). на) оставил нам неразрешимое количество системных моделей, структур и методологий, что сравнение результатов относительной разрешимости и нижних границ для этих моделей и структур стало трудным, неразрешимым, а порой и невозможным.

Мой вопрос очень прост, почему это так? Что настолько принципиально отличается в распределенных вычислениях (от их последовательного аналога), что мы не смогли сопоставить исследование в единой теории распределенных вычислений? С последовательными вычислениями машины Тьюринга, Рекурсивные функции и Лямбда-исчисление все обрезаны, чтобы быть эквивалентными. Было ли это просто удачей или мы действительно проделали хорошую работу по инкапсуляции последовательных вычислений способом, который еще не был достигнут с распределенными вычислениями?

Другими словами, распределенные вычисления по своей природе не поддаются элегантной теории (и если да, то как и почему?) Или мы просто недостаточно умны, чтобы открыть такую ​​теорию?

Единственная ссылка, которую я смог найти для решения этой проблемы: « Оценка двух десятилетий исследований теории распределенных вычислений » Фишера и Мерритта DOI: 10.1007 / s00446-003-0096-6

Любые ссылки или экспозиции будут действительно полезны.

Срикант Шастри
источник

Ответы:

26

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

Скажем, с 1940 по 1995 год размер проблемных экземпляров, относительная «неважность» параллелизма и параллелизма и макромасштаб вычислительных устройств - все это «сговорилось», чтобы машины Тьюринга превосходно приближались к компьютерам реального мира. Однако, как только вы начнете иметь дело с массивными наборами данных, повсеместной потребностью в параллелизме, биологией через алгоритмический объектив и т. Д., Станет гораздо менее понятно, существует ли «интуитивная» модель вычислений. Возможно, сложные задачи в одной модели не являются сложными - строго менее вычислительно сложными - в другой. Поэтому я считаю, что сложная вычислительная сложность наконец-то (!) Догоняет распределенные вычисления, начав с рассмотрения множества моделей вычислений и структур данных, мотивированных реальными соображениями.

Аарон Стерлинг
источник
7
Также рассмотрите определяющие вопросы соответствующих полей. «Предположим, вы можете прекрасно вычислить. Каковы пределы того, что вы можете и не можете сделать?» vs. «Предположим, у вас неисправный канал, процессор или предполагается, что у вас есть злоумышленник. Как вы можете успешно вычислять, когда сталкиваетесь с этими препятствиями?» Первый вопрос, скорее всего, породит «чистые» ответы. Второе - это просьба научить капризничать.
Аарон Стерлинг
21

Я отвечу на это с точки зрения классических проблем с графами (или проблем ввода / вывода): у нас есть сеть, каждый узел получает что-то в качестве ввода, и каждый узел должен производить что-то в качестве вывода. Я думаю, что это ближе всего к миру традиционных вычислительных сложностей.

Я , конечно , пристрастен, но я думаю , что в этой ситуации есть это простой и достаточно широко используемая модель распределенных вычислительный: синхронные распределенные алгоритмы , с определением , что время = количество синхронных раундов работы . В терминологии Пелега это ЛОКАЛЬНАЯ модель.

Эта модель хороша тем, что в ней очень мало «движущихся частей», нет параметров и т. Д. Тем не менее, она очень конкретна: имеет смысл сказать, что время работы алгоритма в этой модели ровно 15. И вы можете доказать безусловные, теоретико-информационные нижние границы: с этой точки зрения распределенная сложность многих задач с графами (например, раскраска графов) достаточно понятна.

Эта модель также обеспечивает единый подход ко многим аспектам распределенных вычислений:

  • Передача сообщений и общая память, широковещательная или одноадресная передача: не имеет значения в этой модели.
  • α
  • Вам нужен алгоритм для динамических сетей или вы хотите восстанавливаться после сбоев? Что ж, если ваш синхронный алгоритм является детерминированным, то вы можете использовать его для построения самостабилизирующегося алгоритма. Опять же, сложность времени практически не изменяется.

Теперь все это хорошо, если вы изучаете проблемы, которые «действительно распределены» в том смысле, что время выполнения вашего алгоритма меньше диаметра графа , т. Е. Ни один узел не должен иметь полной информации о структуре граф. Однако есть также много проблем, которые по своей природе глобальны: самый быстрый алгоритм в этой модели имеет время выполнения, которое является линейным по диаметру графика. При изучении этих проблем приведенная выше модель больше не имеет никакого смысла, и тогда нам нужно прибегнуть к чему-то другому. Как правило, начинают обращать внимание на общее количество сообщений или битов, передаваемых в сети. Это одна из причин, почему мы получаем несколько разных моделей.


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

Юкка Суомела
источник
Если я правильно понимаю, дело в том, что существует изящная теория только для синхронных систем и не более того. Что касается систем, отличных от синхронных, мы объединяем проблемы / фокусы двух разных сообществ, и это представляет методологические проблемы при разработке единой теории. Правильно ли я понял ваши аргументы?
Срикант Шастри
Спасибо за очень информативный ответ. Я бы принял это как ответ.
Мухаммед Аль-Туркистани
5

Одна романтическая идея для захвата различных моделей распределенных вычислений была через алгебраическую топологию. Основная идея заключается в построении симплициальных комплексов, позволяя точкам быть состояниями процесса, каждое из которых помечено идентификатором процесса. Это учебник по теме. Ближайший ответ на ваш вопрос, вероятно, был затронут Эли Гафни в его статье «Распределенные вычисления - проблеск теории». В своей статье он показывает моделирование, как начать с асинхронной общей памяти для двух-трех процессоров (для аварийного останова и византийского) - он показывает, как можно применить это к модели передачи сообщений. Крайне важным для понимания его моделирования является представление о топологическом распределении вычислений.

Kryptos
источник
4

Я думаю, что ситуация выглядит совершенно иначе, если рассматривать ее в контексте: начиная с ранних работ и результатов невозможности византийского соглашения ( PSL80 LSP82 FLP85) вскоре стало ясно, что фундаментальные проблемы в распределенных вычислениях могут быть решены только при строгих предположениях о синхронизации и высокой степени избыточности. Поскольку эти безусловные теоретические нижние границы ресурса считались неосуществимыми для любых практических целей, исследования были сосредоточены на разработке более совершенных моделей, которые позволили бы получить более детальный компромисс между предположениями (например, о временных гарантиях или режимах сбоев) по сравнению с гарантиями (т.е. количеством одновременные сбои того, какие типы компонентов допускаются (например, процессоры, ссылки), чтобы дать разработчикам системы инструменты для нахождения правильного компромисса для имеющейся системы.

Мартин Шварц
источник
Я понимаю, что усовершенствованные модели были введены для понимания «практической» разрешимости задач в распределенном пространстве. Можно было бы ожидать, что эти детализированные модели будут аккуратно организованы в иерархию в отношении разрешимости, сложности времени и сложности сообщений. К сожалению, это не случай. Мой вопрос здесь, в чем причина этой балканизации? Если это какой-то атрибут (ы), присущий распределенным вычислениям, то каковы они?
Срикант Шастри