We introduce collision free layerings as a powerful way to structure radio networks. These layerings can replace hard-to-compute BFS-trees in many contexts while having an efficient randomized distributed construction. We demonstrate their versatility by using them to provide near optimal distributed algorithms for several multi-message communication primitives. Designing efficient communication primitives for radio networks has a rich history that began 25 years ago when Bar-Yehuda et al. introduced fast randomized algorithms for broadcasting and for constructing BFS-trees. Their BFS-tree construction time was O(D log~2 n) rounds, where D is the network diameter and n is the number of nodes. Since then, the complexity of a broadcast has been resolved to be T_(BC) = θ(D log n/D + log~2 n) rounds. On the other hand, BFS-trees have been used as a crucial building block for many communication primitives and their construction time remained a bottleneck for these primitives. We introduce collision free layerings that can be used in place of BFS-trees and we give a randomized construction of these layerings that runs in nearly broadcast time, that is, w.h.p. in T_(Lay) = O(D log n/D + log~(2+ε) n) rounds for any constant ε ＞ 0. We then use these layerings to obtain: (1) A randomized algorithm for gathering k messages running w.h.p. in O(T_(Lay) + k) rounds. (2) A randomized k-message broadcast algorithm running w.h.p. in O(T_(Lay) + k log n) rounds. These algorithms are optimal up to the small difference in the additive poly-logarithmic term between T_(BC) and T_(Lay) Moreover, they imply the first optimal O(n log n) round randomized gossip algorithm.
展开▼
机译：我们引入无冲突分层作为构建无线电网络的有力方法。这些分层可以在许多情况下替换难以计算的BFS树，同时具有有效的随机分布结构。通过使用它们为几种多消息通信原语提供接近最佳的分布式算法，我们证明了它们的多功能性。为无线电网络设计有效的通信原语已有25年的悠久历史，当时Bar-Yehuda等人（美国）引入了用于广播和构建BFS树的快速随机算法。它们的BFS树构建时间为O（D log〜2 n）轮，其中D是网络直径，n是节点数。从那时起，广播的复杂度已解决为T_（BC）=θ（D log n / D + log〜2 n）次。另一方面，BFS树已被用作许多通信原语的关键构建块，而它们的构建时间仍然是这些原语的瓶颈。我们介绍了可用于代替BFS树的无冲突分层，并给出了这些分层的随机构造，该构造在几乎广播时间即w.h.p中运行。在T_（Lay）= O（D log n / D + log〜（2 +ε）n）中对任意常数ε＞ 0进行舍入。然后，我们使用这些分层来获得：（1）一种随机算法，用于收集正在运行的k条消息鞭子在O（T_（Lay）+ k）个回合中。 （2）运行w.h.p的随机k消息广播算法。在O（T_（Lay）+ k log n）个回合中。这些算法是最佳的，直到T_（BC）和T_（Lay）之间的加法对数项之间的微小差异为止。此外，它们暗示了第一个最佳O（n log n）轮随机八卦算法。
展开▼
