złożoność losowych plotek

Problem plotkowania w systemach rozproszonych jest następujący. Mamy wykres $G$ z $n$ wierzchołkami. Każdy wierzchołek ma komunikat który należy wysłać do wszystkich węzłów. $v$ $m_v$

Moje pytanie dotyczy teraz modelu sieci ad-hoc (zakładamy, że węzeł nie ma żadnej wcześniejszej wiedzy na temat topologii sieci, jej stopni wejściowych i wyjściowych oraz zestawu sąsiadów. tylko znajomość każdego węzła jest jego własnym identyfikatorem i całkowitą liczbą węzłów).

Zakładam również, że wszystkie węzły mają dostęp do zegara globalnego i pracują synchronicznie w dyskretnych krokach czasowych zwanych rundami.

Złożoność algorytmu w tym kontekście to liczba rund potrzebnych do ukończenia.

Pamiętam, że istnieje algorytm, który z dużym prawdopodobieństwem rozwiązuje problem plotkowania w rundach . Ale nie mogę już znaleźć odnośnika i zastanawiam się, czy są w tej sprawie nowsze wyniki. $O(n \log ^2 n)$

edytuj zgodnie z rozsądnym komentarzem: w każdej rundzie węzeł może przesłać wiadomość do wszystkich swoich sąsiadów i może odebrać wiadomości od nich. Węzeł otrzyma komunikat w danej rundzie, tylko wtedy, gdy dokładnie jeden z jego sąsiadów transmituje w tej rundzie. W przeciwnym razie nastąpi kolizja i węzeł nie odbierze żadnej wiadomości.

reference-request dc.distributed-comp

— Sylvain Peyronnet
źródło

Chyba zakładasz, że w każdej rundzie każdy węzeł może wysłać wiadomość tylko do jednego sąsiada? W przeciwnym razie problem jest trywialny do rozwiązania w rundach ...

O (n)

$O(n)$

— Jukka Suomela

Oups, zapomniałem o tym wspomnieć, odpowiednio je zredagowałem.

— Sylvain Peyronnet,

Jeśli węzeł otrzymał wiadomości i może przesyłać w jednej rundzie, czy też przesyłane wiadomości są ograniczone do wielkości tylko jednego ładunku?

v

$v$

m_{u}

$m_u$

m_{w}

$m_w$

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

$\{m_v,m_u,m_w\}$

— Warren Schudy,

Czy węzły mogą odróżnić kolizję od nikogo, kto transmituje?

— Warren Schudy,

Czy wykres połączeń jest arbitralnie silnie powiązanym grafem skierowanym?

— Warren Schudy,

Myślę, że odniesieniem, którego szukasz, jest artykuł „Algorytmy nadawcze w sieciach radiowych o nieznanej topologii” Czumaja i Ryttera. Wygląda na to, że ten dokument wprowadza pewne ulepszenia, ale myślę, że zależy to od specyfiki modelu.

— Lew Reyzin
źródło

Tak, tego papieru szukałem. Dziękuję Ci !

— Sylvain Peyronnet

$t$ $2^{-(t \mod \log n)}$

Edycja: nieważne, to nie działa. Na pełnym wykresie wszystkie węzły ostatecznie przerzucałyby te same popularne wiadomości, a wiele wiadomości nigdy nie byłoby odbieranych przez żaden węzeł inny niż źródło. Może byłoby to pomocne, gdyby węzły wolały przesyłać wiadomości, które otrzymywały rzadziej?

— Warren Schudy
źródło