论文标题
分布式图跨度的本地信息成本
The Local Information Cost of Distributed Graph Spanners
论文作者
论文摘要
我们介绍\ emph {本地信息成本}（LIC），该{LIC）量化了网络中节点在求解图形问题时需要学习的信息量。我们表明，本地信息成本对分布式算法的沟通复杂性具有自然的下限。对于同步的EODEST KT1模型，每个节点都有对其邻居ID的初始知识，我们证明$ω（\ frac {\ frac {\ text {lic}_γ（p）} {\logτ\ log n}）$ bits $ p $ p $ p $与$τ$ the $ the $ - fuls $ ound Algorith所必需。我们的结果是第一个下限，在Electest KT1模型中的沟通和图表问题之间产生一般权衡。 我们通过在计算具有乘法拉伸$ 2T-1 $计算跨度的跨度复杂性的下限制的下限来实现本地信息成本，最多由$ o（n^{1+ \ frac {1} {1} {t} {t} +ε}）$ edges，其中$ε= o（$ε= o（{1}/{1}/{t^2}）$。更具体地说，我们表明任何$ o（\ text {poly}（n））$ - 时间跨度算法必须至少发送$ \tildeΩ（\ tfrac {1} {t^2} {t^2} n^{1+ {1+ {1+{1}/{2t}}}）$ lits $ lits $ lits。以前，$ \tildeΩ（n）$位的微不足道的下限以此问题而闻名。 （有关完整摘要，请参见PDF。）
We introduce the \emph{local information cost} (LIC), which quantifies the amount of information that nodes in a network need to learn when solving a graph problem. We show that the local information cost presents a natural lower bound on the communication complexity of distributed algorithms. For the synchronous CONGEST KT1 model, where each node has initial knowledge of its neighbors' IDs, we prove that $Ω(\frac{\text{LIC}_γ(P)}{\logτ\log n})$ bits are required for solving a graph problem $P$ with a $τ$-round algorithm that errs with probability at most $γ$. Our result is the first lower bound that yields a general trade-off between communication and time for graph problems in the CONGEST KT1 model. We demonstrate how to apply the local information cost by deriving a lower bound on the communication complexity of computing a spanner with multiplicative stretch $2t-1$ that consists of at most $O(n^{1+\frac{1}{t} + ε})$ edges, where $ε= O( {1}/{t^2} )$. More concretely, we show that any $O(\text{poly}(n))$-time spanner algorithm must send at least $\tildeΩ(\tfrac{1}{t^2} n^{1+{1}/{2t}})$ bits. Previously, only a trivial lower bound of $\tilde Ω(n)$ bits was known for this problem. (See PDF for the full abstract.)
