An intelligent hybrid optimistic/pessimistic concurrency control algorithm for centralized database systems using modified GSA-optimized ART neural model

Concurrency control is the activity of synchronizing operations issued by concurrent executing transactions on a shared database. The aim of this control is to provide an execution that has the same effect as a serial (non-interleaved) one. The optimistic concurrency control technique allows the transactions to execute without synchronization, relying on commit-time validation to ensure serializability. Effectiveness of the optimistic techniques depends on the conflict rate of transactions. Since different systems have various patterns of conflict and the patterns may also change over time, so applying the optimistic scheme to the entire system results in degradation of performance. In this paper, a novel algorithm is proposed that dynamically selects the optimistic or pessimistic approach based on the value of conflict rate. The proposed algorithm uses an adaptive resonance theory–based neural network in making decision for granting a lock or detection of the winner transaction. In addition, the parameters of this neural network are optimized by a modified gravitational search algorithm. On the other hand, in the real operational environments we know the writeset (WS) and readset (RS) only for a fraction of transactions set before execution. So, the proposed algorithm is designed based on optional knowledge about WS and RS of transactions. Experimental results show that the proposed hybrid concurrency control algorithm results in more than 35 % reduction in the number of aborts in high-transaction rates as compared to strict two-phase locking algorithm that is used in many commercial database systems. This improvement is 13 % as compared to pure-pessimistic approach and is more than 31 % as compared to pure-optimistic approach.     

Secure buffering in firm real-time database systems

Many real-time database applications arise in electronic financial services, safety-critical installations and military systems where enforcing security is crucial to the success of the enterprise. We investigate here the performance implications, in terms of killed transactions, of guaranteeing multi-level secrecy in a real-time database system supporting applications with firm deadlines. In particular, we focus on the buffer management aspects of this issue. Our main contributions are the following. First, we identify the importance and difficulties of providing secure buffer management in the real-time database environment. Second, we present SABRE, a novel buffer management algorithm that provides covert-channel-free security. SABRE employs a fully dynamic one-copy allocation policy for efficient usage of buffer resources. It also incorporates several optimizations for reducing the overall number of killed transactions and for decreasing the unfairness in the distribution of killed transactions across security levels. Third, using a detailed simulation model, the real-time performance of SABRE is evaluated against unsecure conventional and real-time buffer management policies for a variety of security-classified transaction workloads and system configurations. Our experiments show that SABRE provides security with only a modest drop in real-time performance. Finally, we evaluate SABRE's performance when augmented with the GUARD adaptive admission control policy. Our experiments show that this combination provides close to ideal fairness for real-time applications that can tolerate covert-channel bandwidths of up to one bit per second (a limit specified in military standards). Received March 1, 1999 / Accepted October 1, 1999     

移动数据库中数据复制同步处理策略的研究

同步技术是保证复制移动数据库系统一致性的一项关键技术,鉴于目前移动复制同步技术存在通讯数据量大,存储空间消耗多,尤其是在网络带宽下降时,不能及时更新客户端的数据,导致移动事务执行失败等缺陷。通过UTLRSP（Union Transaction-Level Result-Set Propagation,关联事务结果集）复制同步模型结合数据广播技术,并利用基于优先级的增量更新算法实现客户端与中心数据库服务器的数据同步处理。实验结果表明,与两级复制机制相比,UTLRSP模型将事务作相关联处理,且只保存事务结果,有效降低了存贮空间的消耗,减小了同步过程中通讯数据量;基于优先级的增量更新算法根据数据新鲜度排列优先级,保证在无线网络带宽下降时新鲜度最高的数据先传输,提高了数据的传输效率、动态新鲜度以及客户端的可扩展性。     

Replica Consistency in Lazy Master Replicated Databases

In a lazy master replicated database, a transaction can commit after updating one replica copy (primary copy) at some master node. After the transaction commits, the updates are propagated towards the other replicas (secondary copies), which are updated in separate refresh transactions. A central problem is the design of algorithms that maintain replica's consistency while at the same time minimizing the performance degradation due to the synchronization of refresh transactions. In this paper, we propose a simple and general refreshment algorithm that solves this problem and we prove its correctness. The principle of the algorithm is to let refresh transactions wait for a certain deliver time before being executed at a node having secondary copies. We then present two main optimizations to this algorithm. One is based on specific properties of the topology of replica distribution across nodes. In particular, we characterize the nodes for which the deliver time can be null. The other improves the refreshment algorithm by using an immediate update propagation strategy.     

Two algorithms for barrier synchronization

