On the Impact of Identifiers on Local Decision
On the Impact of Identifiers on Local Decision
复制标题
论标识符对局部决策的影响
DOI：
10.1007/978-3-642-35476-2_16
复制
发表时间：
2012
影响因子：
1.3
通讯作者：
Amos Korman
中科院分区：
文献类型：
--
作者：
P. Fraigniaud;M. Halldórsson;Amos Korman
标识符问题在分布式计算中至关重要。非正式地，身份用于解决确定性分布式计算固有的两个基本困难，即：（1）对称性破缺，以及（2）拓扑信息收集。在本地计算的上下文中，即，当节点只能从有界距离的节点收集信息时，已经建立了关于身份角色的一些见解。例如，它表明，对于大类的建设问题，身份的作用可以相当小。然而，要使恒等式不起作用，就必须采用一些其他类型的对称性破缺机制，如边标记或方向感。当涉及到局部分布式决策问题时，决策任务的规范似乎并不涉及对称性破缺。因此，假设节点可以收集到关于其邻域的足够信息，则可以在不采用额外机制来破坏对称性的情况下摆脱身份。我们在\（\mathcal{n}\）模型的框架中处理这个问题。
The issue of identifiers is crucial in distributed computing. Informally, identities are used for tackling two of the fundamental difficulties that are inherent to deterministic distributed computing, namely: (1) symmetry breaking, and (2) topological information gathering. In the context of local computation, i.e., when nodes can gather information only from nodes at bounded distances, some insight regarding the role of identities has been established. For instance, it was shown that, for large classes of construction problems, the role of the identities can be rather small. However, for the identities to play no role, some other kinds of mechanisms for breaking symmetry must be employed, such as edge-labeling or sense of direction. When it comes to local distributed decision problems, the specification of the decision task does not seem to involve symmetry breaking. Therefore, it is expected that, assuming nodes can gather sufficient information about their neighborhood, one could get rid of the identities, without employing extra mechanisms for breaking symmetry. We tackle this question in the framework of the \(\mathcal{LOCAL}\) model.