[[Категория:Параллельное программирование]]
{{Определение
|definition=
'''Задача консенсуса''': есть N процессов, у каждого есть некие данные — предложение (proposal), они должны выполнить некоторый распределённый алгоритм и прийти к решению (decision). Требуется:
* Согласие (agreement): все не отказавшие (не упавшие навсегда) процессы должны завершиться с решением (decide) и все эти решения должны совпадать.
* Нетривиальность (non-triviality): должны быть варианты исполнения, приводящие к разным решениям(возможно, просто с разными исходными предложениями или разным исходным состоянием процессов).
}}
Также можно требовать завершение (termination): протокол должен завершиться за конечное время.
Формальное доказательство, опять же, опущено.
== Способы решения ===== При Решение при отсутствии отказов ===
Каждый процесс рассылает всем остальным своё предложение.
Каждый процесс ждёт предложения остальных, после чего детерминированной функцией выбирает элемент из множества.
У остальных процессов получилось такое же множество, такая же функция, следовательно, такой же результат.
== Сведения ===== Выбор лидера === Задачи: $n$ процессам требуется за конечное выбрать лидераРаботает даже в асинхронной системе, при этом все должны прийти к решению, кто именно лидер.Обычно это часть другого алгоритма.Эквивалентно консенсусу (технические подробности доказательств оставлены за кадром). Сведение: если у нас есть выбор лидера, то консенсус получить легко: выбрали лидера, лидер зафорсировал своё предложение. Сведение: если у нас есть необоснованный консенсус на битах, то из него можно сделать необоснованный консенсус на натуральных числах от 1 до $nN^2$ (запустив несколько раз алгоритм) и так выбрать номер процесса-лидера. Замечание: лидер в процессе выборов может упасть, но мы от этого никак не защитимся: нельзя гарантировать состояние системы "сейчас", лидер может с таким же успехом упасть сразу после выборов.Поэтому если лидер падает, то в дальнейшем алгоритме надо это как-то обнаруживать и обрабатывать. === Terminating Reliable Broadcast (TRB) ===Один процесс шлёт сообщения всем остальным.Но в отличие от обычного broadcast есть гарантия, что либо все получат и обработают сообщение, либо никто не обработает.А с обычным broadcast часть процессов может упасть и не обработать.Алгоритм должен завершиться за конечное время. Пример: в обычном broadcast посылающий может упасть в процессе broadcast, тогда часть получателей получит и обработает, а часть даже не узнает.И у получателей нет способа убедиться, что остальные тоже получили сообщение. На лекции было сказано, что консенсус эквивалентен TRB, а технические детали опущены.Английская Википедия не согласна ("RB is closely related, but not identical, to the fundamental distributed computing problem of consensus."<ref>https://en.wikipedia.org/wiki/Terminating_Reliable_Broadcast</ref>). Сведение: если есть консенсус, то можно сделать обоснованный консенсус из двух вариантов: "обрабатываем сообщение такое-то" и "не обрабатываем вообще".Тут, строго говоря, нужно ещё накладывать условия вроде "если хотя бы один не обработал, то никто не обработал". Сведение: если есть TRB, то эмулируем алгоритм при отсутствии отказов: каждый процесс делает TRB своего предложения, в конце все процессы получили одинаковое множество предложений, выбрали из них одно детерминированной функциейсообщений.
