Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
复制标题
分布式和流式跨越森林计算的最佳下界
DOI：
10.1137/1.9781611975482.111
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Huacheng Yu
中科院分区：
文献类型：
--
作者：
Jelani Nelson;Huacheng Yu
我们在两个不同的模型中显示了跨越森林计算的最佳下限：
*一个人想要一个全动态跨越森林的数据结构，其中更新可以在$ n $顶点的基础集中插入或删除边缘。唯一的允许查询要求一个跨越的森林，数据结构应以一些给定（潜在的）恒定概率$ \ epsilon> 0 $成功回答。我们证明，任何此类数据结构都必须使用$ \ omega（n \ log^3 n）$存储器。
*网络中有一个裁判和$ n $的顶点，共享公共随机性，每个顶点只知道其社区。裁判没有任何输入。每个顶点都会向裁判发送一条消息，裁判然后以恒定概率$ \ epsilon> 0 $计算图形的森林森林。我们证明，平均消息长度必须为$ \ omega（\ log^3 n）$位。
我们的两个下限都是最佳的，具有AGM Sketch [AGM12]提供的匹配上限（即使概率为$ 1-1/\ MATHRM {POLY}（n）$）。此外，对于第一个设置，我们即使对于低故障概率$ \ delta $，只要$ \ delta> 2^{ - n^{1- \ epsilon}} $，我们也会显示最佳下限。
We show optimal lower bounds for spanning forest computation in two different models:
* One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of $n$ vertices. The sole allowed query asks for a spanning forest, which the data structure should successfully answer with some given (potentially small) constant probability $\epsilon>0$. We prove that any such data structure must use $\Omega(n\log^3 n)$ bits of memory.
* There is a referee and $n$ vertices in a network sharing public randomness, and each vertex knows only its neighborhood; the referee receives no input. The vertices each send a message to the referee who then computes a spanning forest of the graph with constant probability $\epsilon>0$. We prove the average message length must be $\Omega(\log^3 n)$ bits.
Both our lower bounds are optimal, with matching upper bounds provided by the AGM sketch [AGM12] (which even succeeds with probability $1 - 1/\mathrm{poly}(n)$). Furthermore, for the first setting we show optimal lower bounds even for low failure probability $\delta$, as long as $\delta > 2^{-n^{1-\epsilon}}$.