292
правки
Изменения
Новая страница: «Категория:Параллельное программирование == Выбор лидера == Задачи: $n$ процессам требуе…»
[[Категория:Параллельное программирование]]
== Выбор лидера ==
Задачи: $n$ процессам требуется за конечное выбрать лидера, при этом все должны прийти к решению, кто именно лидер.
Обычно это часть другого алгоритма.
Эквивалентно консенсусу (технические подробности доказательств оставлены за кадром).
Сведение: если у нас есть выбор лидера, то консенсус получить легко: выбрали лидера, лидер зафорсировал своё предложение.
Сведение: если у нас есть необоснованный консенсус на битах, то из него можно сделать необоснованный консенсус на натуральных числах от 1 до $n$ (запустив несколько раз алгоритм) и так выбрать номер процесса-лидера.
Замечание: лидер в процессе выборов может упасть, но мы от этого никак не защитимся: нельзя гарантировать состояние системы "сейчас", лидер может с таким же успехом упасть сразу после выборов.
Поэтому если лидер падает, то в дальнейшем алгоритме надо это как-то обнаруживать и обрабатывать.
== Terminating Reliable Broadcast (TRB) ==
Один процесс шлёт сообщения всем остальным.
Но, в отличие от обычного broadcast, есть гарантия, что либо все получат и обработают сообщение, либо никто не обработает (например, если кто-то упал, то никто не обработает).
А с обычным broadcast часть процессов может упасть и не обработать.
Алгоритм должен завершиться за конечное время.
Пример: в обычном broadcast посылающий может упасть в процессе broadcast, тогда часть получателей получит и обработает, а часть даже не узнает.
И у получателей нет способа убедиться, что остальные тоже получили сообщение.
При этом результат [[Теорема Фишера-Линча-Патерсона (FLP)|FLP]] о невозможности консенсуса верен даже если процессу разрешено делать операцию «атомарной передачи» сообщения сразу несколько процессам, ибо нет гарантии что все процессы обработают его (может, кто-то упал).
На лекции было сказано, что консенсус эквивалентен TRB, а технические детали опущены.
Английская Википедия не согласна ("RB is closely related, but not identical, to the fundamental distributed computing problem of consensus."<ref>https://en.wikipedia.org/wiki/Terminating_Reliable_Broadcast</ref>).
Сведение: если есть консенсус, то можно сделать обоснованный консенсус из двух вариантов: "обрабатываем сообщение такое-то" и "не обрабатываем вообще".
Тут, строго говоря, нужно ещё накладывать условия вроде "если хотя бы один не обработал, то никто не обработал".
Сведение: если есть TRB, то эмулируем алгоритм при отсутствии отказов: каждый процесс делает TRB своего предложения, в конце все процессы получили одинаковое множество предложений, выбрали из них одно детерминированной функцией.
== Выбор лидера ==
Задачи: $n$ процессам требуется за конечное выбрать лидера, при этом все должны прийти к решению, кто именно лидер.
Обычно это часть другого алгоритма.
Эквивалентно консенсусу (технические подробности доказательств оставлены за кадром).
Сведение: если у нас есть выбор лидера, то консенсус получить легко: выбрали лидера, лидер зафорсировал своё предложение.
Сведение: если у нас есть необоснованный консенсус на битах, то из него можно сделать необоснованный консенсус на натуральных числах от 1 до $n$ (запустив несколько раз алгоритм) и так выбрать номер процесса-лидера.
Замечание: лидер в процессе выборов может упасть, но мы от этого никак не защитимся: нельзя гарантировать состояние системы "сейчас", лидер может с таким же успехом упасть сразу после выборов.
Поэтому если лидер падает, то в дальнейшем алгоритме надо это как-то обнаруживать и обрабатывать.
== Terminating Reliable Broadcast (TRB) ==
Один процесс шлёт сообщения всем остальным.
Но, в отличие от обычного broadcast, есть гарантия, что либо все получат и обработают сообщение, либо никто не обработает (например, если кто-то упал, то никто не обработает).
А с обычным broadcast часть процессов может упасть и не обработать.
Алгоритм должен завершиться за конечное время.
Пример: в обычном broadcast посылающий может упасть в процессе broadcast, тогда часть получателей получит и обработает, а часть даже не узнает.
И у получателей нет способа убедиться, что остальные тоже получили сообщение.
При этом результат [[Теорема Фишера-Линча-Патерсона (FLP)|FLP]] о невозможности консенсуса верен даже если процессу разрешено делать операцию «атомарной передачи» сообщения сразу несколько процессам, ибо нет гарантии что все процессы обработают его (может, кто-то упал).
На лекции было сказано, что консенсус эквивалентен TRB, а технические детали опущены.
Английская Википедия не согласна ("RB is closely related, but not identical, to the fundamental distributed computing problem of consensus."<ref>https://en.wikipedia.org/wiki/Terminating_Reliable_Broadcast</ref>).
Сведение: если есть консенсус, то можно сделать обоснованный консенсус из двух вариантов: "обрабатываем сообщение такое-то" и "не обрабатываем вообще".
Тут, строго говоря, нужно ещё накладывать условия вроде "если хотя бы один не обработал, то никто не обработал".
Сведение: если есть TRB, то эмулируем алгоритм при отсутствии отказов: каждый процесс делает TRB своего предложения, в конце все процессы получили одинаковое множество предложений, выбрали из них одно детерминированной функцией.
