Есть ли список канонических проблем в распределенных системах?

На прошлой неделе я снова читал текст Лесли Лампорта, опубликованный в 1982 году, на конференции, которую он дал о « Решенных проблемах, нерешенных проблемах и проблемах в параллелизме» . Бумага легко читается, но одна из вещей, которая заставила меня задуматься, это следующее утверждение:

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

Я хотел бы знать, был ли дан ответ на этот вопрос для случая распределенных систем.

Существует ли набор канонических проблем распределенных систем, из которых можно свести все возможные проблемы распределенных систем? Что это за канонический список?

Если нет канонического списка, каков текущий список проблем и какие сокращения существуют?

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

Если возможно, я бы предпочел, чтобы в ответах содержалась ссылка на опубликованную статью / книгу, подтверждающую ее утверждения :)

Существует ли набор канонических проблем распределенных систем, из которых можно свести все возможные проблемы распределенных систем?

Я не знаю о таком опубликованном списке проблем.

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

$2$

С другой стороны, при рассмотрении сбоев вопросы в большей степени связаны с проблемами разрешимости, такими как «Решим ли консенсус в этой модели?» или «Можем ли мы реализовать этот причудливый детектор неисправностей при этих предположениях?»

Если нет канонического списка, каков текущий список проблем и какие сокращения существуют?

Есть много примеров такого сокращения в определенных моделях распределенных вычислений, я ограничу свой ответ следующими 2:

Локальные вычисления в (безошибочной) синхронной модели

$\Omega(\sqrt{\log n} + \log\Delta)$$n$$\Delta$$2$$A$$A$

Асинхронная модель с ошибками сбоя

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

$S$ $P$$T$$P$$S$

$P$$Q$$P$$Q$$k$

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

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

[1] Pierre Fraigniaud: Распределенные вычислительные сложности: вы увлечены вольво или одержимы наскар? PODC 2010. http://doi.acm.org/10.1145/1835698.1835700

[2] Фабиан Кун, Томас Москиброда, Роджер Ваттенхофер: Локальные вычисления: нижние и верхние границы. CoRR abs / 1011.5470 (2010) http://arxiv.org/abs/1011.5470

[3] Тушар Дипак Чандра, Сэм Тоуг: Ненадежные детекторы отказов для надежных распределенных систем. J. ACM 43 (2): 225-267 (1996). http://doi.acm.org/10.1145/226643.226647

[4] Прасад Джаянти, Сэм Тоуег: У каждой проблемы самый слабый детектор неисправностей. PODC 2008: 75-84. http://doi.acm.org/10.1145/1400751.1400763

[5] Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg: самый слабый детектор ошибок для достижения консенсуса. J. ACM 43 (4): 685-722 (1996) http://doi.acm.org/10.1145/234533.234549

[6] Мишель Рейнал: Детекторы отказов для решения асинхронного соглашения с k-множествами: проблеск недавних результатов. Бюллетень EATCS 103: 74-95 (2011) http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/61