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

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

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

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

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

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

Сведения

Выбор лидера

Задачи: $n$ процессам требуется за конечное выбрать лидера, при этом все должны прийти к решению, кто именно лидер. Обычно это часть другого алгоритма. Эквивалентно консенсусу (технические подробности доказательств оставлены за кадром).

Сведение: если у нас есть выбор лидера, то консенсус получить легко: выбрали лидера, лидер зафорсировал своё предложение.

Сведение: если у нас есть необоснованный консенсус на битах, то из него можно сделать необоснованный консенсус на натуральных числах от 1 до $n$ (запустив несколько раз алгоритм) и так выбрать номер процесса-лидера.

Замечание: лидер в процессе выборов может упасть, но мы от этого никак не защитимся: нельзя гарантировать состояние системы "сейчас", лидер может с таким же успехом упасть сразу после выборов. Поэтому если лидер падает, то в дальнейшем алгоритме надо это как-то обнаруживать и обрабатывать.

Terminating Reliable Broadcast (TRB)

Отличие TRB от обычного broadcast: часть может получить и обработать, а посылающий упал. У других нет гарантий про то, получили ли остальные сообщения.