ТЕХНИЧЕСКОЕ ЗАДАНИЕ: Реализовать leader election для агентов (алгоритм Bully)

1. Цель задачи

Разработать систему multi-agent координации, в которой несколько агентов (процессов) динамически выбирают лидера с использованием алгоритма Bully. При отказе текущего лидера должна автоматически запускаться процедура перевыборов, гарантирующая, что новый лидер будет избран в течение ограниченного времени. Ключевой результат работающая симуляция кластера из 3-5 агентов, в которой при ручном «убийстве» лидера происходит переизбрание не более чем за 5 секунд, и все агенты консистентно признают нового лидера.

2. Исходные данные

Если нет реального инструмента — симулируем:

1. Все агенты запускаются в одном процессе Python, каждый как asyncio.Task.
2. Для эмуляции сети используем asyncio.Queue для каждого агента (inbox).
3. Отказ лидера симулируется остановкой его задачи (или вызовом task.cancel()).
4. Состояние агентов (роль, текущий лидер) хранится в атрибутах класса агента.

3. Технологический стек

4. Этапы выполнения

Этап 1: Базовая архитектура агента (1,5 часа)

Действия

1. Создать файл agent.py с классом BullyAgent.
2. Определить константы:

   IDLE = 0
   ELECTION = 1
   COORDINATOR_SENT = 2
   

3. Реализовать конструктор с параметрами:
   • agent_id (int, уникальный)
   • total_agents (int)
   • inbox (asyncio.Queue)
   • peers_inboxes (list of asyncio.Queue)
   • heartbeat_interval (float, по умолчанию 1.0)
   • election_timeout (float, по умолчанию 2.0)
4. Добавить атрибуты состояния:
   • state (текущая фаза: IDLE, ELECTION, COORDINATOR_SENT)
   • leader_id (int или None)
   • is_leader (bool)
5. Реализовать метод send_message(target_id, message_type, payload) — кладёт словарь в очередь получателя.
6. Реализовать метод handle_message(message) — диспетчер по message_type (пока заглушка).

Ожидаемый результат этапа
Файл agent.py с классом, готовым к приёму и отправке сообщений, инициализацией состояния, без логики выборов.

Этап 2: Реализация протокола Bully (2,5 часа)

Действия

1. Реализовать обработку сообщений:
   • ELECTION: отправить OK всем с большим ID, дождаться ответов.
   • OK: отмечать голосование, не начинать выборы повторно.
   • COORDINATOR: обновить leader_id, переключиться на IDLE.
2. Реализовать метод start_election():
   • Отправить ELECTION всем агентам с id > self.agent_id.
   • Запустить таймер ожидания election_timeout.
   • Если получен хотя бы один OK — не становиться лидером (ждать COORDINATOR).
   • Если таймер истёк без OK — объявить себя лидером (send_coordinator).
3. Реализовать метод send_coordinator():
   • Отправить COORDINATOR всем агентам меньшего ID.
   • Установить leader_id = self.agent_id, is_leader = True.

Ожидаемый результат этапа
Агент корректно инициирует выборы, реагирует на сообщения, и при отсутствии более высоких ID становится лидером.

Этап 3: Heartbeat и обнаружение отказа лидера (1,5 часа)

Действия

1. Добавить фоновую задачу heartbeat_sender (только для лидера):
   • Каждые heartbeat_interval отправлять HEARTBEAT всем не-лидерам.
2. Для не-лидеров: фоновую задачу heartbeat_listener.
   • Если HEARTBEAT не получен в течение 2 * heartbeat_interval, считать лидера упавшим и запустить start_election().
3. Реализовать обработку HEARTBEAT — сброс таймера.
4. Добавить методы start() и stop() для запуска/остановки фоновых задач.

Ожидаемый результат этапа
При остановке задачи лидера (например, task.cancel()) другие агенты запускают выборы в течение заданного таймаута.

Этап 4: Интеграционное тестирование и сценарий падения лидера (1,5 часа)

Действия

