Proof labeling schemes
Proof labeling schemes
复制标题
证明标签方案
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
Amos Korman;S. Kutten;D. Peleg
本文解决了本地验证全球属性的问题，例如“本地验证有多昂贵？”根据顶点需要进行交流的位数，对问题进行了研究。为了验证全球财产是否存在）。在证明标签方案的背景下，关于不可能和复杂性的独特身份。验证此配置是否具有一定的所需属性。验证。那就是，它首先生成所需的配置，而无需验证它，然后处理构造合适的验证方案的任务。因此，我们的方法允许对算法进行更模块化的设计，并且即使在没有验证的情况下完成了维护它们的结构的原始设计，也有可能验证属性。
This paper addresses the problem of locally verifying global properties. Several natural questions are studied, such as “how expensive is local verification?” and more specifically, “how expensive is local verification compared to computation?” A suitable model is introduced in which these questions are studied in terms of the number of bits a vertex needs to communicate. The model includes the definition of a proof labeling scheme (a pair of algorithms- one to assign the labels, and one to use them to verify that the global property holds). In addition, approaches are presented for the efficient construction of schemes, and upper and lower bounds are established on the bit complexity of schemes for multiple basic problems. The paper also studies the role and cost of unique identities in terms of impossibility and complexity, in the context of proof labeling schemes. Previous studies on related questions deal with distributed algorithms that simultaneously compute a configuration and verify that this configuration has a certain desired property. It turns out that this combined approach enables the verification to be less costly sometimes, since the configuration is typically generated so as to be easily verifiable. In contrast, our approach separates the configuration design from the verification. That is, it first generates the desired configuration without bothering with the need to verify it, and then handles the task of constructing a suitable verification scheme. Our approach thus allows for a more modular design of algorithms, and has the potential to aid in verifying properties even when the original design of the structures for maintaining them was done without verification in mind.