Топологический подход в распределенных вычислениях: различия между версиями

Пожалуй, первой работой, в которой исследовалась разрешимость распределенных задач, была основополагающая статья Фишера, Линч и Патерсона 1985 года [ ], в которой было показано, что консенсус, считавшийся в то время абстракцией задачи внесения данных в базу данных, не имеет 1-устойчивого решения с передачей сообщений. Внимание исследователей также привлекли другие задачи, такие как переименование [1, 12, 15] и согласование множеств [3, 5, 12, 10, 15, 17].

В 1988 году Биран, Моран и Закс [2] представили теоретико-графовую характеризацию проблем разрешимости, которые могут быть решены при наличии одного сбоя в системе передачи сообщений. Этот результат не был существенно улучшен до 1993 года, когда трем независимым исследовательским группам удалось применить комбинаторные методы к протоколам, допускающим задержки более чем у одного процессора: Боровски и Гафни [3], Сакс и Захароглу [ ], Херлихи и Шавит [15].

Биран, Моран и Закс [ ] представили первый результат о разрешимости задач на принятие решений, показав, что эти задачи разрешимы в 1-устойчивой модели передачи сообщений. Гафни и Кутсупиас [7] первыми сделали важное замечание о том, что задача о стягиваемости может быть использована для доказательства неразрешимости задач, и предложили стратегию сведения конкретной не требующей ожидания задачи для трех процессов к задаче о стягиваемости. Херлихи и Райсбаум [ ] предоставили более обширную коллекцию результатов о разрешимости.

Боровски и Гафни [ ] определили модель итертативного моментального снимка, имеющую рекурсивную структуру. Чаудхури, Херлихи, Линч и Таттл [ ] предложили индуктивное построение синхронной модели, и хотя полученный «бермудский треугольник» визуально привлекателен и представляет собой элегантную комбинацию методов доказательства из литературы, формальное описание этого построения выглядит весьма сложным. В этом смысле формальное представление более поздних построений оказалось значительно лаконичнее.