Randomized proof-labeling schemes
Randomized proof-labeling schemes
复制标题
DOI：
10.1007/s00446-018-0340-8
复制
发表时间：
2019-06-01
影响因子：
1.3
通讯作者：
Perry, Mor
中科院分区：
文献类型：
--
作者：
Fraigniaud, Pierre;Patt-Shamir, Boaz;Perry, Mor
由Korman等人（Distrib Comput 22（4）：215-233，2010. 10.1007/s 00446 -010-0095-3）是一种证明网络配置满足给定布尔谓词的机制。这种机制在许多情况下都有应用，例如，容错分布式算法的设计。在证明标记方案中，谓词验证由邻居交换标记组成，其内容取决于谓词。在本文中，我们介绍了随机证明标签计划的概念，其中消息是随机的，正确性是概率的。我们表明，随机化降低验证的复杂性指数，同时保证概率的正确性任意接近1。我们还提出了一种新的消息大小下限技术，适用于确定性以及随机证明标签计划。使用这种技术，我们建立了几个严格的界限上的验证复杂性MST，非循环性，连通性，最长的周期大小。
Proof-labeling schemes, introduced by Korman et al. (Distrib Comput 22(4):215-233, 2010. 10.1007/s00446-010-0095-3), are a mechanism to certify that a network configuration satisfies a given boolean predicate. Such mechanisms find applications in many contexts, e.g., the design of fault-tolerant distributed algorithms. In a proof-labeling scheme, predicate verification consists of neighbors exchanging labels, whose contents depends on the predicate. In this paper, we introduce the notion of randomized proof-labeling schemes where messages are randomized and correctness is probabilistic. We show that randomization reduces verification complexity exponentially while guaranteeing probability of correctness arbitrarily close to one. We also present a novel message-size lower bound technique that applies to deterministic as well as randomized proof-labeling schemes. Using this technique, we establish several tight bounds on the verification complexity of MST, acyclicity, connectivity, and longest cycle size.