Problem plotkowania w systemach rozproszonych jest następujący. Mamy wykres z wierzchołkami. Każdy wierzchołek ma komunikat który należy wysłać do wszystkich węzłów.
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.
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.
źródło
Odpowiedzi:
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.
źródło
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?
źródło