Nested transaction models have been widely adopted in many advanced database applications, such as telecommunications and real-time traffic information systems. However, noticeable studies focus on scheduling flat transactions for the current research of distributed real-time database systems (RTDBS). This paper presents an efficient real-time scheduler consisting of (1) a priority assignment policy called FHRN to schedule real-time nested transactions, and (2) a lock mechanism called 2PL-HPN to resolve the data conflict problem among nested transactions for distributed RTDBS using nested transaction models. The simulation result shows that the FHRN outperforms current priority assignment policies such as ED, HV and HRU.

Many noticeable studies have focussed on scheduling flat transactions in a distributed real-time database system (RTDBS). However, a nested transaction model has been widely adopted in many real-life applications such as Internet stock trading systems and telecommunications. This work concerns efficiently scheduling real-time nested transactions in a distributed RTDBS. A new real-time scheduler called flexible high reward for nested transactions (FHRN) is proposed. FHRN consists of (1) FHRNp1 policy to schedule real-time nested transactions and (2) 2PL_HPN to resolve the concurrent data-accessing problem among interleaved nested transactions. Simulation results show that FHRN outperforms these existent real-time schedulers such as random priority (RP), earliest deadline (ED), highest value (HV), hierarchical earliest deadline (HED), and highest reward and urgency (HRU) when an application requires a nested transaction model.

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.

F.J. Meyer and D.K. Pradhan (1991) 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). 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.

Traditionally, the Byzantine Agreement (BA) problem is studied either in a fully connected network or in a broadcast network. A generalized network model for BA is proposed in this paper. A fully-connected network or a broadcast network is a special case of the new network architecture. Under the new generalized network model, the BA problem is reexamined with the assumption of malicious faults on both processors and transmission medium (TM), as opposed to previous studies which consider malicious faults on processors only. The proposed algorithm uses the minimum number of message exchanges, and can tolerate the maximum number of allowable faulty components to make each healthy processor reach a common agreement for the cases of processor failures, TM failures, or processor/TM failures. The results can also be used to solve the interactive consistency problem and the consensus problem.>

A database languages based on Many-Sorted First-Order Logic (MSFOL) have many advantages over one based on One-Sorted First-Order Logic (OSFOL). The advantages includes ease-of-expressiveness, efficiency, and the abstraction mechanism. Many database researchers have used OSFOL to view the Relational Data Model (RDM); however, no RDM has been modelled by MSFOL. This paper first gives a formal definition for MSFOL and then its advantages of expressiveness and of abstraction are illustrated. Two reduction algorithms which can transform an MSFOL-based language into/from an OSFOL-based language are given. The semantic equivalence between languages based on MSFOL and Typed OSFOL is also proved. Recent extensions of RDMs require aggregation, classification, and generalisation/specialisation mechanisms which MSFOL-based languages can provide, but OSFOL-based languages cannot.

Traditionally, the problems of Byzantine agreement, consensus, and interactive consistency are studied in a fully connected network with processors in malicious failure only. Such problems are reexamined with the assumption of malicious faults on both processors and links. The proposed protocols use the minimum number of message exchanges and can tolerate the maximum number of allowable faulty components to make each fault-free processor reach a common agreement for the cases of processor failure, link failure, or processor and link failure.>

The average lock range (ALR) is proposed as an evaluation factor for measuring the strengths and weaknesses of locking-based concurrency control methods, for both structural and nonstructural locking. The methodology provides a simple and general way to analyze the performance of any locking method, and requires no queueing model. Based on the concept of the ALR, two popular locking protocols, the 2PL protocol and the tree protocol, are analyzed and a simulation is done to validate the correctness of the ALR model.>

The 'straw man' analysis (see J.N. Gray et al., 1981) is based on the assumption that the accessible unit and locking unit are both a record occurrence (or a tuple); consequently the results cannot be applied when a locking unit is a large granule such as an area, a file, or an index (or a data) block. In this paper, the probabilities of a transaction's waits and deadlocks are derived when the accessible unit is a data object and the locking unit is a granule. The results can be used to explain a transaction's wait and deadlock situations for: (1) various sizes of a granule; and (2) different distributions of data objects accessed by a transaction.>

The efficient organization of a very large file to facilitate search and retrieval operations is an important but very complex problem. In this paper we consider the case of a large file in which the frequency of use of its component subfiles are known. We develop the organization of the file so that the average number of entries to locate individual items in it by means of binary search is minimized. The algorithm iteratively partitions the file into "saturated" subfiles, and with each successive iteration the average number of entries to locate an item is reduced until no more improvement is possible. Next, we extend the method to solve the realistic problem of designing an optimal memory hierarchy to hold the file in a computer system. The sizes of various memory components and location of various items of the frequency-dependent file are determined so that the average time to locate an item (over the totality of items) in the memory hierarchy is minimized for a given total cost of the memory system. A number of examples are given to elucidate the methods. Also, the characteristics and results of a Fortran implementation of the algorithms on the CDC 6600 are described.