论文标题
反应性证明标签方案用于分布式决策
Reactive Proof Labeling Schemes for Distributed Decision
论文作者
论文摘要
我们将证明标签方案的定义推广到反应性系统，即配置应该永远改变的系统。例如，我们解决了反应性任务的主要经典测试案例，即令牌传递的任务。对于假定网络是树或匿名环或一般图的情况，给出了不同的RPLS，并且分析了RPLSS标签的尺寸。我们还解决了是否存在RPL的问题。首先，从积极的一面来看，我们证明了对于具有独特身份的图形家庭的任何分布式任务的RPL。对于匿名网络的情况（即使对于环），有趣的是，即使已知节点的n数n，也可能无法通过令牌传递算法。尽管如此，我们表明RPL是可能的。在负面的一面，我们表明，如果一个人丢弃了n是已知的假设，那么构造就变得不可能。
We generalize the definition of Proof Labeling Schemes to reactive systems, that is, systems where the configuration is supposed to keep changing forever. As an example, we address the main classical test case of reactive tasks, namely, the task of token passing. Different RPLSs are given for the cases that the network is assumed to be a tree or an anonymous ring, or a general graph, and the sizes of RPLSs' labels are analyzed. We also address the question of whether an RPLS exists. First, on the positive side, we show that there exists an RPLS for any distributed task for a family of graphs with unique identities. For the case of anonymous networks (even for the special case of rings), interestingly, it is known that no token passing algorithm is possible even if the number n of nodes is known. Nevertheless, we show that an RPLS is possible. On the negative side, we show that if one drops the assumption that n is known, then the construction becomes impossible.
