Консенсус в распределённой системе

Определение:

Задача консенсуса: есть N процессов, у каждого есть некие данные — предложение (proposal), они должны выполнить некоторый распределённый алгоритм и прийти к решению (decision). Требуется: Согласие (agreement): все не отказавшие (не упавшие навсегда) процессы должны завершиться с решением (decide) и все эти решения должны совпадать. Нетривиальность (non-triviality): должны быть варианты исполнения, приводящие к разным решениям.

Также можно требовать завершение (termination): протокол должен завершиться за конечное время.

Предложение/решение может быть битом, числом, чем-нибудь ещё — это всё друг к другу сводится. Доказательств не было, они очень технические, есть в толстенной книжке Линча. Но нужно примерно понимание, как сводить консенсус на бите к консенсусу на чём-нибудь сложном.

Можно ещё требовать обоснованный консенсус: это когда принятое решение должно совпадать с одним из исходных предложений. Необоснованный консенсус к обоснованному тоже сводится: сначала выбираем лидера (см. ниже), а потом лидер делает обоснованный выбор (если возникают потери сообщений или падения, то всё тухло). Формальное доказательство, опять же, опущено.