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

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