Основные нерешенные проблемы в распределенных системах?

Вдохновленный этим вопросом , каковы основные проблемы и существующие решения, которые нуждаются в улучшении в (теоретической) области распределенных систем.

Что-то вроде протоколов членства, согласованности данных?

См., Например, Восемь открытых проблем в распределенных вычислениях .

Распределенный временная сложность многочисленных задач на графах по - прежнему остается открытым.

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

Например, мы не знаем, сколько раундов связи требуется, чтобы найти максимальное независимое множество , максимальное совпадение , правильную раскраску вершин с цветами или правильную раскраску ребер с цветами в граф с максимальной степенью . Все эти проблемы легко решить с помощью жадных централизованных алгоритмов, и для каждой из них существуют эффективные распределенные алгоритмы, но мы не знаем, являются ли какие-либо из существующих алгоритмов оптимальными.2 Δ - 1 $\Delta+1$$2\Delta-1$$\Delta$

Например, для всех этих проблем существуют детерминированные распределенные алгоритмы для модели LOCAL со временем выполнения , где - количество узлов. Это хорошо известно , что эти проблемы не могут быть решены за время раундов, но это не известно , если они могут быть решены за время раундов. В общем, мы не понимаем, как время выполнения зависит от максимальной степени - это то, что я называю проблемой локальной координации .$O(\Delta + \log^* n)$O ( Δ ) + o ( log ∗ n ) o ( Δ ) + O ( log ∗ n $n$$O(\Delta) + o(\log^* n)$$o(\Delta) + O(\log^* n)$

Роль случайности - еще одна важная проблема. Например, многие из вышеупомянутых проблем могут быть решены за время полилога с помощью рандомизированных алгоритмов (т. Е. Время является полилогом по для любого значения ), но детерминированные алгоритмы времени полилога не известны, например, для максимального независимого наборы. Эти вопросы, а также многие другие открытые проблемы более подробно обсуждаются в разделе 11 недавней книги Баренбойма и Элькина .$n$$\Delta$

Выше я сосредоточился на вопросах, относящихся к распределенным вычислениям. Есть также открытые вопросы в алгоритмах распределенных графов, которые имеют нетривиальные связи с открытыми проблемами в теоретической информатике в целом. Например, непостоянные нижние оценки для модели перегруженной клики являются большим открытым вопросом в распределенных вычислениях; недавно было обнаружено, что такие нижние оценки также означают новые нижние оценки для ACC.

Открытые задачи по «Распределенным алгоритмам для минимальных остовных деревьев (MST)»: (перечислены в [1])

1. Что касается сложности времени ,

   Оптимальные по ближнему времени алгоритмы и нижние оценки приведены в [2] и в ссылках. Оптимальная временная сложность остается открытой проблемой.

2. Что касается сложности сообщения ,

   Что касается сложности сообщения , хотя асимптотически точная граница для задачи MST в общих графах известна, нахождение фактических констант остается открытой проблемой.$O(m + n \log n)$

3. По поводу синхронной модели:

   В синхронной модели для оверлейных сетей, где все процессоры напрямую связаны друг с другом, MST может быть построен за сублогарифмическое время, а именно раундов связи [3], и соответствующая нижняя граница не известна.$O(\log \log n)$

Также отметим, что существует алгоритм аппроксимации для распределенного MST [4].$O(\log n)$

[1] Распределенные алгоритмы для минимальных остовных деревьев. Автор Sergio Rajsbaum в «Энциклопедии алгоритмов», 2008.

[2] Распределенный MST для графиков постоянного диаметра по Lotker et al. Distrib. Comput., 2006.

[3] Построение минимального веса связующего дерева в раундах связи$O(\log \log n)$ по Lotker et al. SIAM J. Comput., 35 (1), 2005.

[4] Алгоритм быстрого распределенного приближения для минимальных остовных деревьев , Khan et al. ДИСК 2006.

см. также (совсем недавно) слайд-шоу «Нерешенные проблемы информатики в распределенных вычислениях» от 2012 года от исследователя Нотр-Дама Дугласа Тейна, который возглавляет совместную вычислительную лабораторию. у него больше прикладного уклона, но перечисленные ключевые вопросы неизбежно ведут к теоретическим областям.

• Проблема Kiloscale: любой рабочий процесс с достаточным параллелизмом должен иметь возможность правильно запускаться на ядрах 1K в первый раз и каждый раз без помощи системного администратора.

• Проблема остановки: учитывая рабочий процесс, работающий на одной тысяче узлов, остановите его и очистите все связанные состояния с полной уверенностью.

• Проблема зависимости:

  (1) Учитывая программу, выясните все, что ей действительно нужно для запуска на другом компьютере.

  (2) Учитывая процесс, определите (распределенные) ресурсы, которые он фактически использует во время работы.

  (3) Расширить 1 и 2 на весь рабочий процесс.

• Проблема правильного определения размера: учитывая (структурированное) приложение и данный кластер, облако или сетку, выберите распределение ресурсов, которое обеспечивает хорошую производительность при приемлемых затратах.

• Проблема устранения неполадок: когда происходит сбой в середине 100-слойного программного стека, как и когда вы сообщаете / повторяете / игнорируете / подавляете ошибку?

• Проблема проектирования: как следует разрабатывать приложения, чтобы они хорошо подходили для распределенных вычислений?