Certification of Distributed Algorithms Solving Problems with Optimal Substructure
Certification of Distributed Algorithms Solving Problems with Optimal Substructure
复制标题
解决最优子结构问题的分布式算法的认证
DOI：
10.1007/978-3-319-22969-0_14
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
W. Reisig
中科院分区：
文献类型：
--
作者：
K. Völlinger;W. Reisig
我们报告了将认证算法的概念应用于分布式算法的工作进展。认证算法不仅产生结果，而且产生验证结果正确性的证据。已经开发了许多(顺序)算法的认证变体。然而，分布式算法的行为不同于顺序算法。因此，使它们获得认证是具有挑战性的。我们采用局部方法使分布式算法计算多个本地目击者，共同验证结果的正确性。我们确定了这种方法适用的问题。特别地，我们假设对于具有最优子结构的问题(即，可以从子问题的最优解构造最优解)，通常很容易应用局部方法。作为例子，我们给出了求解最短路径问题的精确分布式算法。
We report work-in-progress on applying the concept of a certifying algorithm to distributed algorithms. Acertifying algorithmproduces not only a result, but also awitnessthat verifies the result’s correctness. Certifying variants of numerous (sequential) algorithms have been developed. However,distributed algorithmsbehave differently from sequential algorithms. Consequently, it is challenging to make them certifying. Ourlocal approachis to make the distributed algorithm compute manylocalwitnesses that together verify the result’s correctness. We identified problems for which this approach is applicable. Particularly, we hypothesize that for problems withoptimal substructure(i.e., an optimal solution can be constructed from optimal solutions of its subproblems) it is often easy to apply the local approach. As an example, we give acertifyingdistributed algorithm for the shortest path problem.
通过局部检查和全局重置实现自稳定（扩展摘要）
DOI：
--
发表时间：
1994
期刊：
International Workshop on Distributed Algorithms
影响因子：
--
作者：
B. Awerbuch;B. Patt;G. Varghese;S. Dolev
通讯作者：
S. Dolev