Как распространять сообщение в сети независимых агентов?

Вопрос про децентрализацию. Есть независимые автономные агенты == боты. Общие у них только часы и известно каждому общее число ботов в коробке. Нет центрального состояния, менеджера-супервайзора. Действуют «самостоятельно».

Боты перемещаются.
Каждый может коммуницировать в определённом радиусе с соседними: инициировать или принимать запросы. Т.е. образуется граф ближайших соседей nearest neighbor'ов, который меняется по мере движения ботов. Визуализация для вдохновения.

Вот у одного бота оказывается некое Ценное Сообщение, которое нужно распространить по всем ботам сети, от одного другому, в рамках досягаемости очередного.

Какой алгоритм / протокол решает такую задачу? С требованиями:
  1. минимизировать избыточные транзакции: когда отправка сообщения не добавляет к выполнению задачи: бот-получатель уже с Сообщением от другого, или «я» уже отправлял ему.
  2. прекратить попытки передачи, когда сообщение получено всеми
  3. прекратить передачи по истечении опр. времени


Пункт 3 это просто, в самом сообщении держать TTL. Есть у бота сообщение – он его перестанет пытаться слать дальше по истечении времени.

Пункт 2, т.к. нет общего Состояния, требует хождения ещё и служебных сообщений, наверное, обновляющих число получивших сообщение.

Пункт 1 никак наверно? Запоминать, кому отправил - ок. А с остальными только отправлять «А вот Сообщение» – в ответ: «Да знаю я».

Как называется, что почитать, как решать задачу такого типа?
  • Вопрос задан
  • 212 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Это называется Delay Tolerant Networking.

Есть куча статей и конференций на тему. Это активная область исследования и каких-то окончательных ответов тут человечество пока не придумало, но есть куча очень умных алгоримов.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы