What can be decided locally without identifiers?
What can be decided locally without identifiers?
复制标题
没有标识符可以在本地决定什么？
DOI：
10.1145/2484239.2484264
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
J. Suomela
中科院分区：
文献类型：
--
作者：
P. Fraigniaud;Mika Göös;Amos Korman;J. Suomela
唯一的节点标识符是否有助于确定网络G是否具有规定的属性P？我们在分布式局部决策的背景下研究这个问题，其目标是通过让每个节点运行一个恒定时间的分布式决策算法来决定G是否具有属性P。在yes实例中，所有节点都应该输出yes，而在no实例中，至少有一个节点应该输出no。
最近，Fraigniaud等人（OPODIS 2012）给出了几个不需要标识符的条件，他们证明了在任何决策问题中都不需要标识符。在目前的工作中，我们反驳的猜想。
更重要的是，我们分析了分布式计算底层模型的两个关键变体：
(B)标识符的大小由输入网络的大小的函数限定，
（B）：标识符是无界的，
(C)节点运行可计算算法，
（C）：节点可以计算任何可能无法计算的函数。
虽然很容易看出在（€ B，€ C）下不需要标识符，但我们表明，在所有其他组合下，当且仅当标识符存在时，才有可以本地决定的属性。
Do unique node identifiers help in deciding whether a network G has a prescribed property P? We study this question in the context of distributed local decision, where the objective is to decide whether G has property P by having each node run a constant-time distributed decision algorithm. In a yes-instance all nodes should output yes, while in a no-instance at least one node should output no.
Recently, Fraigniaud et al. (OPODIS 2012) gave several conditions under which identifiers are not needed, and they conjectured that identifiers are not needed in any decision problem. In the present work, we disprove the conjecture.
More than that, we analyse two critical variations of the underlying model of distributed computing:
(B): the size of the identifiers is bounded by a function of the size of the input network,
(¬B): the identifiers are unbounded,
(C): the nodes run a computable algorithm,
(¬C): the nodes can compute any, possibly uncomputable function.
While it is easy to see that under (¬B, ¬C) identifiers are not needed, we show that under all other combinations there are properties that can be decided locally if and only if identifiers are present.