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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение при отсутствии отказов)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 4: Строка 4:
 
'''Задача консенсуса''': есть N процессов, у каждого есть некие данные — предложение (proposal), они должны выполнить некоторый распределённый алгоритм и прийти к решению (decision). Требуется:
 
'''Задача консенсуса''': есть N процессов, у каждого есть некие данные — предложение (proposal), они должны выполнить некоторый распределённый алгоритм и прийти к решению (decision). Требуется:
 
* Согласие (agreement): все не отказавшие (не упавшие навсегда) процессы должны завершиться с решением (decide) и все эти решения должны совпадать.
 
* Согласие (agreement): все не отказавшие (не упавшие навсегда) процессы должны завершиться с решением (decide) и все эти решения должны совпадать.
* Нетривиальность (non-triviality): должны быть варианты исполнения, приводящие к разным решениям.
+
* Нетривиальность (non-triviality): должны быть варианты исполнения, приводящие к разным решениям (возможно, просто с разными исходными предложениями или разным исходным состоянием процессов).
 
}}
 
}}
 
Также можно требовать завершение (termination): протокол должен завершиться за конечное время.
 
Также можно требовать завершение (termination): протокол должен завершиться за конечное время.
Строка 22: Строка 22:
 
Каждый процесс ждёт предложения остальных, после чего детерминированной функцией выбирает элемент из множества.
 
Каждый процесс ждёт предложения остальных, после чего детерминированной функцией выбирает элемент из множества.
 
У остальных процессов получилось такое же множество, такая же функция, следовательно, такой же результат.
 
У остальных процессов получилось такое же множество, такая же функция, следовательно, такой же результат.
 +
Работает даже в асинхронной системе, $N^2$ сообщений.

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


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

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

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

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

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

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