We describe two new algorithms for implementing barrier synchronization on a shared-memory multicomputer. Both algorithms are based on a method due to Brooks. We first improve Brooks' algorithm by introducing double buffering. Our dissemination algorithm replaces Brook's communication pattern with an information dissemination algorithm described by Han and Finkel. Our tournament algorithm uses a different communication pattern and generally requires fewer total instructions. The resulting algorithms improve Brook's original barrier by a factor of two when the number of processes is a power of two. When the number of processes is not a power of two, these algorithms improve even more upon Brooks' algorithm because absent processes need not be simulated. These algorithms share with Brooks' barrier the limitation that each of then processes meeting at the barrier must be assigned identifiersi such that 0i<n.     

On-the-fly reading of entire databases

A common database need is to obtain a global-read, which is a consistent read of an entire database. To avoid terminating normal system activity, and thus improve availability, we propose an on-the-fly algorithm that reads database entities incrementally and allows normal transactions to proceed concurrently. The algorithm assigns each entity a color based on whether the entity has been globally read, and a shade based on how normal transactions have accessed the entity. Serializability of execution histories is ensured by requiring normal transactions to pass both a color test and a shade test before being allowed to commit. Our algorithm improves on a color-only-based scheme from the literature; the color-only scheme does not guarantee serializability     

On the Feasibility of Time Estimation under Isolation Conditions in Wireless Sensor Networks

We study the problem of providing a sensor with an accurate estimate of the time, from a novel perspective which is complementary to the well-studied clock synchronization problem. More precisely, we analyze the case in which a sensor node is temporarily unable to run a clock synchronization protocol due to failures or intermittent connectivity, or is willing to skip one or more clock adjustments to save energy, but still requires an accurate estimate of the reference time. We propose and analyze two simple and efficient clock reading methods, one deterministic and the other probabilistic, which are designed to work in synergy with a clock synchronization protocol. Our deterministic method achieves a better time accuracy by exploiting information regarding the sign of the deviation of the hardware clock from the reference time. This algorithm leads to noticeable energy savings since it can be applied to reduce the frequency of the periodic clock adjustments by a factor of 2, while maintaining the same error bound. Moreover, our method is of theoretical interest since it shows how a stronger but realistic clock model leads to a refinement of the optimality bound for the maximum deviation of a clock that is periodically synchronized. We also propose two simple versions of this algorithm: a method that guarantees the monotonicity of the clock values, and a generalization that improves the accuracy in case of clock stability. Our probabilistic method is based on time series forecasting, and provides a probabilistically accurate estimate of the reference time with a constant error bound. It is more flexible than our previous methods since it does not depend on the frequency at which clock synchronization occurs, and can be dynamically tuned according to the application requirements and resource availability. All these methods have broad applicability for their generality. In sensor networks they can be applied to improve the clock accuracy of a sensor node in conditions of network isolation, or to reduce the frequency of the clock adjustments, thus saving energy and increasing the system lifetime.     

Implementing Distributed Read-Only Transactions

This paper presents an efficient scheme for eliminating conflicts between distributed read-only transactions and distributed update transactions, thereby reducing synchronization delays. The scheme makes use of a multiversion mechanism in order to guarantee that distributed read-only transactions see semantically consistent snap-shots of the database, that they never have to be rolled-back due to their late arrival at retrieval sites, and that they inflict minimal synchronization delays on concurrent update transactions. Proof that the presented scheme guarantees semantic consistency is provided. Two important by-products of this scheme are that the recovery from transaction and system failures is greatly simplified and the taking of database dumps also can be accommodated while leaving the database on-line.     

Faster synchronization in P systems

In the field of molecular computing, in particular P systems, synchronization is an important requirement for composing or sequentially linking together congenial P system activities. We provide a deterministic algorithm to the Firing Squad Synchronization Problem, for digraph-based P systems, which runs in 3e + 11 steps, where e is the eccentricity of the general. Our algorithm uses a convenient framework, called simple P modules, which embraces the essential features of several popular types of P systems.     

基于关联事务的移动数据库冲突处理算法

移动数据库系统由于自身的特点采用乐观复制机制。该文引入关联事务的概念,提出关联事务划分算法(UTDA)及冲突处理算法(CRA)。UTDA算法将移动终端在本地提交的移动事务划分成关联事务,把关联事务作为数据同步和冲突处理的基本粒度。实验结果表明,UTDA算法满足事务执行的原子性和串行性,提交时间比传统事务提交时间减少了2/3,为移动数据库系统的冲突处理提供了可行的解决方案。     

On earliest deadline first scheduling for temporal consistency maintenance

