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

Проблема сплетен в распределенных системах заключается в следующем. У нас есть граф с вершинами. Каждая вершина имеет сообщение которое необходимо отправить всем узлам. $G$ $n$ $v$ $m_v$

Теперь мой вопрос в контексте специальной сетевой модели (мы предполагаем, что узел не имеет каких-либо предварительных знаний о топологии сети, степенях входа и выхода и наборе соседей. только знание каждого узла - это его собственный идентификатор и общее количество узлов).

Я также предполагаю, что все узлы имеют доступ к глобальным часам и работают синхронно с дискретными временными шагами, называемыми циклами.

Сложность алгоритма в этом контексте заключается в количестве раундов, необходимых для завершения.

Я помню, что существует алгоритм, который решает проблему сплетен в раундах с высокой вероятностью. Но я больше не могу найти ссылку, и мне интересно, есть ли более свежие результаты по этому вопросу. $O(n \log ^2 n)$

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

reference-request dc.distributed-comp Сильвен Пейроннет
источник

Я предполагаю, что вы предполагаете, что в каждом раунде каждый узел может отправить сообщение только одному соседу? В противном случае задачу тривиально решить за

раундов ...

O (n)

$O(n)$

Юкка Суомела

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

Сильвен Пейроннет

Если узел

получил сообщения

может ли он передать

за один раунд или переданные сообщения ограничены размером только одной полезной нагрузки?

v

$v$

m_{u}

$m_u$

m_{w}

$m_w$

{m_{v}, m_{u}, m_{w}}

$\{m_v,m_u,m_w\}$

Уоррен Шуди

Могут ли узлы определить разницу между коллизией и отсутствием передачи?

Уоррен Шуди

Является ли граф связей произвольным сильно связным ориентированным графом?

Уоррен Шуди

$t$ $2^{-(t \mod \log n)}$ и выбирает сообщение для случайной равномерной передачи из числа сообщений, которые оно получило до сих пор. Может ли это работать?

Изменить: не важно, это не работает. На полном графике все узлы заканчиваются в основном повторной передачей одних и тех же популярных сообщений, и многие сообщения никогда не будут получены ни одним узлом, кроме источника. Может быть, было бы полезно, если бы узлы предпочитали передавать сообщения, которые они получали реже?

Уоррен Шуди
источник

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

Ответы: