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

Question

[Сергей Соколов]

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

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

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

Какой алгоритм / протокол решает такую задачу? С требованиями:

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

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

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

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

Как называется, что почитать, как решать задачу такого типа?

Comments

[Akina]

Как я понимаю, есть смысл к этому сообщению хранить дополнительно список ботов, которые извещены.

То есть бот получает сообщение изначально, формирует пустой список и добавляет в него себя.

Далее - обнаружив соседа, бот высылает ему сообщение вместе со списком, а в список в своей копии добавляет номер этого соседа, если он там отсутствует. Если обнаружится ещё один сосед - ему уйдёт сообщение со списком из 2 ботов, а локально список станет содержать три бота. И так далее.

Если от соседа получено сообщение с неким списком, производится проверка, что это сообщение уже имеется. Если нет - успокоились, добавляем в список себя и ищем других соседей. Если сообщение уже имеется - выполняется сверка списков. Если в локальном списке есть хотя бы один узел, отсутствующий в присланном, кроме себя и соседа - списки сливаются и выполняется отсылка сообщения этому соседу с обновлённым списком.

минимизировать избыточные транзакции

Проблема в том, что, как я понимаю, невозможно прогнозировать сеансы связи с соседями. Равно как и невозможно предсказать, даже если и сам бот, и этот сосед есть в списке, не обновился ли список у соседа... не вижу путей к оптимизации.

прекратить попытки передачи, когда сообщение получено всеми

Ну если у ботов имеется полный список ботов системы, то это возможно - по описанной методике выполняется новый цикл распространения, но на сей раз каждый адресат помечается признаком, что ему отослан полный список. И рассылка выполняется только тем соседям, у кого нет такой пометки.

А если список ботов неизвестен или динамический - то без шансов. Только ждать, пока сообщение прокиснет, и его можно будет дропнуть.

[Владимир Коротенко]

пусть будет
структура

uid
timestamp
message

отправленные сообщения

uid
botid
status

протокол взаимодействия
HELLO - вызывается при обнаружении бота
отдает список не переданных идентификаторов сообщений
ответ TRANSFER
после этого прилетает GET UID
на что должна быть передача тела сообщения
в отправленные сообщения вставляется пометка
после сеанс закрывается

Возможно нужна будет табличка для ближайших соседей. И несколько комманд для передачи сообщений

[Сергей Соколов]

Akina, да, вырисовывается решение!

невозможно прогнозировать сеансы связи с соседями

Тут можно считать операцию "узнать только id" ближайшего соседа — «дешевой», а вот обмен списками – «дорогим». Тогда вполне. Ну ещё можно вероятности прикрутить — чем полнее свой список, тем может, реже начать «общаться»? Не факт, правда, что это выигрышная стратегия. Надо ещё подумать, что ценнее: охватить всех-всех, или же снизить шум ложных проверок.

[Akina]

Сергей Соколов,

Тут можно считать операцию "узнать только id" ближайшего соседа — «дешевой», а вот обмен списками – «дорогим». Тогда вполне.

А что это даст? я же говорил:

невозможно предсказать, даже если и сам бот, и этот сосед есть в списке, не обновился ли список у соседа...

То есть даже если дешёвая операция дала ID, который есть в списке - обмен всё равно нужен. Ведь в списке могли появиться боты, которых не было при "том" обмене. Хотя... если хранить и штамп времени оповещения "соседа"...

[Сергей Соколов]

Akina, да, обмен парой id:timestamp можно считать дешёвым, а таблицами – дорогим.

Что думаете насчёт вероятностного снижения частоты диалогов?

[Akina]

Сергей Соколов, ничего не думаю. Тут всё зависит от "важности". Что приоритетнее - снижение нагрузки на трафик (или имеющееся ограничение) или максимальное распространение сообщения.

В любом случае, не вижу ничего умнее рандома, применяемого только в случае, если сосед уже присутствует в списке (при отсутствии - безусловная передача) и регулируемого, например, соотношением количества оповещённых соседей до него и после, или, при наличии сведений об общем количестве ботов, соотношением количества оповещённых после и количества отсутствующих в списке.

И вообще, что-то сильно сомневаюсь в осмысленности такого регулирования...

Answer 1

[Wataru]

Это называется Delay Tolerant Networking.

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