1632
правки
Изменения
м
== Сведения ===== Выбор лидера === Задачи: $n$ процессам требуется за конечное выбрать лидера, при этом все должны прийти к решению, кто именно лидер.Обычно это часть другого алгоритма.Эквивалентно консенсусу (технические подробности доказательств оставлены за кадром). Сведение: если у нас есть выбор лидера, то консенсус получить легко: выбрали лидера, лидер зафорсировал Каждый процесс рассылает всем остальным своё предложение. Сведение: если у нас есть необоснованный консенсус на битахКаждый процесс ждёт предложения остальных, то после чего детерминированной функцией выбирает элемент из него можно сделать необоснованный консенсус на натуральных числах от 1 до $n$ (запустив несколько раз алгоритм) и так выбрать номер процесса-лидерамножества. Замечание: лидер в процессе выборов может упастьУ остальных процессов получилось такое же множество, такая же функция, но мы от этого никак не защитимся: нельзя гарантировать состояние системы "сейчас"следовательно, лидер может с таким такой же успехом упасть сразу после выбороврезультат.Поэтому если лидер падает, то Работает даже в дальнейшем алгоритме надо это как-то обнаруживать и обрабатывать. === Terminating Reliable Broadcast (TRB) === Отличие TRB от обычного broadcast: часть может получить и обработатьасинхронной системе, а посылающий упал.У других нет гарантий про то, получили ли остальные сообщения$N^2$ сообщений.
rollbackEdits.php mass rollback
[[Категория:Параллельное программирование]]
{{Определение
|definition=
'''Задача консенсуса''': есть N процессов, у каждого есть некие данные — предложение (proposal), они должны выполнить некоторый распределённый алгоритм и прийти к решению (decision). Требуется:
* Согласие (agreement): все не отказавшие (не упавшие навсегда) процессы должны завершиться с решением (decide) и все эти решения должны совпадать.
* Нетривиальность (non-triviality): должны быть варианты исполнения, приводящие к разным решениям(возможно, просто с разными исходными предложениями или разным исходным состоянием процессов).
}}
Также можно требовать завершение (termination): протокол должен завершиться за конечное время.
Формальное доказательство, опять же, опущено.
== Способы решения ===== При Решение при отсутствии отказов ===
