Невозможность асинхронного консенсуса: различия между версиями

Многие исследователи изучали альтернативные модели вычислений, в которых можно достичь консенсуса. Долев, Дворк и Стокмайер [5] рассматривают различные альтернативные модели передачи сообщений, определяя точные предположения, необходимые для возможности достижения консенсуса. Дворк, Линч и Стокмайер [6] вывели верхние и нижние границы для полусинхронной модели, в которой есть верхняя и нижняя границы времени доставки сообщений. Бен-Ор [1] показал, что введение рандомизации делает возможным консенсус в асинхронной системе передачи сообщений. Чандра и Туэг [3] показали, что консенсус становится возможным при наличии оракула, способного (ненадежно) определить, когда процесс закончился сбоем. Каждая из процитированных здесь работ вдохновила множество последующих. Желающим разобраться в теме рекомендуем для начала прекрасный обзор Фич и Рупперта [7].

Протокол ''не требует ожидания'', если он допускает сбои в работе всех участников, кроме одного. Реализация параллельного объекта ''линеаризуема'' в случае, если каждый вызов метода мгновенно производит эффект в какой-то момент между обращением к нему и его ответом. Херлихи [9] показал, что каждому объекту совместно используемой памяти можно присвоить ''номер консенсуса'' – максимальное количество процессов, для которых существует протокол консенсуса без ожидания, использующий комбинацию памяти с возможностью чтения/записи и рассматриваемых объектов. Номера консенсуса порождают бесконечную иерархию объектов, в которой (несколько упрощая) вышестоящие объекты являются более мощными по сравнению с нижестоящими. В системе из n или более параллельных процессов невозможно построить свободную от блокировок реализацию объекта с номером консенсуса n из объекта с меньшим номером консенсуса. С другой стороны, любой объект с номером консенсуса n является ''универсальным'' в системе из n или менее процессов: он может быть использован для построения линеаризуемой реализации любого объекта без ожидания.

В 1990 году Чаудхури [4] представила задачу о согласовании k множеств (k-set agreement problem), иногда называемую задачей о нахождении консенсуса для k множеств, которая обобщает задачу достижения консенсуса, позволяя выбирать k или меньше различных значений решения. В частности, консенсусом является задача о согласовании для 1 множества. Вопрос о том, можно ли решить задачу о согласовании k множеств в асинхронных моделях передачи сообщений, оставался открытым в течение нескольких лет, пока три независимые группы исследователей [2, 10, 11] не показали, что такого протокола не существует.