292
правки
Изменения
Новая страница: «{{Определение |definition= '''Задача консенсуса''': есть N процессов, у каждого есть некие данные…»
{{Определение
|definition=
'''Задача консенсуса''': есть N процессов, у каждого есть некие данные — предложение (proposal), они должны выполнить некоторый распределённый алгоритм и прийти к решению (decision). Требуется:
* Согласие (agreement): все не отказавшие (не упавшие навсегда) процессы должны завершиться с решением (decide) и все эти решения должны совпадать.
* Нетривиальность (non-triviality): должны быть варианты исполнения, приводящие к разным решениям.
}}
Также можно требовать завершение (termination): протокол должен завершиться за конечное время.
Предложение/решение может быть битом, числом, чем-нибудь ещё — это всё друг к другу сводится.
Доказательств не было, они очень технические, есть в толстенной книжке Линча.
Но нужно примерно понимание, как сводить консенсус на бите к консенсусу на чём-нибудь сложном.
Можно ещё требовать '''обоснованный''' консенсус: это когда принятое решение должно совпадать с одним из исходных предложений.
Необоснованный консенсус к обоснованному тоже сводится: сначала выбираем лидера (см. ниже), а потом лидер делает обоснованный выбор
(если возникают потери сообщений или падения, то всё тухло).
Формальное доказательство, опять же, опущено.
== Выбор лидера ==
== Terminating Reliable Broadcast (TRB) ==
|definition=
'''Задача консенсуса''': есть N процессов, у каждого есть некие данные — предложение (proposal), они должны выполнить некоторый распределённый алгоритм и прийти к решению (decision). Требуется:
* Согласие (agreement): все не отказавшие (не упавшие навсегда) процессы должны завершиться с решением (decide) и все эти решения должны совпадать.
* Нетривиальность (non-triviality): должны быть варианты исполнения, приводящие к разным решениям.
}}
Также можно требовать завершение (termination): протокол должен завершиться за конечное время.
Предложение/решение может быть битом, числом, чем-нибудь ещё — это всё друг к другу сводится.
Доказательств не было, они очень технические, есть в толстенной книжке Линча.
Но нужно примерно понимание, как сводить консенсус на бите к консенсусу на чём-нибудь сложном.
Можно ещё требовать '''обоснованный''' консенсус: это когда принятое решение должно совпадать с одним из исходных предложений.
Необоснованный консенсус к обоснованному тоже сводится: сначала выбираем лидера (см. ниже), а потом лидер делает обоснованный выбор
(если возникают потери сообщений или падения, то всё тухло).
Формальное доказательство, опять же, опущено.
== Выбор лидера ==
== Terminating Reliable Broadcast (TRB) ==
