We consider basic communication tasks in arbitrary radio networks: k-broadcasting and k-gathering. In the case of k-broadcasting, messages from k sources have to get to all nodes in the network. The goal of k-gathering is to collect messages from k source nodes in a designated sink node. We consider these problems in the framework of distributed algorithms with advice. Krisko and Miller showed in 2021 that the optimal size of advice for k-broadcasting is \(\varTheta (\min (\log \varDelta ,\) \( \log k))\) , where \(\varDelta \) is equal to the maximum degree of a vertex of the input communication graph. We show that the same bound \(\varTheta (\min (\log \varDelta , \log k))\) on the size of optimal labeling scheme holds also for the k-gathering problems. Moreover, we design fast algorithms for both problems with asymptotically optimal size of advice. For k-gathering, our algorithm works in at most \(D+k\) rounds, where D is the diameter of the communication graph. This time bound is optimal even for centralized algorithms. We apply the k-gathering algorithm for k-broadcasting to achieve an algorithm working in time \(O(D+\log ^2 n+k)\) rounds. We also exhibit a logarithmic time complexity gap between distributed algorithms with advice of optimal size and distributed algorithms with distinct arbitrary labels.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Optimal-Length Labeling Schemes and Fast Algorithms for k-Gathering and k-Broadcasting

  • Adam Gańczorz,
  • Tomasz Jurdziński

摘要

We consider basic communication tasks in arbitrary radio networks: k-broadcasting and k-gathering. In the case of k-broadcasting, messages from k sources have to get to all nodes in the network. The goal of k-gathering is to collect messages from k source nodes in a designated sink node. We consider these problems in the framework of distributed algorithms with advice. Krisko and Miller showed in 2021 that the optimal size of advice for k-broadcasting is \(\varTheta (\min (\log \varDelta ,\) \( \log k))\) , where \(\varDelta \) is equal to the maximum degree of a vertex of the input communication graph. We show that the same bound \(\varTheta (\min (\log \varDelta , \log k))\) on the size of optimal labeling scheme holds also for the k-gathering problems. Moreover, we design fast algorithms for both problems with asymptotically optimal size of advice. For k-gathering, our algorithm works in at most \(D+k\) rounds, where D is the diameter of the communication graph. This time bound is optimal even for centralized algorithms. We apply the k-gathering algorithm for k-broadcasting to achieve an algorithm working in time \(O(D+\log ^2 n+k)\) rounds. We also exhibit a logarithmic time complexity gap between distributed algorithms with advice of optimal size and distributed algorithms with distinct arbitrary labels.