Local Distributed Decision
Local Distributed Decision
复制标题
局部分布式决策
DOI：
10.1109/focs.2011.17
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
P. Fraigniaud;Amos Korman;D. Peleg
分布式网络算法中的一个中心主题涉及理解和处理局部性问题。尽管取得了相当大的进展，在这个方向上的研究工作还没有导致一个坚实的基础，在一个基本的计算复杂性理论的地方。受序贯复杂性理论的启发，本文研究了分布式决策问题的复杂性理论.在局部性的上下文中，解决决策问题需要处理器独立地检查它们的局部邻域，然后共同决定给定的全局输入实例是否属于某个指定的语言。我们考虑标准的$\cal{t}$计算模型，并将$LD（t）$（用于{\em local decision}）定义为可以在$t$通信轮中解决的决策问题类。我们首先研究随机化是否有助于本地分布式计算，以及在何种程度上有趣的问题。具体来说，我们定义了相应的随机类$BPLD（t，p，q）$，包含所有的语言，存在一个随机算法，运行在$t$轮，接受正确的实例的概率至少$p$和拒绝不正确的概率至少$q$。我们证明了$p^2+q = 1$是$LD（t）$包含在$BPLD（t，p，q）$中的阈值。更准确地说，我们证明了存在一种语言，它对于任何t=o（n）$都不属于$LD（t）$，但对于任何p，q\in（0，1]$都属于$BPLD（0，p，q）$，使得$p^2+q\leq 1$。另一方面，我们证明了，仅限于遗传语言，对于任意函数t和任意p，q\in（0，1]$，使得p^2 +q>，1$，$BPLD（t，p，q）= LD（O（t））$.此外，我们还研究了非确定性对局部决策的影响，并建立了一些受经典计算复杂性理论启发的结构性结果。具体来说，我们表明，非决定论确实有帮助，但这种帮助是有限的，因为存在的语言，不能决定非决定论。也许令人惊讶的是，事实证明，正是随机化与非确定性的结合，才能在恒定的时间内决定所有语言。最后，我们引入了局部约简的概念，并建立了一些完备性结果。
A central theme in distributed network algorithms concerns understanding and coping with the issue of {\em locality}. Despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a fundamental computational complexity theory for locality. Inspired by sequential complexity theory, we focus on a complexity theory for \emph{distributed decision problems}. In the context of locality, solving a decision problem requires the processors to independently inspect their local neighborhoods and then collectively decide whether a given global input instance belongs to some specified language. We consider the standard $\cal{LOCAL}$ model of computation and define $LD(t)$ (for {\em local decision}) as the class of decision problems that can be solved in $t$ communication rounds. We first study the intriguing question of whether randomization helps in local distributed computing, and to what extent. Specifically, we define the corresponding randomized class $BPLD(t,p,q)$, containing all languages for which there exists a randomized algorithm that runs in $t$ rounds, accepts correct instances with probability at least $p$ and rejects incorrect ones with probability at least $q$. We show that $p^2+q = 1$ is a threshold for the containment of $LD(t)$ in $BPLD(t,p,q)$. More precisely, we show that there exists a language that does not belong to $LD(t)$ for any $t=o(n)$ but does belong to $BPLD(0,p,q)$ for any $p,q\in (0,1]$ such that $p^2+q\leq 1$. On the other hand, we show that, restricted to hereditary languages, $BPLD(t,p,q) = LD(O(t))$, for any function $t$ and any $p,q\in (0,1]$ such that $p^2+q>, 1$. In addition, we investigate the impact of non-determinism on local decision, and establish some structural results inspired by classical computational complexity theory. Specifically, we show that non-determinism does help, but that this help is limited, as there exist languages that cannot be decided non-deterministically. Perhaps surprisingly, it turns out that it is the combination of randomization with non-determinism that enables to decide \emph{all} languages \emph{in constant time}. Finally, we introduce the notion of local reduction, and establish some completeness results.