Browsing by Author "Chin, YH"

Now showing 1 - 10 of 10

A note on consensus on dual failure modes
(1996-03-01)
Siu, HS
;
Chin, YH
;
Yang, WP
;
資訊工程學系
;
Department of Computer Science
Meyer and Pradhan proposed the MS (for ''mixed-sum'') algorithm to solve the Byzantine Agreement (BA) problem with dual failure modes: arbitrary faults (Byzantine faults) and dormant faults (essentially omission faults and timing faults) [3]. Our study indicates that this algorithm uses an inappropriate method to eliminate the effects of dormant faults and that the bound on the number of allowable faulty processors is overestimated. This paper corrects the algorithm and gives a new bound for the allowable faulty processors.
An adaptive value-based scheduling policy for multiprocessor real-time database systems
(1997)
Tseng, SM
;
Chin, YH
;
Yang, WP
;
交大名義發表
;
資訊工程學系
In a real-time application, a transaction may be assigned a value to reflect the profit of completing the transaction before its deadline. Satisfying both goals of maximizing the totally obtained profit and minimizing the number of missed transactions at the same time is a challenge. In this paper we present an adaptive real-time scheduling policy named Value-based Processor Allocation (VPA-k) for scheduling value-based transactions in a multiprocessor real-time database system. Using VPA-k policy, the transactions with higher values are given higher priorities to execute first, while at most k percentage of total processors are dynamically allocated to execute the urgent transactions. Through simulation experiments, VPA-k is shown to outperform other scheduling policies substantially in bath maximizing the totally obtained profit mid minimizing the number of missed transactions under various system environments.
Byzantine agreement in the presence of mixed faults on processors and links
(1998-04-01)
Siu, HS
;
Chin, YH
;
Yang, WP
;
資訊工程學系
;
Department of Computer Science
In early stage, the Byzantine agreement (BA) problem was studied with single faults on processors in either a fully connected network or a nonfully connected network. Subsequently, the single fault assumption was extended to mixed faults (also referred to as hybrid fault model) on processors. For the case of both processor and link failures, the problem has been examined in a fully connected network with a single faulty type, namely an arbitrary fault. To release the limitations of a fully connected network and a single faulty type, the problem is reconsidered in a general network. The processors and links in such a network can both be subjected to different types of fault simultaneously. The proposed protocol uses the minimum number of message exchanges and can tolerate the maximum number of allowable faulty components to make each fault-free processor reach an agreement.
Performance evaluation of a high-value scheduling policy for real-time main memory databases
(1996-09-01)
Tseng, SM
;
Chin, YH
;
Yang, WP
;
資訊工程學系
;
Department of Computer Science
With the decrease in hardware prices, storing databases in main memory has become feasible for meeting the high-performance requirements of real-time applications. In this paper, an efficient scheduling policy is proposed for scheduling transactions with values in real- time main memory databases, where the value of a transaction means its worthiness to a real-time application of it is completed before the deadline. Through detailed performance evaluation, the proposed policy is shown to outperform the existing policies in both minimizing the number of missed transactions and maximizing the obtained values under various system environments. A cost formula for evaluating the optimal memory size to store partial databases such as to maximize the net profits is developed from the economic standpoint. Some suggestions are given for scheduling value-based transactions in real-time main memory databases.
Performance evaluation of a high-value scheduling policy for real-time main memory databases
(1996-09-01)
Tseng, SM
;
Chin, YH
;
Yang, WP
;
資訊工程學系
;
Department of Computer Science
With the decrease in hardware prices, storing databases in main memory has become feasible for meeting the high-performance requirements of real-time applications. In this paper, an efficient scheduling policy is proposed for scheduling transactions with values in real- time main memory databases, where the value of a transaction means its worthiness to a real-time application of it is completed before the deadline. Through detailed performance evaluation, the proposed policy is shown to outperform the existing policies in both minimizing the number of missed transactions and maximizing the obtained values under various system environments. A cost formula for evaluating the optimal memory size to store partial databases such as to maximize the net profits is developed from the economic standpoint. Some suggestions are given for scheduling value-based transactions in real-time main memory databases.
Reaching fault diagnosis agreement under a hybrid fault
(2000-09-01)
Hsiao, HS
;
Chin, YH
;
Yang, WP
;
資訊工程學系
;
Department of Computer Science
The goal of the fault diagnosis agreement (FDA) problem is to make each fault-free processor detect/locate a common set of faulty processors. The problem is examined on processors with mixed fault model (also referred to as hybrid fault model). An evidence-based fault diagnosis protocol is proposed to solve the FDA problem. The proposed protocol first collects the messages which have accumulated in the Byzantine agreement protocol as the evidence. By examining the collected evidence, a fault-free processor can detect/locate which processor is faulty. Then, the network can be reconfigured by removing the detected faulty processors and the links connected to these processors from the network. The proposed protocol can detect/locate the maximum number of faulty processors to solve the FDA problem.
Reaching strong consensus in a general network
(2002-07-01)
Hsiao, HS
;
Chin, YH
;
Yang, WP
;
資訊工程學系
;
Department of Computer Science
The strong consensus (SC) problem is a variant of the conventional distributed consensus problem (also known as the Byzantine agreement problem). The SC problem requires that the agreed value among fault-free processors be one of the fault-free processor's initial values. Originally, the problem was studied in a fully connected network with malicious faulty processors. In this paper, the SC problem is re-examined in a general network, in which the components (processors and communication links) may be subjected to different faulty types simultaneously (also called the hybrid fault model or mixed faulty types) and the network topology does not have to be fully connected. The proposed protocol can tolerate the maximum number of tolerable faulty components such that each fault-free processor obtains a common value for the SC problem in a general network.
Reaching strong consensus in the presence of mixed failure types
(1998-07-01)
Siu, HS
;
Chin, YH
;
Yang, WP
;
資訊工程學系
;
Department of Computer Science
The Strong Consensus (SC) is a variant of the conventional distributed consensus problem. The protocol designed for the SC problem requires that the agreed value among fault-free processors be one of the fault-free processor's initial value. The SC problem is re-examined with the assumption of mixed failure types (also referred to as the hybrid fault model). Compared with the features of the existing protocols, the underlying network topologies of the proposed protocol do not have to be fully connected, the mixed failure types can be tolerated, and no prior information of the system's faulty status is required. The proposed protocol can tolerate a maximum number of faults to enable each fault-free processor to reach an agreement with a minimum number of message exchanges. (C) 1998 Published by Elsevier Science Inc. All rights reserved.
Value-based scheduling for multiprocessor real-time database systems
(1998-01-01)
Tseng, SM
;
Chin, YH
;
Yang, WP
;
資訊工程學系
;
Department of Computer Science
We present a new scheduling policy named Value-based Processor Allocation (VPA-k) for scheduling value-based transactions in a multiprocessor real-time database system. The value of a transaction represents the profit the transaction contributes to the system if it is completed before its deadline. Using VPA-k policy, the transactions with higher values are given higher priorities to execute first, while at most k percentage of the total processors are allocated to the urgent transactions dynamically. Through simulation experiments, VPA-k policy is shown to outperform other scheduling policies substantially in both maximizing the totally obtained values and minimizing the number of missed transactions.
Value-based scheduling for multiprocessor real-time database systems
(1998-01-01)
Tseng, SM
;
Chin, YH
;
Yang, WP
;
資訊工程學系
;
Department of Computer Science
We present a new scheduling policy named Value-based Processor Allocation (VPA-k) for scheduling value-based transactions in a multiprocessor real-time database system. The value of a transaction represents the profit the transaction contributes to the system if it is completed before its deadline. Using VPA-k policy, the transactions with higher values are given higher priorities to execute first, while at most k percentage of the total processors are allocated to the urgent transactions dynamically. Through simulation experiments, VPA-k policy is shown to outperform other scheduling policies substantially in both maximizing the totally obtained values and minimizing the number of missed transactions.