Невозможность асинхронного консенсуса: различия между версиями
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим распределенную систему, состоящую из множества ''процессов'', которые взаимодействуют между собой путем отправки и получения сообщений. Сеть представляет собой мультимножество сообщений, | Рассмотрим распределенную систему, состоящую из множества ''процессов'', которые взаимодействуют между собой путем отправки и получения сообщений. Сеть представляет собой мультимножество сообщений, в котором каждое сообщение адресовано некоторому процессу. Процесс – это машина состояний, которая может выполнять три вида ''шагов''. | ||
• На шаге ''отправки'' ( | • На шаге ''отправки'' (send) процесс помещает сообщение в сеть. | ||
• На шаге ''получения'' (receive) процесс A либо считывает и удаляет из сети сообщение, адресованное A, либо считывает выделенное ''нулевое'' значение, оставляя сеть без изменений. Если сообщение, адресованное A, помещено в сеть, и если A последовательно выполнит бесконечное число шагов получения, то в конце концов получит это сообщение. | • На шаге ''получения'' (receive) процесс A либо считывает и удаляет из сети сообщение, адресованное A, либо считывает выделенное ''нулевое'' значение, оставляя сеть без изменений. Если сообщение, адресованное A, помещено в сеть, и если A последовательно выполнит бесконечное число шагов получения, то в конце концов получит это сообщение. | ||
| Строка 17: | Строка 17: | ||
В ''задаче о достижении консенсуса'' каждый процесс начинает работу с частного ''входного'' значения, взаимодействует с остальными, а затем останавливается с найденным значением ''решения''. Такие значения должны удовлетворять следующим свойствам: | В ''задаче о достижении консенсуса'' каждый процесс начинает работу с частного ''входного'' значения, взаимодействует с остальными, а затем останавливается с найденным значением ''решения''. Такие значения должны удовлетворять следующим свойствам: | ||
• ''Согласованность'': значения решений всех процессов должны | • ''Согласованность'': значения решений всех процессов должны быть согласованными. | ||
• ''Допустимость'': каждое значение решения должно быть входным значением некоторого процесса. | • ''Допустимость'': каждое значение решения должно быть входным значением некоторого процесса. | ||
| Строка 46: | Строка 46: | ||
'''Лемма 1'''. Каждый протокол консенсуса имеет бивалентное начальное состояние. | '''Лемма 1'''. Каждый протокол консенсуса имеет бивалентное начальное состояние. | ||
Доказательство. Предположим от противного, что существует протокол консенсуса для (n + 1) потоков <math>A_0, ..., A_n</math>, в котором каждое начальное состояние является унивалентным. Обозначим за <math>s_i</math> начальное состояние, в котором процессы <math>A_i, ..., A_n</math> имеют на входе 0, а у <math>A_0, ..., A_{i - i}</math> на входе 1. Очевидно, что <math>s_0</math> является 0-валентным: все процессы имеют на входе 0, поэтому по условию допустимости все они должны прийти к решению 0. Если <math>s_i</math> является 0-валентным, то и <math>s_{i + 1}</math> тоже. Эти состояния отличаются только входными данными процесса <math>A_i</math>: 0 у <math>s_i</math> и 1 у | Доказательство. Предположим от противного, что существует протокол консенсуса для (n + 1) потоков <math>A_0, ..., A_n</math>, в котором каждое начальное состояние является унивалентным. Обозначим за <math>s_i</math> начальное состояние, в котором процессы <math>A_i, ..., A_n</math> имеют на входе 0, а у <math>A_0, ..., A_{i - i}</math> на входе 1. Очевидно, что <math>s_0</math> является 0-валентным: все процессы имеют на входе 0, поэтому по условию допустимости все они должны прийти к решению 0. Если <math>s_i</math> является 0-валентным, то и <math>s_{i + 1}</math> тоже. Эти состояния отличаются только входными данными процесса <math>A_i</math>: 0 у <math>s_i</math> и 1 у <math>s_{i + 1}</math>. Любое выполнение, начинающееся с <math>s_i</math>, в котором <math>A_i</math> останавливается перед выполнением каких-либо шагов, неотличимо от выполнения, начинающегося с <math>s_{i + 1}</math>, в котором <math>A_i</math> останавливается перед выполнением каких-либо шагов. Поскольку в первом случае процессы должны принять решение 0, во втором они должны принять решение 1. А поскольку существует одно исполнение, начинающееся с <math>s_{i + 1}</math>, которое принимает решение 0, и поскольку согласно гипотезе <math>s_{i + 1}</math> унивалентно, то <math>s_{i + 1}</math> является 0-валентным. Отсюда следует, что состояние <math>s_{n + 1}</math>, в котором все процессы начинаются со входного значения 1, является 0-валентным, что противоречит условию. <math>\Box</math> | ||
'''Лемма 2'''. Каждый протокол консенсуса имеет критическое состояние. | '''Лемма 2'''. Каждый протокол консенсуса имеет критическое состояние. | ||
Доказательство от противного. Согласно лемме 1, протокол имеет бивалентное начальное состояние. Запустим выполнение протокола в этом состоянии. Многократно выбираем процесс, следующий шаг которого оставляет протокол в бивалентном состоянии, и позволяем данному процессу сделать этот шаг. Либо протокол будет работать вечно, нарушая условие завершения, либо в конце концов перейдет в критическое состояние. | Доказательство от противного. Согласно лемме 1, протокол имеет бивалентное начальное состояние. Запустим выполнение протокола в этом состоянии. Многократно выбираем процесс, следующий шаг которого оставляет протокол в бивалентном состоянии, и позволяем данному процессу сделать этот шаг. Либо протокол будет работать вечно, нарушая условие завершения, либо в конце концов перейдет в критическое состояние. <math>\Box</math> | ||
'''Теорема 3 Не существует протокола консенсуса для асинхронной системы передачи сообщений, в которой один процесс может претерпеть сбой.''' | '''Теорема 3. Не существует протокола консенсуса для асинхронной системы передачи сообщений, в которой один процесс может претерпеть сбой.''' | ||
Доказательство. Предположим от противного, что такой протокол существует. Будем выполнять протокол, пока он не достигнет критического состояния s. Должны существовать два процесса A и B, такие, что следующий шаг A переводит протокол в 0-валентное состояние, а следующий шаг B переводит его в 1-валентное состояние. | Доказательство. Предположим от противного, что такой протокол существует. Будем выполнять протокол, пока он не достигнет критического состояния s. Должны существовать два процесса A и B, такие, что следующий шаг A переводит протокол в 0-валентное состояние, а следующий шаг B переводит его в 1-валентное состояние. | ||
| Строка 62: | Строка 62: | ||
Из всех возможных пар шагов, которые A и B могли бы выполнить, большинство из них ''коммутативны'': состояния <math>s_{AB}</math> и <math>s_{BA}</math> идентичны, что порождает противоречие, поскольку они имеют разные валентности. | Из всех возможных пар шагов, которые A и B могли бы выполнить, большинство из них ''коммутативны'': состояния <math>s_{AB}</math> и <math>s_{BA}</math> идентичны, что порождает противоречие, поскольку они имеют разные валентности. | ||
Единственная пара некоммутативных шагов имеет место в случае, когда А собирается отправить сообщение В (или наоборот). Обозначим за <math>s_{AB}</math> состояние, возникающее, если А посылает сообщение В, а В затем его получает, а за <math>s_{BA}</math> – состояние, возникающее, если В получает другое (или ''нулевое'') сообщение, а затем А посылает свое сообщение В. Обратите внимание, что каждый процесс, отличный от В, имеет одно и то же локальное состояние в <math>s_{AB}</math> и <math>s_{BA}</math>. Рассмотрим выполнение, начинающееся с <math>s_{AB}</math>, в котором каждый процесс, кроме В, делает шаги в порядке очереди. Поскольку <math>s_{AB}</math> является 0-валентным, все эти процессы в конечном итоге найдут решение 0. Далее рассмотрим выполнение, начинающееся с <math>s_{BA}</math>, в котором каждый процесс, отличный от В, делает шаги в порядке очереди. Поскольку <math>s_{BA}</math> является 1-валентным, все эти процессы в конечном итоге найдут решение 1. Но все процессы, кроме В, имеют одинаковые локальные состояния в конце каждого выполнения, поэтому они не могут принимать решения с разными значениями, что составляет противоречие. | Единственная пара некоммутативных шагов имеет место в случае, когда А собирается отправить сообщение В (или наоборот). Обозначим за <math>s_{AB}</math> состояние, возникающее, если А посылает сообщение В, а В затем его получает, а за <math>s_{BA}</math> – состояние, возникающее, если В получает другое (или ''нулевое'') сообщение, а затем А посылает свое сообщение процессу В. Обратите внимание, что каждый процесс, отличный от В, имеет одно и то же локальное состояние в <math>s_{AB}</math> и <math>s_{BA}</math>. Рассмотрим выполнение, начинающееся с <math>s_{AB}</math>, в котором каждый процесс, кроме В, делает шаги в порядке очереди. Поскольку <math>s_{AB}</math> является 0-валентным, все эти процессы в конечном итоге найдут решение 0. Далее рассмотрим выполнение, начинающееся с <math>s_{BA}</math>, в котором каждый процесс, отличный от В, делает шаги в порядке очереди. Поскольку <math>s_{BA}</math> является 1-валентным, все эти процессы в конечном итоге найдут решение 1. Но все процессы, кроме В, имеют одинаковые локальные состояния в конце каждого выполнения, поэтому они не могут принимать решения с разными значениями, что составляет противоречие. <math>\Box</math> | ||
| Строка 77: | Строка 77: | ||
Многие исследователи изучали альтернативные модели вычислений, в которых можно достичь консенсуса. Долев, Дворк и Стокмайер [5] рассматривают различные альтернативные модели передачи сообщений, определяя точные предположения, необходимые для возможности достижения консенсуса. Дворк, Линч и Стокмайер [6] вывели верхние и нижние границы для полусинхронной модели, в которой есть верхняя и нижняя границы времени доставки сообщений. Бен-Ор [1] показал, что введение рандомизации делает возможным консенсус в асинхронной системе передачи сообщений. Чандра и Туэг [3] | Многие исследователи изучали альтернативные модели вычислений, в которых можно достичь консенсуса. Долев, Дворк и Стокмайер [5] рассматривают различные альтернативные модели передачи сообщений, определяя точные предположения, необходимые для возможности достижения консенсуса. Дворк, Линч и Стокмайер [6] вывели верхние и нижние границы для полусинхронной модели, в которой есть верхняя и нижняя границы времени доставки сообщений. Бен-Ор [1] показал, что введение рандомизации делает возможным консенсус в асинхронной системе передачи сообщений. Чандра и Туэг [3] продемонстрировали, что консенсус становится возможным при наличии оракула, способного (ненадежно) определить, когда процесс закончился сбоем. Каждая из процитированных здесь работ вдохновила множество последующих. Желающим разобраться в теме рекомендуем для начала прекрасный обзор Фич и Рупперта [7]. | ||
Протокол '' | Протокол является ''протоколом без ожидания'', если он допускает сбои в работе всех участников, кроме одного. Параллельная реализация объектов ''линеаризуема'' в случае, если каждый вызов метода мгновенно производит эффект в какой-то момент между обращением к нему и его ответом. Херлихи [9] показал, что каждому объекту совместно используемой памяти можно присвоить ''номер консенсуса'' – максимальное количество процессов, для которых существует протокол консенсуса без ожидания, использующий комбинацию памяти с возможностью чтения/записи и рассматриваемых объектов. Номера консенсуса порождают бесконечную иерархию объектов, в которой (несколько упрощая) вышестоящие объекты являются более мощными по сравнению с нижестоящими. В системе из n или более параллельных процессов невозможно построить свободную от блокировок реализацию объекта с номером консенсуса n из объекта с меньшим номером консенсуса. С другой стороны, любой объект с номером консенсуса n является ''универсальным'' в системе из n или менее процессов: он может быть использован для построения линеаризуемой реализации любого объекта без ожидания. | ||
В 1990 году Чаудхури [4] представила задачу о согласовании k множеств (k-set agreement problem), иногда называемую задачей о нахождении консенсуса для k множеств, которая обобщает задачу достижения консенсуса, позволяя выбирать k или меньше различных значений решения. В частности, консенсусом является задача о согласовании для 1 множества. Вопрос о том, можно ли решить задачу о согласовании k множеств в асинхронных моделях передачи сообщений, оставался открытым в течение нескольких лет, пока три независимые группы исследователей [2, 10, 11] не | В 1990 году Чаудхури [4] представила [[Согласование множеств|задачу о согласовании k множеств]] (k-set agreement problem), иногда называемую ''задачей о нахождении консенсуса для k множеств'', которая обобщает задачу достижения консенсуса, позволяя выбирать k или меньше различных значений решения. В частности, консенсусом является задача о согласовании для 1 множества. Вопрос о том, можно ли решить задачу о согласовании k множеств в асинхронных моделях передачи сообщений, оставался открытым в течение нескольких лет, пока три независимые группы исследователей [2, 10, 11] не доказали, что такого протокола не существует. | ||
== См. также == | == См. также == | ||
Текущая версия от 15:30, 16 сентября 2024
Ключевые слова и синонимы
Консенсус без ожидания; согласование
Постановка задачи
Рассмотрим распределенную систему, состоящую из множества процессов, которые взаимодействуют между собой путем отправки и получения сообщений. Сеть представляет собой мультимножество сообщений, в котором каждое сообщение адресовано некоторому процессу. Процесс – это машина состояний, которая может выполнять три вида шагов.
• На шаге отправки (send) процесс помещает сообщение в сеть.
• На шаге получения (receive) процесс A либо считывает и удаляет из сети сообщение, адресованное A, либо считывает выделенное нулевое значение, оставляя сеть без изменений. Если сообщение, адресованное A, помещено в сеть, и если A последовательно выполнит бесконечное число шагов получения, то в конце концов получит это сообщение.
• В состоянии вычисления (computation) процесс изменяет свое состояние без коммуникаций с каким-либо другим процессом.
Процессы являются асинхронными: не существует ограничений на их относительную скорость. Процессы могут претерпевать сбои: они могут просто остановиться и больше не делать никаких шагов. Далее рассматривается выполнение, в ходе которого сбой происходит не более чем у одного процесса.
В задаче о достижении консенсуса каждый процесс начинает работу с частного входного значения, взаимодействует с остальными, а затем останавливается с найденным значением решения. Такие значения должны удовлетворять следующим свойствам:
• Согласованность: значения решений всех процессов должны быть согласованными.
• Допустимость: каждое значение решения должно быть входным значением некоторого процесса.
• Завершение: каждый процесс без сбоев должен принять решение за конечное число шагов.
Фишер, Линч и Патерсон показали, что не существует протокола, решающего задачу о достижении консенсуса в любой асинхронной системе передачи сообщений, где даже один процесс может завершиться сбоем. Этот результат стал одним из самых влиятельных в области распределенных вычислений и заложил основу для целого ряда последующих исследований.
Терминология
Без потери общности можно ограничиться бинарным консенсусом, у которого входные значения могут быть равны 0 или 1. Состояние протокола – это комплекс состояний процессов и мультимножества сообщений, проходящих по сети. Начальным состоянием является состояние протокола до того, как какой-либо процесс начал движение, а конечным – состояние протокола после завершения всех процессов. Значение решения в любом конечном состоянии представляет собой значение, принятое всеми процессами в этом состоянии.
Набор возможных состояний любого завершающегося протокола образует дерево, где каждая вершина представляет возможное состояние протокола, а каждое ребро – возможный шаг некоторого процесса. Поскольку протокол должен завершиться, дерево является конечным. Каждая вершина-лист представляет конечное состояние протокола со значением решения 0 или 1.
Бивалентное состояние протокола – это состояние, в котором конечное значение решения еще не фиксировано. Из любого бивалентного состояния существует выполнение, в котором конечное значение решения равно 0, и другое, в котором оно равно 1. Унивалентное состояние протокола – это состояние, в котором исход фиксирован. Каждое выполнение, начиная с унивалентного состояния, находит решение с одним и тем же значением. 1-валентное состояние протокола является унивалентным с конечным значением решения 1; аналогично для 0-валентного состояния.
Состояние протокола является критическим, если:
• оно бивалентно и
• если какой-либо процесс совершает шаг, состояние протокола становится унивалентным.
Основные результаты
Лемма 1. Каждый протокол консенсуса имеет бивалентное начальное состояние.
Доказательство. Предположим от противного, что существует протокол консенсуса для (n + 1) потоков [math]\displaystyle{ A_0, ..., A_n }[/math], в котором каждое начальное состояние является унивалентным. Обозначим за [math]\displaystyle{ s_i }[/math] начальное состояние, в котором процессы [math]\displaystyle{ A_i, ..., A_n }[/math] имеют на входе 0, а у [math]\displaystyle{ A_0, ..., A_{i - i} }[/math] на входе 1. Очевидно, что [math]\displaystyle{ s_0 }[/math] является 0-валентным: все процессы имеют на входе 0, поэтому по условию допустимости все они должны прийти к решению 0. Если [math]\displaystyle{ s_i }[/math] является 0-валентным, то и [math]\displaystyle{ s_{i + 1} }[/math] тоже. Эти состояния отличаются только входными данными процесса [math]\displaystyle{ A_i }[/math]: 0 у [math]\displaystyle{ s_i }[/math] и 1 у [math]\displaystyle{ s_{i + 1} }[/math]. Любое выполнение, начинающееся с [math]\displaystyle{ s_i }[/math], в котором [math]\displaystyle{ A_i }[/math] останавливается перед выполнением каких-либо шагов, неотличимо от выполнения, начинающегося с [math]\displaystyle{ s_{i + 1} }[/math], в котором [math]\displaystyle{ A_i }[/math] останавливается перед выполнением каких-либо шагов. Поскольку в первом случае процессы должны принять решение 0, во втором они должны принять решение 1. А поскольку существует одно исполнение, начинающееся с [math]\displaystyle{ s_{i + 1} }[/math], которое принимает решение 0, и поскольку согласно гипотезе [math]\displaystyle{ s_{i + 1} }[/math] унивалентно, то [math]\displaystyle{ s_{i + 1} }[/math] является 0-валентным. Отсюда следует, что состояние [math]\displaystyle{ s_{n + 1} }[/math], в котором все процессы начинаются со входного значения 1, является 0-валентным, что противоречит условию. [math]\displaystyle{ \Box }[/math]
Лемма 2. Каждый протокол консенсуса имеет критическое состояние.
Доказательство от противного. Согласно лемме 1, протокол имеет бивалентное начальное состояние. Запустим выполнение протокола в этом состоянии. Многократно выбираем процесс, следующий шаг которого оставляет протокол в бивалентном состоянии, и позволяем данному процессу сделать этот шаг. Либо протокол будет работать вечно, нарушая условие завершения, либо в конце концов перейдет в критическое состояние. [math]\displaystyle{ \Box }[/math]
Теорема 3. Не существует протокола консенсуса для асинхронной системы передачи сообщений, в которой один процесс может претерпеть сбой.
Доказательство. Предположим от противного, что такой протокол существует. Будем выполнять протокол, пока он не достигнет критического состояния s. Должны существовать два процесса A и B, такие, что следующий шаг A переводит протокол в 0-валентное состояние, а следующий шаг B переводит его в 1-валентное состояние.
Начиная с s, обозначим за [math]\displaystyle{ s_A }[/math] состояние, достигаемое в случае, если A делает первый шаг, за [math]\displaystyle{ s_B }[/math] – если B делает первый шаг, за [math]\displaystyle{ s_{AB} }[/math] – если A делает шаг, за которым следует B, и так далее. Состояния [math]\displaystyle{ s_A }[/math] и [math]\displaystyle{ s_{AB} }[/math] являются 0-валентными, а [math]\displaystyle{ s_B }[/math] и [math]\displaystyle{ s_{BA} }[/math] – 1-валентными. Остается провести разбор случаев.
Из всех возможных пар шагов, которые A и B могли бы выполнить, большинство из них коммутативны: состояния [math]\displaystyle{ s_{AB} }[/math] и [math]\displaystyle{ s_{BA} }[/math] идентичны, что порождает противоречие, поскольку они имеют разные валентности.
Единственная пара некоммутативных шагов имеет место в случае, когда А собирается отправить сообщение В (или наоборот). Обозначим за [math]\displaystyle{ s_{AB} }[/math] состояние, возникающее, если А посылает сообщение В, а В затем его получает, а за [math]\displaystyle{ s_{BA} }[/math] – состояние, возникающее, если В получает другое (или нулевое) сообщение, а затем А посылает свое сообщение процессу В. Обратите внимание, что каждый процесс, отличный от В, имеет одно и то же локальное состояние в [math]\displaystyle{ s_{AB} }[/math] и [math]\displaystyle{ s_{BA} }[/math]. Рассмотрим выполнение, начинающееся с [math]\displaystyle{ s_{AB} }[/math], в котором каждый процесс, кроме В, делает шаги в порядке очереди. Поскольку [math]\displaystyle{ s_{AB} }[/math] является 0-валентным, все эти процессы в конечном итоге найдут решение 0. Далее рассмотрим выполнение, начинающееся с [math]\displaystyle{ s_{BA} }[/math], в котором каждый процесс, отличный от В, делает шаги в порядке очереди. Поскольку [math]\displaystyle{ s_{BA} }[/math] является 1-валентным, все эти процессы в конечном итоге найдут решение 1. Но все процессы, кроме В, имеют одинаковые локальные состояния в конце каждого выполнения, поэтому они не могут принимать решения с разными значениями, что составляет противоречие. [math]\displaystyle{ \Box }[/math]
В доказательстве этой теоремы и в доказательствах предыдущих лемм мы строим сценарии, в которых задерживается не более одного процесса. В результате данное утверждение о невозможности выполняется для любой системы, в которой один процесс может закончиться невыявляемым сбоем.
Применение
Задача о достижении консенсуса является ключевым инструментом для понимания возможностей различных асинхронных моделей вычислений.
Открытые вопросы
Существует множество открытых вопросов, касающихся разрешимости задачи о нахождении консенсуса в других моделях или при ограничениях на входные данные.
Родственные работы
Изначальная статья Фишера, Линч и Патерсона [8] до сих пор является образцом ясности.
Многие исследователи изучали альтернативные модели вычислений, в которых можно достичь консенсуса. Долев, Дворк и Стокмайер [5] рассматривают различные альтернативные модели передачи сообщений, определяя точные предположения, необходимые для возможности достижения консенсуса. Дворк, Линч и Стокмайер [6] вывели верхние и нижние границы для полусинхронной модели, в которой есть верхняя и нижняя границы времени доставки сообщений. Бен-Ор [1] показал, что введение рандомизации делает возможным консенсус в асинхронной системе передачи сообщений. Чандра и Туэг [3] продемонстрировали, что консенсус становится возможным при наличии оракула, способного (ненадежно) определить, когда процесс закончился сбоем. Каждая из процитированных здесь работ вдохновила множество последующих. Желающим разобраться в теме рекомендуем для начала прекрасный обзор Фич и Рупперта [7].
Протокол является протоколом без ожидания, если он допускает сбои в работе всех участников, кроме одного. Параллельная реализация объектов линеаризуема в случае, если каждый вызов метода мгновенно производит эффект в какой-то момент между обращением к нему и его ответом. Херлихи [9] показал, что каждому объекту совместно используемой памяти можно присвоить номер консенсуса – максимальное количество процессов, для которых существует протокол консенсуса без ожидания, использующий комбинацию памяти с возможностью чтения/записи и рассматриваемых объектов. Номера консенсуса порождают бесконечную иерархию объектов, в которой (несколько упрощая) вышестоящие объекты являются более мощными по сравнению с нижестоящими. В системе из n или более параллельных процессов невозможно построить свободную от блокировок реализацию объекта с номером консенсуса n из объекта с меньшим номером консенсуса. С другой стороны, любой объект с номером консенсуса n является универсальным в системе из n или менее процессов: он может быть использован для построения линеаризуемой реализации любого объекта без ожидания.
В 1990 году Чаудхури [4] представила задачу о согласовании k множеств (k-set agreement problem), иногда называемую задачей о нахождении консенсуса для k множеств, которая обобщает задачу достижения консенсуса, позволяя выбирать k или меньше различных значений решения. В частности, консенсусом является задача о согласовании для 1 множества. Вопрос о том, можно ли решить задачу о согласовании k множеств в асинхронных моделях передачи сообщений, оставался открытым в течение нескольких лет, пока три независимые группы исследователей [2, 10, 11] не доказали, что такого протокола не существует.
См. также
Литература
1. Ben-Or, M.: Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In: PODC '83: Proceedings of the second annual ACM symposium on Principles of distributed computing, pp. 27-30. ACM Press, New York (1983)
2. Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: Proceedings of the 1993 ACM Symposium on Theory of Computing, May 1993. pp. 206-215
3. Chandra, T.D.,Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225-267 (1996)
4. Chaudhuri, S.: Agreement is harder than consensus: Set consensus problems in totally asynchronous systems. In: Proceedings Of The Ninth Annual ACM Symposium On Principles of Distributed Computing, August 1990. pp. 311-234
5. Chandhuri, S.: More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems. Inf. Comput. 105(1), 132-158, July 1993
6. Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288-323 (1988)
7. Fich, F., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distrib. Comput. 16(2-3), 121-163(2003)
8. Fischer, M., Lynch, N., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374-382 (1985)
9. Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. (TOPLAS) 13(1), 124-149 (1991)
10. Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858-923 (1999)
11. Saks, M.E., Zaharoglou, F.: Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput. 29(5),1449-1483(2000)