Как преобразовать централизованный алгоритм распределенным алгоритмом?

Question

Есть ли алгоритм или процедура для преобразования централизованного алгоритма для распределенного алгоритма?Есть ли теоретический результат или соответствующий анализ сложности?

Answer 1

Конечно. Если у вас есть распределенная система с N MACHINES, вы всегда можете запустить централизованный алгоритм на машине 1 и пусть машины 2 ...N сидеть на холостом ходу.

Если вы спрашиваете, могут ли все последовательные алгоритмы могут быть распараллелизованы, это открытый вопрос, но считается, что ответ не является: см. Класс сложности NC . Как говорится в Википедии,

Вероятно, есть некоторые прочные проблемы, которые являются «по своей природой», и не могут быть значительно ускорены, используя параллелизм.

P-полные проблемы являются хорошими кандидатами для проблем, которые, вероятно, не поддаются ускорению путем параллелизма.

Если вы спрашиваете, могут ли вы быть сделаны все алгоритмы надежными в распределенной системе, то есть тонкий вопрос, который зависит от того, какие сбои вы рассматриваете. Вы можете посмотреть на Консенсусные протоколы , репликация состояния машины и Крышка теорема .