基于执行分数向量的分布式终止检测算法

Distributed termination detection algorithm based on credit vector

提出了一项新算法检测分布式操作在全局范围内的终止信号。该算法扩展了执行分数算法,保留了原有算法的异步执行、控制消息数目最少、支持非先入先出信道等优点。通过引入执行分数向量数据结构,该算法使用较小的比特数组和少量的按位操作替代了原有算法中复杂的执行分数计算,去除了计算精度限制,并且提高了时间和空间效率。最后给出了新算法的正确性证明以及性能测试分析。

An efficient algorithm is designed to detect whether a distributed computation is globally terminated or not. The algorithm is developed from the credit recovery algorithm, retaining the advantages of being asynchronous, message optimal and workable on non- FIFO message channels. The algorithm is based on credit vector, which uses simple bitwise operations and small bit-array storage to calculate the credit value, thus eliminates original limitations on precision, time performance, and space performance. Correctness proving and performance analysis of the optimized algorithm are also presented.