Консенсус в распределённой системе — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Terminating Reliable Broadcast (TRB))
(Решение при отсутствии отказов)
 
(не показано 6 промежуточных версий этого же участника)
Строка 1: Строка 1:
 +
[[Категория:Параллельное программирование]]
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
 
'''Задача консенсуса''': есть N процессов, у каждого есть некие данные — предложение (proposal), они должны выполнить некоторый распределённый алгоритм и прийти к решению (decision). Требуется:
 
'''Задача консенсуса''': есть N процессов, у каждого есть некие данные — предложение (proposal), они должны выполнить некоторый распределённый алгоритм и прийти к решению (decision). Требуется:
 
* Согласие (agreement): все не отказавшие (не упавшие навсегда) процессы должны завершиться с решением (decide) и все эти решения должны совпадать.
 
* Согласие (agreement): все не отказавшие (не упавшие навсегда) процессы должны завершиться с решением (decide) и все эти решения должны совпадать.
* Нетривиальность (non-triviality): должны быть варианты исполнения, приводящие к разным решениям.
+
* Нетривиальность (non-triviality): должны быть варианты исполнения, приводящие к разным решениям (возможно, просто с разными исходными предложениями или разным исходным состоянием процессов).
 
}}
 
}}
 
Также можно требовать завершение (termination): протокол должен завершиться за конечное время.
 
Также можно требовать завершение (termination): протокол должен завершиться за конечное время.
Строка 16: Строка 17:
 
Формальное доказательство, опять же, опущено.
 
Формальное доказательство, опять же, опущено.
  
== Способы решения ==
+
== Решение при отсутствии отказов ==
=== При отсутствии отказов ===
 
  
== Сведения ==
+
Каждый процесс рассылает всем остальным своё предложение.
=== Выбор лидера ===
+
Каждый процесс ждёт предложения остальных, после чего детерминированной функцией выбирает элемент из множества.
 
+
У остальных процессов получилось такое же множество, такая же функция, следовательно, такой же результат.
Задачи: $n$ процессам требуется за конечное выбрать лидера, при этом все должны прийти к решению, кто именно лидер.
+
Работает даже в асинхронной системе, $N^2$ сообщений.
Обычно это часть другого алгоритма.
 
Эквивалентно консенсусу (технические подробности доказательств оставлены за кадром).
 
 
 
Сведение: если у нас есть выбор лидера, то консенсус получить легко: выбрали лидера, лидер зафорсировал своё предложение.
 
 
 
Сведение: если у нас есть необоснованный консенсус на битах, то из него можно сделать необоснованный консенсус на натуральных числах от 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."<ref>https://en.wikipedia.org/wiki/Terminating_Reliable_Broadcast</ref>).
 
 
 
Сведение: если есть консенсус, то можно сделать обоснованный консенсус из двух вариантов: "обрабатываем сообщение такое-то" и "не обрабатываем вообще".
 
Тут, строго говоря, нужно ещё накладывать условия вроде "если хотя бы один не обработал, то никто не обработал".
 
 
 
Сведение: если есть TRB, то эмулируем централизованный алгоритм: каждый процесс делает TRB своего предложения, в конце все процессы получили одинаковое множество предложений, выбрали из них одно детерминированной функцией.
 

Текущая версия на 00:13, 4 июня 2019


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

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

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

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

Решение при отсутствии отказов[править]

Каждый процесс рассылает всем остальным своё предложение. Каждый процесс ждёт предложения остальных, после чего детерминированной функцией выбирает элемент из множества. У остальных процессов получилось такое же множество, такая же функция, следовательно, такой же результат. Работает даже в асинхронной системе, $N^2$ сообщений.