论文标题
混合模型中的路由方案和距离甲壳
Routing Schemes and Distance Oracles in the Hybrid Model
论文作者
论文摘要
$ \ Mathsf {Hybrid} $模型是作为使用各种通信模式的分布式网络的理论研究的一种手段。从概念上讲，这是一个具有本地通信模式的同步消息传递模型，在每个回合中，每个节点都可以在本地网络（图）和一个全局通信模式中向其所有邻居发送大消息，每个节点都被分配有限（polyrogarithmic）每轮带宽（polylogarithmic）带宽，它可以用来与网络中的任何一个网络通信。 先前的工作通常集中在本地网络中的最短路径问题上，因为它们的全球性质使这些有趣的案例研究如何在$ \ Mathsf {hybrid} $模型中结合通信模式如何克服两种模式的单个下限。在这项工作中，我们考虑了一个类似的问题，即距离甲壳和路由方案的计算。在前者中，所有节点都必须计算本地表，这使他们可以在提供目标标签时查找本地网络中任何目标节点的距离（估计）。在后者中，节点在（大约）最短的目标路径上给出下一个节点就足够了。 我们的目标是用尽可能小的标签尽可能快地计算这些本地表。我们表明，可以在$ \ widetilde o（n^{1/3}）$通信弹和大小$θ（n^{2/3}）$ bits的标签中精确地完成此操作。对于恒定的拉伸近似值，我们同时获得了$ o（\ log n）$的标签。此外，作为我们的主要技术贡献，我们为各种问题参数提供了计算下限。例如，我们表明，延伸以下的计算解决方案以$ \ widetildeω（n^{1/3}）$ rounds为$ o（n^{2/3}）$，即
The $\mathsf{HYBRID}$ model was introduced as a means for theoretical study of distributed networks that use various communication modes. Conceptually, it is a synchronous message passing model with a local communication mode, where in each round each node can send large messages to all its neighbors in a local network (a graph), and a global communication mode, where each node is allotted limited (polylogarithmic) bandwidth per round which it can use to communicate with any node in the network. Prior work has often focused on shortest paths problems in the local network, as their global nature makes these an interesting case study how combining communication modes in the $\mathsf{HYBRID}$ model can overcome the individual lower bounds of either mode. In this work we consider a similar problem, namely computation of distance oracles and routing schemes. In the former, all nodes have to compute local tables, which allows them to look up the distance (estimates) to any target node in the local network when provided with the label of the target. In the latter, it suffices that nodes give the next node on an (approximately) shortest path to the target. Our goal is to compute these local tables as fast as possible with labels as small as possible. We show that this can be done exactly in $\widetilde O(n^{1/3})$ communication rounds and labels of size $Θ(n^{2/3})$ bits. For constant stretch approximations we achieve labels of size $O(\log n)$ in the same time. Further, as our main technical contribution, we provide computational lower bounds for a variety of problem parameters. For instance, we show that computing solutions with stretch below a certain constant takes $\widetilde Ω(n^{1/3})$ rounds even for labels of size $O(n^{2/3})$.
