Browsing by Author "Chen, LB"

Now showing 1 - 8 of 8

An efficient distributed online algorithm to detect strong conjunctive predicates
(2002-11-01)
Chen, LB
;
Wu, IC
;
資訊工程學系
;
Department of Computer Science
Detecting strong conjunctive predicates is a fundamental problem in debugging and testing distributed programs. A strong conjunctive predicate is a logical statement to represent the desired event of the system. Therefore, if the predicate is not true, an error may occur because the desired event does not happen. Recently, several reported detection algorithms reveal the problem of unbounded state queue growth since the system may generate a huge amount of execution states in a very short time. In order to solve this problem, this paper introduces the notion of removable states which can be disregarded in the sense that detection results still remain correct. A fully distributed algorithm is developed in this paper to perform the detection in an online manner. Based on the notion of removable states, the time complexity of the detection algorithm is improved as the number of states to be evaluated is reduced.
An efficient incremental algorithm for identifying consistent checkpoint
(1998)
Chen, LB
;
Wu, IC
;
資訊工程學系
;
Department of Computer Science
In a distributed system, identifying consistent check points is essential for error recovery and debugging. In this paper, me design an efficient incremental algorithm capable of identifying all the consistent and removable checkpoints each time a new checkpoint is reported. By doing so, the required memory space can be minimized by removing those removables. While minimizing the memory space, the algorithm requires only O(p(2)M) time in total, where p is the number of processes and M is the number of checkpoints.
Detection of summative global predicates
(2003-05-01)
Chen, LB
;
Wu, IC
;
資訊工程學系
;
Department of Computer Science
In many distributed systems, tokens are fundamental tools to manage resources shared by processes. Thus, monitoring tokens has become a significant problem in developing the distributed programs. This paper formulates the problems of monitoring tokens in terms of detecting the special global predicates, called summative global predicates. In this paper, several algorithms to detect various summative global predicates are developed and their time complexities are discussed.
Detection of summative global predicates
(1997)
Chen, LB
;
Wu, IC
;
資訊工程學系
;
Department of Computer Science
In distributed programs, we usually keep some global predicates from being satisfied to make it easy to run the programs correctly. 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 paper; we call this summative predicates, classified into the following four: (1) at some global state of the system, N not equal K, (2) N < K (or N less than or equal to K), (3) N > K (or N greater than or equal to K), and (4) N = K, where N is the fetal number of tokens and ii is a constant. This paper investigates the methods of detecting various summative global predicates, The first class of summative predicates are trivial to detect by simply checking each message, For the second class of summative predicates, Groselj [6] and Garg [2] solved the problem by reducing the problem to a maximum network pou: problem. In this paper, we propose an elegant technique, called normalization, to allow the second and third classes of summative predicates to be solved by also reducing the problem to a maximum network pou: problem. For the fourth floss of summative! predicates, we prove that it is an NP-complete problem.
On detection of bounded global predicates
(1998-01-01)
Wu, IC
;
Chen, LB
;
資訊工程學系
;
Department of Computer Science
Distributed programs often follow some bounded global predicates, for example, the total number of certain tokens is always the same or bounded in a range. In order to detect bounded global predicates, we can first derive the minimum and maximum global snapshots and then check if the minimum and maximum are out of the range, Recently, Chase and Garg proposed an efficient method to derive the minimum global snapshot by reducing this problem to a maximum network flow problem. A restriction of this method is that all message values (e.g,, the token number in messages) must be zero and all process state values (e.g,, the token number in processes) must be non-negative. In this paper, we propose an elegant technique, called normalization. By using this technique, we can remove the above restriction and also derive the minimum and maximum global snapshots at the same time.
On detection of bounded global predicates
(1998-01-01)
Wu, IC
;
Chen, LB
;
資訊工程學系
;
Department of Computer Science
Distributed programs often follow some bounded global predicates, for example, the total number of certain tokens is always the same or bounded in a range. In order to detect bounded global predicates, we can first derive the minimum and maximum global snapshots and then check if the minimum and maximum are out of the range, Recently, Chase and Garg proposed an efficient method to derive the minimum global snapshot by reducing this problem to a maximum network flow problem. A restriction of this method is that all message values (e.g,, the token number in messages) must be zero and all process state values (e.g,, the token number in processes) must be non-negative. In this paper, we propose an elegant technique, called normalization. By using this technique, we can remove the above restriction and also derive the minimum and maximum global snapshots at the same time.
On the complexity of the minimum and maximum global snapshot problems
(1997)
Chen, LB
;
Wu, IC
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
Deriving the minimum and maximum global snapshots Is very useful for some error detection problems in distributed programs. Several researchers, e.g., Groselj, Chen and Wu, have shown that the minimum and maximum global snapshot problems are linear-time reducible to the maximum constant-ratio net work flow (MCNF) problem, here defined as the well-known maximum network flow problem with m = Theta(n), where m is the number of edges and n is the number of vertices in the given flow network. In this paper we show in a reverse way that the MCNF problem is also linear-time reducible to these global snapshot problems. Thus, we can conclude that the global snapshot problems are ''as difficult as'' the MCNF problem in terms of time complexity.
On the time complexity of minimum and maximum global snapshot problems
(1998-08-17)
Chen, LB
;
Wu, IC
;
資訊工程學系
;
Department of Computer Science
Deriving the minimum and maximum global snapshots is very useful for some error detection problems in distributed programs. Several researchers, e.g., Groselj, Chen and Wu, have shown that the minimum and maximum global snapshot problems are linear-time reducible to the maximum constant-ratio network flow (MCNF) problem, here defined as the well-known maximum network flow problem with m = Theta(n), where m is the number of edges and n is the number of vertices in the given flow network. In this paper we show in a reverse way that the MCNF problem is also linear-time reducible to these global snapshot problems. Thus, we can conclude that the global snapshot problems are "as difficult as" the MCNF problem in terms of time complexity. (C) 1998 Elsevier Science B.V. All rights reserved.