Algorithms for efficient transaction management and consistent queries in client -server semantic object-oriented parallel databases

Large read-only or read-write transactions with a large read set and a small write set constitute an important class of transactions used in such applications as data mining, data warehousing, statistical applications, and report generators. Such transactions are best supported with optimistic concurrency, because locking of large amounts of data for extended periods of time is not an acceptable solution. The abort rate in regular optimistic concurrency algorithms increases exponentially with the size of the transaction. The algorithm proposed in this dissertation solves this problem by using a new transaction scheduling technique that allows a large transaction to commit safely with significantly greater probability that can exceed several orders of magnitude versus regular optimistic concurrency algorithms. A performance simulation study and a formal proof of serializability and external consistency of the proposed algorithm are also presented.^ This dissertation also proposes a new query optimization technique (lazy queries). Lazy Queries is an adaptive query execution scheme which optimizes itself as the query runs. Lazy queries can be used to find an intersection of sub-queries in a very efficient way, which does not require full execution of large sub-queries nor does it require any statistical knowledge about the data.^ An efficient optimistic concurrency control algorithm used in a massively parallel B-tree with variable-length keys is introduced. B-trees with variable-length keys can be effectively used in a variety of database types. In particular, we show how such a B-tree was used in our implementation of a semantic object-oriented DBMS. The concurrency control algorithm uses semantically safe optimistic virtual "locks" that achieve very fine granularity in conflict detection. This algorithm ensures serializability and external consistency by using logical clocks and backward validation of transactional queries. A formal proof of correctness of the proposed algorithm is also presented. ^

On-Line Real-Time Service-Oriented Task Scheduling Using TUF

We present our approach to real-time service-oriented scheduling problems with the objective of maximizing the total system utility. Different from the traditional utility accrual scheduling problems that each task is associated with only a single time utility function (TUF), we associate two different TUFs—a profit TUF and a penalty TUF—with each task, to model the real-time services that not only need to reward the early completions but also need to penalize the abortions or deadline misses. The scheduling heuristics we proposed in this paper judiciously accept, schedule, and abort real-time services when necessary to maximize the accrued utility. Our extensive experimental results show that our proposed algorithms can significantly outperform the traditional scheduling algorithms such as the Earliest Deadline First (EDF), the traditional utility accrual (UA) scheduling algorithms, and an earlier scheduling approach based on a similar model.

What's in it for us? A case study research about micro sense making processes through the eyes of front line employees, during culture change implementation

Abstract How employees make sense of change is a very complex process. Recently, academics have neglected to research sense making activities in a micro culture implementation context, through the eyes of front line employees. In contrast to a macro view, a micro perspective limits researchers to only look at an individual, departmental or group level. By doing so, we can zoom in on the details of sense making processes that employees use in their daily work life. A macro (organisational) view is based on the notion that there is a general integrated culture that can be found in all organisational units and departments. It is assumed that culture can be researched by using the entire organisation as one single research entity. This thesis challenges this assumption. In case of planned change it is usually the management community who are in charge of the change intervention. Because of their formal hierarchical position, they have the power to abort or initiate change programs. It is perhaps therefore that researchers tend to be focused on the management community rather than on lower level organisational members, such as front line employees. Apart from the micro view, scholars also neglected to research culture change implementation through the eyes of front line employees. This thesis is an attempt to fill these two gaps that currently exists in academic change management publications. The main research question is therefore: From a micro point of view how do front-line employees make sense of the impact of culture change, during the implementation phase? This thesis starts with a literature review which exposes the two main gaps. The most important outcome of this review is that only 2% of the research articles dealt with culture implementation, through the eyes of front line employees. A conceptual research model is built on the integrated sense making theory of Weber and Manning (2001) and the micro variables of Raelin and Cataldo (2011). These theories emphasize elements of sense making in a daily working context. It is likely that front line employees can identify themselves with research elements such as tasks, skills practices, involvement and behaviour. Front line employees were selected, because as lower level organisational members they are usually the change recipients. They are further away from the change initiating scene (usually the management of an organisation) and form a potential sense making ‘hotspot’ that could provide new academic insights. In order to carry out the primary research, two case organisations were selected in the leisure industry. A participative case study research method was chosen. This meant that the researcher worked in the concerning departments of the case organisations. The goal was to observe and interview front line employees, while they were performing their jobs. The most important advantage of this approach is that the researcher temporarily becomes one with the organisation and is therefore able to acquire both formal and informal narratives that front line employees use during sense making activities. It was found that front line employees make sense of organisational change by using a practical approach. They make sense of the change program by carrying out new tasks, developing new skills and sharing best practices. The most noticeable conclusion was that sense making activities predominantly take place at an individual level in relation to change acceptance. Organisational members tend to create a mental equation in order to weigh the advantages against the disadvantages. They evaluate whether the concerning change program is beneficial to them or not. For future research a sense making scheme model is suggested that is based on two methods: an introspection and an action method.

Insights into the Fallback Path of Best-Effort Hardware Transactional Memory Systems

Current industry proposals for Hardware Transactional Memory (HTM) focus on best-effort solutions (BE-HTM) where hardware limits are imposed on transactions. These designs may show a significant performance degradation due to high contention scenarios and different hardware and operating system limitations that abort transactions, e.g. cache overflows, hardware and software exceptions, etc. To deal with these events and to ensure forward progress, BE-HTM systems usually provide a software fallback path to execute a lock-based version of the code. In this paper, we propose a hardware implementation of an irrevocability mechanism as an alternative to the software fallback path to gain insight into the hardware improvements that could enhance the execution of such a fallback. Our mechanism anticipates the abort that causes the transaction serialization, and stalls other transactions in the system so that transactional work loss is mini- mized. In addition, we evaluate the main software fallback path approaches and propose the use of ticket locks that hold precise information of the number of transactions waiting to enter the fallback. Thus, the separation of transactional and fallback execution can be achieved in a precise manner. The evaluation is carried out using the Simics/GEMS simulator and the complete range of STAMP transactional suite benchmarks. We obtain significant performance benefits of around twice the speedup and an abort reduction of 50% over the software fallback path for a number of benchmarks.