Verifying the Output of a Distributed Algorithm Using Certification
Verifying the Output of a Distributed Algorithm Using Certification
复制标题
使用认证验证分布式算法的输出
DOI：
10.1007/978-3-319-67531-2_29
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
K. Völlinger
中科院分区：
文献类型：
--
作者：
K. Völlinger
认证算法通过除了输入输出对之外还生成见证来验证其在运行时输出的正确性。如果见证谓词适用于三元组，则输入输出对是正确的。检查算法决定见证谓词。虽然证明顺序算法已经很成熟，但我们考虑分布式算法。在本文中，我们研究了验证分布式算法的分布式输出。虽然见证谓词声明了网络中的属性，但对于分布式检查，需要为每个组件决定附加谓词。我们通过例子来说明其适用性。
Acertifying algorithmverifies the correctness of its output at runtime by producing awitnessin addition to an input-output pair. If awitness predicateholds for the triple, the input-output pair is correct. Acheckeralgorithm decides the witness predicate. While certifyingsequentialalgorithms are well-established, we considerdistributedalgorithms. In this paper, we investigate certifying distributed algorithms that verify their distributed output. While the witness predicate states a property in the network, for distributed checking, additional predicates are decided for each component. We illustrate the applicability by examples.
登录
查看更多内容
证明标签方案
DOI：
--
发表时间：
2005
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Amos Korman;S. Kutten;D. Peleg
通讯作者：
D. Peleg
DOI：
10.1007/978-3-319-57288-8_27
发表时间：
2017
期刊：
影响因子：
--
作者：
K. Völlinger;S. Akili
通讯作者：
S. Akili
分布式系统中 LTL 规范的去中心化运行时验证
DOI：
10.1109/ipdps.2015.95
发表时间：
2015
期刊：
2015 IEEE International Parallel and Distributed Processing Symposium
影响因子：
--
作者：
Menna Mostafa;Borzoo Bonakdarpour
通讯作者：
Borzoo Bonakdarpour
解决最优子结构问题的分布式算法的认证
DOI：
10.1007/978-3-319-22969-0_14
发表时间：
2015
期刊：
影响因子：
--
作者：
K. Völlinger;W. Reisig
通讯作者：
W. Reisig