Консенсус в распределённой системе — различия между версиями
Yeputons (обсуждение | вклад) |
м (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^2$ сообщений. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Текущая версия на 19:15, 4 сентября 2022
| Определение: |
Задача консенсуса: есть N процессов, у каждого есть некие данные — предложение (proposal), они должны выполнить некоторый распределённый алгоритм и прийти к решению (decision). Требуется:
|
Также можно требовать завершение (termination): протокол должен завершиться за конечное время.
Предложение/решение может быть битом, числом, чем-нибудь ещё — это всё друг к другу сводится. Доказательств не было, они очень технические, есть в толстенной книжке Линча. Но нужно примерно понимание, как сводить консенсус на бите к консенсусу на чём-нибудь сложном.
Можно ещё требовать обоснованный консенсус: это когда принятое решение должно совпадать с одним из исходных предложений. Необоснованный консенсус к обоснованному тоже сводится: сначала выбираем лидера (см. ниже), а потом лидер делает обоснованный выбор (если возникают потери сообщений или падения, то всё тухло). Формальное доказательство, опять же, опущено.
Решение при отсутствии отказов
Каждый процесс рассылает всем остальным своё предложение. Каждый процесс ждёт предложения остальных, после чего детерминированной функцией выбирает элемент из множества. У остальных процессов получилось такое же множество, такая же функция, следовательно, такой же результат. Работает даже в асинхронной системе, $N^2$ сообщений.
