總和型全域述語之偵測

Abstract

對分散式程式的執行過程，檢查某個全域述語是否為真，是偵錯及監 測分散式系統的一個重要方法。一個常見的全域述語為：在一個分散式 系統中，token總數能否保持 (1) 等於 K (常數)、(2) 小於 K、(3) 大 於 K、(4) 不等於K。我們將這四項述語通稱為"總和型全域述語"。本篇 論文研究上述四項總和型全域述語之偵測，包括離線(off-line)偵測和 線上(on-line)偵測。離線偵測法是整個程式執行完畢後，才開始分析偵 測。而線上偵測是每當一有新的資訊，立即偵測。 對(1)項的每一次離線及線上偵測問題，我們證明針對分散式系統中 的訊息，各別檢查即可。 對(2)(3)項的每一次離線偵測問題，我們解決的方法是將這些問題 導為最大流量問題。藉此，這些問題都可在 O(n2 log n) 時間內解決， 其中 n 是程式執行過程中的訊息數量。另外，本篇論文亦證明在時間複 雜度方面，最大流量問題和(2)(3)項的偵測問題是一樣困難的。 對(2)(3)項的每一次線上偵測問題，我們解決的方法是將這些問題 導為一個新的問題，稱為"線上最大流量問題"。本篇論文中，我們設計 了新的線上最大流量演算法。藉此，(2)(3)項的每一次線上偵測問題都 可在 O(n2 log n) 時間解決，與離線偵測演算法相同。也就是說，將離 線演算法推廣成線上演算法的成本只有常數倍而已。事實上，我們的線 上最大流量演算法對所有的流量網路皆可使用。假設流量網路有 m 線 及 n 點。在m = Q(n) 的情形下，新的線上最大流量演算法的時間複雜 度，與目前已知最好的離線最大流量演算法的時間複雜度相同。在 m = O(n1+e) 的情形下，其中 e 是大於0 之任意常數，我們的線上演 算法的時間複雜度比目前最佳的離線最大流量演算法[1, 19, 35, 36] 的時間複雜度只差O(log n) 倍。 對(4)項的每一次離線及線上偵測問題，我們證明其為 NP-complete。

Detecting global predicates of distributed programs is an important problem in debugging and monitoring distributed systems. A common type of global predicates are: the total number of certain tokens in the whole distributed system is always the same or in specific ranges. In this thesis, we call this summative global predicates, classified into the following four: (1) at some global state of the system, N □K, (2) N < K (or N □K), (3) N > K (or N □K), and (4) N = K, where N is the total number of tokens and K is a constant. This thesis investigates off-line and on-line algorithms of detecting various summative global predicates. The off-line algorithms detect global predicates after the whole computation is finished, while the on-line algorithms detect global predicates at each time when more input data is provided. For the first class of summative global predicates, we show that they are trivial to detect off-line and on-line by simply checking each message once. For the second and third classes of summative global predicates, we show that they can be detected off-line in time O(n2logn) by reducing the problems to the maximum network flow problems, where n is the number of messages sent and received during the program execution. We also show that this detection problem is "as difficult as" the maximum flow problem in terms of time complexity. For the second and third classes of summative global predicates, we solve the on-line detection problems by reducing the problems to a new problem, called on-line maximum network flow problem. In this thesis, we design an on-line maximum flow algorithm, by which we can solve these on-line detection problems in time O(n2 log n), the same as that of the off-line detection algorithm. That is, the cost to pay for the on-line requirement is only a constant factor. In fact, our on-line maximum flow algorithm is general for all flow networks with n vertices and m edges. In the case of m = Q(n), its time complexity is the same as those of the best current off-line maximum flow algorithms up to date. In the case of m=O(n1+e) for any constant e > 0, its time complexity is only O(log n) times higher than those of the best maximum flow algorithms in [1, 19, 35, 36] up to date. For the fourth class of summative global predicates, we show that the off-line and on-line detection problems are NP-complete.