292
правки
Изменения
→Выбор лидера
=== Выбор лидера ===
Задачи: $n$ процессам требуется за конечное выбрать лидера, при этом все должны прийти к решению, кто именно лидер.Обычно это часть другого алгоритма.Эквивалентно консенсусу (технические подробности доказательств оставлены за кадром).
Сведение: если у нас есть выбор лидера, то консенсус получить легко: выбрали лидера, через него договорилисьлидер зафорсировал своё предложение.
Сведение: если у нас есть необоснованный консенсус на битах, то из него можно сделать необоснованный консенсус на натуральных числах от 1 до $n$ (запустив несколько раз алгоритм) и так выбрать номер процесса-лидера.
