A data extraction model, named the browser-oriented data extraction (BODE) model, was proposed by I-Chen Wu et al. (2005) to extract Web contents with script functions. In this model, the system built on top of browsers accesses pages by simulating users' operations on browsers. Based on this model, this paper defines a scripting language, named the BODED (browser-oriented data extraction description) language, which instructs the system how to do data extraction. This paper proposes a technique, called indirect browser replication to implement a BODE system, and also optimize the performance of this technique.

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 number 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.

In a distributed system, identifying consistent checkpoints is essential for error recovery and debugging. We 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/sup 2/M) time in total, where p is the number of processes and M is the number of checkpoints.

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.

Deriving the minimum and maximum global snapshots is very useful for some error detection problems in distributed programs. Several researchers, e.g., Groselj (1993) and Chen and Wu (1996), 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=/spl Theta/(n), where m is the number of edges and n is the number of vertices in the given flow network. The authors show in a reverse way that the MCNF problem is also linear-time reducible to these global snapshot problems. Thus, one can conclude that the global snapshot problems are "as difficult as" the MCNF problem in terms of time complexity.

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/spl ne/K, (2) NK (or N/spl ges/K), and (4) N=K, where N is the total number of tokens and K 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, B. Groselj (1993) and V.K. Garg (1995) solved the problem by reducing the problem to a maximum network flow 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 flow problem. For the fourth class of summative predicates, we prove that it is an NP-complete problem.