偵測一般形式全域述句的分散式演算法

Abstract

由於缺乏共享的記憶體以及全域的時鐘﹐測試與偵錯分散式程式較循序性 程式來得困難。偵測全域述句是個減輕這些問題的研究方法。偵測全域述 句的演算法可區分成兩組 -- 一組是偵測連結形式的述句﹐另一組是偵測 一般形式的述句。連結形式的述句乃由在分散式系統中的各個程序的區域 述句連結而成。這一組演算法的最大優點是其效率。然而﹐並非所有欲偵 測的述句都是連結形式的。因此﹐偵測一般形式的演算法是需要的﹐而集 中式的演算法的確已經存在。在這篇論文中﹐我們提出一個偵測一般形式 全域述句的分散式演算法。稱做分散式乃因所有的程序合作地收集各個全 域狀態。我們也證明演算法的正確性。此外﹐我們分析訊息複雜度﹐空間 複雜度以及時間複雜度﹐並與其餘的相關演算法做比較。這些分析與比較 顯示我們的演算法具較優的複雜度。 Testing and debugging distributed programs are more difficult than sequential programs for lack of shared memory and global clocks. One approach to alleviating the problems is to detect global predicates. Algorithms for detecting global predicates could be divided into two groups -- one is to detect conjunctive form predicates (CFP), and the other is to detect general form predicates (GFP). A conjunctive form predicate is one that can be formed by the conjunction of the predicates local to the processes in the distributed system. Efficiency is the greatest advantage of the algorithms in this group. However, not all predicates one wishes to detect are conjunctive form predicates. Algorithms for detecting general form predicates are needed, and centralized algorithms do exist. In this thesis, we propose a distributed algorithm by which all processes cooperate in collecting global states for detecting general form global predicates. We also prove that our algorithm is correct. Analyses of message, space, and time complexities respectively are given accompanied by comparison with those of related works. The analyses and comparisons show that our algorithm has better complexities.