A real-time object is one whose state may become invalid with the passage of time. A temporal validity interval is associated with the object state, and the real-time object is temporally consistent if its temporal validity interval has not expired. Clearly, the problem of maintaining temporal consistency of data is motivated by the need for a real-time system to track its environment correctly. Hence, sensor transactions must be able to execute periodically and also each instance of a transaction should perform the relevant data update before its deadline. Unfortunately, the period and deadline assignment problem for periodic sensor transactions has not received the attention that it deserves. An exception is the More-Less scheme, which uses the Deadline Monotonic (DM) algorithm for scheduling periodic sensor transactions. However, there is no work addressing this problem from the perspective of dynamic priority scheduling. In this paper, we examine the problem of temporal consistency maintenance using the Earliest Deadline First (EDF) algorithm in three steps: First, the problem is transformed to another problem with a sufficient (but not necessary) condition for feasibly assigning periods and deadlines. An optimal solution for the problem can be found in linear time, and the resulting processor utilization is characterized and compared to a traditional approach. Second, an algorithm to search for the optimal periods and deadlines is proposed. The problem can be solved for sensor transactions that require any arbitrary deadlines. However, the optimal algorithm does not scale well when the problem size increases. Hence, thirdly, we propose a heuristic search-based algorithm that is more efficient than the optimal algorithm and is capable of finding a solution if one exists.

Performance of memory reclamation for lockless synchronization

Achieving high performance for concurrent applications on modern multiprocessors remains challenging. Many programmers avoid locking to improve performance, while others replace locks with non-blocking synchronization to protect against deadlock, priority inversion, and convoying. In both cases, dynamic data structures that avoid locking require a memory reclamation scheme that reclaims elements once they are no longer in use.The performance of existing memory reclamation schemes has not been thoroughly evaluated. We conduct the first fair and comprehensive comparison of three recent schemes—quiescent-state-based reclamation, epoch-based reclamation, and hazard-pointer-based reclamation—using a flexible microbenchmark. Our results show that there is no globally optimal scheme. When evaluating lockless synchronization, programmers and algorithm designers should thus carefully consider the data structure, the workload, and the execution environment, each of which can dramatically affect the memory reclamation performance.We discuss the consequences of our results for programmers and algorithm designers. Finally, we describe the use of one scheme, quiescent-state-based reclamation, in the context of an OS kernel—an execution environment which is well suited to this scheme.     

A nonrestrictive concurrency control protocol for object-oriented databases

We propose an algorithm for executing transactions in object-oriented databases. The object-oriented database model generalizes the classical model of database concurrency control by permitting accesses toclass andinstance objects, by permittingarbitrary operations on objects as opposed to traditional read and write operations, and by allowingnested execution of transactions on objects. In this paper, we first develop a uniform methodology for treating both classes and instances. We then develop a two-phase locking protocol with a new relationship between locks calledordered sharing for an object-oriented database. Ordered sharing does not restrict the execution of conflicting operations. Finally, we extend the protocol to handle objects that execute methods on other objects thus resulting in the nested execution of transactions. The resulting protocol permits more concurrency than other known locking-based protocols.     

复制的移动数据库系统事务级同步处理策略

同步处理技术是保持复制的移动数据库系统一致性的一项关键技术,但现有的事务级同步处理算法存在着一定的局限性.为了克服这些缺陷,并增强其实用性,提出了一种新的移动数据库同步处理模型──基于双时间印的事务级同步(DTSTLS)模型.DTSTLS模型采用了一种三级复制体系结构,系统可以直接使用通用的数据库产品作为其数据库服务器,因此具有良好的可扩充性.作为一种异步的多主副本复制方法,DTSTLS模型允许移动计算机在断连的情况下存取本地副本,从而造成系统短暂的不一致,重新连接时进行冲突检测及同步处理,使系统重新收敛于一致性的状态.此外,通过一种独特的时间印处理策略,DTSTLS模型减少了通信代价,并降低了资源消耗.实验结果表明,DTSTLS模型提高了移动数据库系统的资源利用效率,保证了事务调度的可串行性和数据库的一致性.     

Finding missing synchronization in a distributed computation using controlled re-execution