1. Создать файл test_bully.py с функцией test_cluster().
2. Реализовать симуляцию на 5 агентах:

   async def test_cluster():
       n = 5
       queues = [asyncio.Queue() for _ in range(n)]
       agents = []
       for i in range(n):
           peers = [q for j, q in enumerate(queues) if j != i]
           agent = BullyAgent(i, n, queues[i], peers)
           agents.append(agent)
       tasks = [asyncio.create_task(a.run()) for a in agents]
       # дать время на выборы
       await asyncio.sleep(3)
       # проверить, что избран лидер (самый высокий id, т.е. 4)
       assert all(a.leader_id == 4 for a in agents if not a.is_leader)
       # убить лидера (агента 4)
       tasks[4].cancel()
       await asyncio.sleep(5)
       # проверить, что новый лидер — агент 3 (следующий по id)
       assert all(a.leader_id == 3 for a in agents if not a.is_leader and a.agent_id != 4)
   

3. Запустить тест и убедиться, что assert'ы проходят.

Ожидаемый результат этапа
Автоматический тест, подтверждающий перевыборы при падении лидера.

Этап 5: Документация и оптимизация (1 час)

Действия

1. Написать README.md с описанием архитектуры, инструкцией по запуску и результатами тестов.
2. Добавить логирование в каждом агенте: logging.info(f"Agent {id}: received {msg}").
3. Опционально: визуализировать последовательность выборов с помощью matplotlib и networkx.

Ожидаемый результат этапа
Готовый репозиторий с кодом, тестами, документацией и (опционально) графиком выборов.

5. Критерии приемки (Definition of Done)

• Код агента реализует алгоритм Bully с сообщениями ELECTION, OK, COORDINATOR и HEARTBEAT.
• При старте кластера (все агенты запускаются одновременно) в течение 3 секунд формируется консенсусный лидер (агент с максимальным ID).
• При принудительном завершении задачи лидера другие агенты замечают отсутствие heartbeat и запускают выборы.
• Новый лидер избирается не более чем за 2 * heartbeat_interval + election_timeout (в сумме ≤5 сек).
• Все агенты (включая нового лидера) консистентно обновляют leader_id.
• Написаны минимум два автоматических теста (pytest-asyncio): первый — стартовые выборы, второй — перевыборы после падения.
• Код покрыт логированием ключевых событий (начало выборов, получение OK, объявление лидера).
• Репозиторий содержит README.md и requirements.txt.

6. Ожидаемый результат

Основной артефакт

• agent.py — реализация класса BullyAgent.
• test_bully.py — интеграционные тесты.
• requirements.txt — зависимости (только pytest-asyncio для тестов).
• README.md — описание решения и инструкция по запуску.

Содержание agent.py

• Полная логика Bully с heartbeat.
• Асинхронный цикл обработки сообщений.
• Фоновые задачи для heartbeat (лидер) и timeout (не-лидеры).

Дополнительные результаты (опционально):

• visualize.py — скрипт для отрисовки графа лидерства (сеть агентов, выделен лидер).
• bully_diagram.png — пример диаграммы последовательности выборов.

7. Возможные сложности и их решение

8. Бюджет времени (оценка)

Примечание: Для начинающих с асинхронным программированием время может увеличиться до 12 часов — рекомендуется выделить запас.

9. Связанные вопросы из базы знаний

10. Чек-лист самопроверки

• Я прочитал описание алгоритма Bully и понимаю, как он должен работать.
• Я написал класс агента с обработчиками ELECTION, OK, COORDINATOR и HEARTBEAT.
• Я реализовал таймеры для heartbeat (только лидер) и для обнаружения падения лидера (остальные).
• Я протестировал сценарий с 3-5 агентами, убив лидера и проверив, что за 5 секунд лидер меняется.
• Я проверил, что после перевыборов все агенты ссылаются на один и тот же leader_id.
• Я написал автоматический тест и убедился, что он проходит без ошибок.
• Я задокументировал, как запустить симуляцию и интерпретировать логи.