Введение
В распределенных вычислениях алгоритм "булли" — это метод динамического избрания координатора или лидера из группы распределенных компьютерных процессов. Процесс с наибольшим номером идентификатора из числа процессов, не завершивших работу, выбирается в качестве координатора.
Безопасность
Ожидаемым свойством безопасности протоколов выбора лидера является то, что каждый неисправный процесс либо выбирает процесс в качестве лидера, либо не выбирает никого вообще. Важно отметить, что все процессы, выбравшие лидера, должны прийти к согласию относительно одного и того же процесса как лидера. Алгоритм Bully удовлетворяет этому свойству (в рамках указанной модели системы), и в любой момент времени два процесса в группе не могут иметь противоречивых представлений о том, кто является лидером, за исключением периода проведения выборов. Это верно, поскольку если бы это было не так, существовали бы два процесса, P и Q, которые оба отправили сообщение Координатору (о победе) группе. Это означает, что P и Q также должны были отправить друг другу сообщения о победе. Однако это невозможно, поскольку до отправки сообщения о победе между ними должны были быть обменены сообщения о выборах, и процесс с меньшим идентификатором процесса из этих двух никогда бы не отправил сообщение о победе. Мы приходим к противоречию, и, следовательно, наше первоначальное предположение о том, что в системе в любой момент времени может быть два лидера, неверно. Это доказывает безопасность алгоритма Bully.
a conflicting view of who the leader is, except during an election. This is true because if it weren't, there are two processes and such that both sent the Coordinator (victory) message to the group. This means and must also have sent each other victory messages. But this cannot happen, since before sending the victory message, Election messages would have been exchanged between the two, and the process with a lower process ID among the two would never send out victory messages. We have a contradiction, and hence our initial assumption that there are two leaders in the system at any given time is false, and that shows that the bully algorithm is safe.
Живость
Живость также гарантируется в синхронной модели восстановления после сбоев. Рассмотрим ситуацию, когда потенциальный лидер выходит из строя после отправки сообщения "Ответ (Жив)", но до отправки сообщения "Координатор (победа)". Если он не восстанавливается до истечения тайм-аута, установленного для процессов с меньшими идентификаторами, один из них в конечном итоге станет лидером (даже если некоторые другие процессы выйдут из строя). Если вышедший из строя процесс восстанавливается вовремя, он просто отправляет сообщение "Координатор (победа)" всей группе.
Использование полосы пропускания сети
Предполагая, что сообщения алгоритма выбора лидера имеют фиксированные (известные, инвариантные) размеры, наибольшее количество сообщений обменивается в группе, когда процесс с наименьшим идентификатором инициирует выборы. Этот процесс отправляет (N-1) сообщений о выборах, следующий по величине идентификатор отправляет (N-2) сообщений и так далее, что приводит к сообщениям о выборах. Также есть сообщения Alive и сообщения координатора, таким образом, общее количество сообщений, обмененных в худшем случае, составляет .