Консенсус в распределённой системе
| Определение: |
Задача консенсуса: есть N процессов, у каждого есть некие данные — предложение (proposal), они должны выполнить некоторый распределённый алгоритм и прийти к решению (decision). Требуется:
|
Также можно требовать завершение (termination): протокол должен завершиться за конечное время.
Предложение/решение может быть битом, числом, чем-нибудь ещё — это всё друг к другу сводится. Доказательств не было, они очень технические, есть в толстенной книжке Линча. Но нужно примерно понимание, как сводить консенсус на бите к консенсусу на чём-нибудь сложном.
Можно ещё требовать обоснованный консенсус: это когда принятое решение должно совпадать с одним из исходных предложений. Необоснованный консенсус к обоснованному тоже сводится: сначала выбираем лидера (см. ниже), а потом лидер делает обоснованный выбор (если возникают потери сообщений или падения, то всё тухло). Формальное доказательство, опять же, опущено.
Способы решения
При отсутствии отказов
Каждый процесс рассылает всем остальным своё предложение. Каждый процесс ждёт предложения остальных, после чего детерминированной функцией выбирает элемент из множества. У остальных процессов получилось такое же множество, такая же функция, следовательно, такой же результат.
Сведения
Выбор лидера
Задачи: $n$ процессам требуется за конечное выбрать лидера, при этом все должны прийти к решению, кто именно лидер. Обычно это часть другого алгоритма. Эквивалентно консенсусу (технические подробности доказательств оставлены за кадром).
Сведение: если у нас есть выбор лидера, то консенсус получить легко: выбрали лидера, лидер зафорсировал своё предложение.
Сведение: если у нас есть необоснованный консенсус на битах, то из него можно сделать необоснованный консенсус на натуральных числах от 1 до $n$ (запустив несколько раз алгоритм) и так выбрать номер процесса-лидера.
Замечание: лидер в процессе выборов может упасть, но мы от этого никак не защитимся: нельзя гарантировать состояние системы "сейчас", лидер может с таким же успехом упасть сразу после выборов. Поэтому если лидер падает, то в дальнейшем алгоритме надо это как-то обнаруживать и обрабатывать.
Terminating Reliable Broadcast (TRB)
Один процесс шлёт сообщения всем остальным. Но в отличие от обычного broadcast есть гарантия, что либо все получат и обработают сообщение, либо никто не обработает. А с обычным broadcast часть процессов может упасть и не обработать. Алгоритм должен завершиться за конечное время.
Пример: в обычном broadcast посылающий может упасть в процессе broadcast, тогда часть получателей получит и обработает, а часть даже не узнает. И у получателей нет способа убедиться, что остальные тоже получили сообщение.
На лекции было сказано, что консенсус эквивалентен TRB, а технические детали опущены. Английская Википедия не согласна ("RB is closely related, but not identical, to the fundamental distributed computing problem of consensus."[1]).
Сведение: если есть консенсус, то можно сделать обоснованный консенсус из двух вариантов: "обрабатываем сообщение такое-то" и "не обрабатываем вообще". Тут, строго говоря, нужно ещё накладывать условия вроде "если хотя бы один не обработал, то никто не обработал".
Сведение: если есть TRB, то эмулируем алгоритм при отсутствии отказов: каждый процесс делает TRB своего предложения, в конце все процессы получили одинаковое множество предложений, выбрали из них одно детерминированной функцией.