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

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

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