Correct distributed programs are hard to write. Not surprisingly, distributed systems are especially vulnerable to software faults. Testing and debugging is an important way to improve the reliability of distributed systems. A distributed debugger equipped with the mechanism to re-execute the traced computation in a controlled fashion can greatly facilitate the detection and localization of bugs. This approach gives rise to a general problem of predicate control, which takes a computation and a safety property specified on the computation as inputs, and produces a controlled computation, with added synchronization, that maintains the given safety property as output. We devise efficient control algorithms for two classes of useful predicates, namely region predicates and disjunctive predicates. For the former, we prove that the control algorithm is optimal in the sense that it guarantees maximum concurrency possible in the controlled computation. For the latter, we prove that our control algorithm generates the least number of synchronization dependencies and therefore has optimal message-complexity. Furthermore, we provide a necessary and sufficient condition under which it is possible to efficiently compute a minimal controlling synchronization for a general predicate. We also give an algorithm to compute such a synchronization under the condition provided.Received: 19 June 2002, Accepted: 7 November 2003, Published online: 1 March 2004Vijay K. Garg: Supported in part by the NSF Grants ECS-9907213, CCR-9988225, Texas Education Board Grant ARP-320, an Engineering Foundation Fellowship, and an IBM grant.A preliminary version of the results in this paper first appeared in [15].     

Localization in time and space for wireless sensor networks: An efficient and lightweight algorithm

In many applications that use Wireless Sensor Networks (WSNs), detected events need to be localized in both time and space. As a result, sensor nodes need to have precisely synchronized clocks as well as to be localized in a common spatial reference system. While synchronization and localization algorithms have been proposed to solve these problems independently, in this work we propose to combine both synchronization and localization into a single problem that we refer to as the time–space localization problem. We then propose a novel and efficient time–space localization algorithm for wireless sensor networks which we refer to as the Lightness algorithm. Our proposed algorithm not only takes advantage of the additional hardware resources required by the positioning mechanism in order to improve the performance and scalability of synchronization, but also benefits from the additional communication needed by the synchronization mechanism in order to decrease positioning errors. We also present an extensive set of experiments to evaluate the performance of our algorithm. Our results indicate clearly that our proposed scheme is scalable while keeping a low synchronization error and a low communication overhead. Our results also indicate that the additional packets needed to compute clocks’ drift have the ability to decrease the positioning errors to almost one third of the initial positioning.     

Atomic RMI: A Distributed Transactional Memory Framework

This paper presents Atomic RMI, a distributed transactional memory framework that supports the control flow model of execution. Atomic RMI extends Java RMI with distributed transactions that can run on many Java virtual machines located on different network nodes. Our system employs SVA, a fully-pessimistic concurrency control algorithm that provides exclusive access to shared objects and supports rollback and fault tolerance. SVA is capable of achieving a relatively high level of parallelism by interweaving transactions that access the same objects and by making transactions that do not share objects independent of one another. It also allows any operations within transactions, including irrevocable ones, like system calls, and provides an unobtrusive API. Our evaluation shows that in most cases Atomic RMI performs better than fine grained mutual-exclusion and read/write locking mechanisms. Atomic RMI also performs better than an optimistic transactional memory in environments with high contention and a high ratio of write operations, while being competitive otherwise.     

Efficient Graph-Based Algorithms for Discovering and Maintaining Association Rules in Large Databases

In this paper, we study the issues of mining and maintaining association rules in a large database of customer transactions. The problem of mining association rules can be mapped into the problems of finding large itemsets which are sets of items brought together in a sufficient number of transactions. We revise a graph-based algorithm to further speed up the process of itemset generation. In addition, we extend our revised algorithm to maintain discovered association rules when incremental or decremental updates are made to the databases. Experimental results show the efficiency of our algorithms. The revised algorithm is a significant improvement over the original one on mining association rules. The algorithms for maintaining association rules are more efficient than re-running the mining algorithms for the whole updated database and outperform previously proposed algorithms that need multiple passes over the database. Received 4 August 1999 / Revised 18 March 2000 / Accepted in revised form 18 October 2000     

A combinatorial testing strategy for concurrent programs

One approach to testing concurrent programs is called reachability testing, which derives test sequences automatically and on‐the‐fly, without constructing a static model. Existing reachability testing algorithms are exhaustive in that they are intended to exercise all possible synchronization sequences of a concurrent program with a given input. In this paper, we present a new testing strategy, called t‐way reachability testing, that adopts the dynamic framework of reachability testing but selectively exercises a subset of synchronization sequences. The selection of the synchronization sequences is based on a combinatorial testing strategy called t‐way testing. We present an algorithm that implements t‐way reachability testing, and report the results of several case studies that were conducted to evaluate its effectiveness. The results indicate that t‐way reachability testing can substantially reduce the number of synchronization sequences exercised during reachability testing while still effectively detecting faults. Copyright © 2007 John Wiley & Sons, Ltd.