Browsing by Author "Chu, William"

Now showing 1 - 2 of 2

Efficient online algorithm for identifying useless states in distributed systems
(2011-04-01)
Chen, Lung-Pin
;
Sun, Der-Johng
;
Chu, William
;
資訊工程學系
;
Department of Computer Science
In a distributed system, detecting whether a given logical predicate is true on the global states is fundamental for testing and debugging the program. Detecting predicates by examining all global states is intractable due to the combinatorial nature of the problem. This work designs an efficient online algorithm that identifies the consistent and useless states each time a new state is reported. This paper formulates the optimality of detecting algorithms in terms of pseudo states, which are employed to represent unknown states to the monitor process. Based on this technique, memory space of the debugger can be minimized by removing the useless states without affecting the debugging results. While minimizing memory space, the proposed algorithm requires only O(p (2) M) time in total, where p is the number of processes, and M is the number of reported states.
Incremental Digital Content Object Delivering in Distributed Systems
(2010-06-01)
Chen, Lung-Pin
;
Wu, I-Chen
;
Chu, William
;
Hong, Jhen-You
;
Ho, Meng-Yuan
Deploying and managing content objects efficiently is critical for building a scalable and transparent content delivery system. This paper investigates the advanced incremental deploying problem of which the objects are delivered in a successive manner. Recently, the researchers show that the minimum-cost content deployment can be obtained by reducing the problem to the well-known network flow problem. In this paper, the maximum flow algorithm for a single graph is extended to the incremental growing graph. Based on this extension, an efficient incremental content deployment algorithm is developed in this work.