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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 2 участников)
Строка 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) ===
 
 
 
Отличие TRB от обычного broadcast: часть может получить и обработать, а посылающий упал.
 
У других нет гарантий про то, получили ли остальные сообщения.
 

Текущая версия на 19:15, 4 сентября 2022


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

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

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

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

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

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