Concurrency control issues in nested transactions

The concept of nested transactions offers more decomposable execution units and finer-grained control over concurrency and recovery than flat transactions. Furthermore, it supports the decomposition of a unit of work into subtasks and their appropriate distribution in a computer system as a prerequisite of intratransaction parallelism. However, to exploit its full potential, suitable granules of concurrency control as well as access modes for shared data are necessary. In this article, we investigate various issues of concurrency control for nested transactions. First, the mechanisms for cooperation and communication within nested transactions should not impede parallel execution of transactions among parent and children or among siblings. Therefore, a model for nested transactions is proposed allowing for effective exploitation of intra-transaction parallelism. Starting with a set of basic locking rules, we introduce the concept of downward inheritance of locks to make data manipulated by a parent available to its children. To support supervised and restricted access, this concept is refined to controlled downward inheritance. The initial concurrency control scheme was based on S-X locks for flat, non-overlapping data objects. In order to adjust this scheme for practical applications, a set of concurrency control rules is derived for generalized lock modes described by a compatibility matrix. Also, these rules are combined with a hierarchical locking scheme to improve selective access to data granules of varying sizes. After having tied together both types of hierarchies (transaction and object), it can be shown how controlled downward inheritance for hierarchical objects is achieved in nested transactions. Finally, problems of deadlock detection and resolution in nested transactions are considered.     

Eine bedingte Form der Integral-Ungleichung von Gronwall,leichte Verallgemeinerung eines Stabilitätssatzes von Perron und überlauffreie Skalierung von Analogrechenschaltungen

Zusammenfassung Es geht in dieser Arbeit in der Hauptsache darum, ein vorgelegtes Differentialgleichungssystem so zu skalieren, daß in der zugehörigen Analogrechnerschaltung die Spannungen an den Ausgängen der Integratoren die durch die Referenzspannung einerseits und durch das Auflösevermögen andererseits gesetzten Schranken nicht über- bzw. unterschreiten. Es werden Abschätzungssätze hergeleitet, die diese Frage im Apriori-Sinn, also ohne die Lösung des Differentialgleichungssystems zu kennen, zu lösen gestatten. Zur Abschätzung werden zunächst Normen, dannKamke-Normen verwendet. Der im Titel erwähnte Satz vonPerron ergibt sich durch spezielle Normengebung und Verzicht auf Abschätzung nach unten. Erschwert werden die Betrachtungen durch die relative Schwäche der Forderung, daß die rechte Seite des Systemsdx/dt=f(x,t) der Bedingung aus xa folgt f(x,t)v(t)x genüge (...:=Norm,a positiv reell). Dadurch scheint es bei Abschätzungen mitKamke-Normen nicht mehr möglich, von den in der Literatur über Existenzbeweise und Abschätzungssätze üblichen Methoden Gebrauch zu machen. Zur Lösung dieser Frage wird eine bedingte Form des bekannten Satzes vonGronwall (auch Satz vonBellman genannt) entwickelt.

---

A conditional version of the integral inequality of gronwall, a slight generalization of a stability theorem of perron, and overflow-free scaling of analogue computer set-ups

Summary The main subject of this paper is the scaling of a given set of differential equations in such a way that the output voltages of the integrators of the associated analogue computer set-up do not exceed certain upper and lower bounds imposed by the reference voltage and the limited power of resolution of the elements of the analogue computer. The paper gives a priori bounds on the solution of the differential set. Some of these bounds work with norms, others withKamke-norms.Perron's stability theorem mentioned in the title of this paper results by inserting special norms and neglecting lower bounds. A difficulty arises by the relative weakness of the condition xa implies f(x,t)v(t)x on the right hand side of the setdx/dt=f(x,t), where ... is any norm anda is a positive real constant. As a consequence of this, it seems no longer possible to use the usual techniques known from the literature on existence theorems and bounds for the solution of differential equations. To cope with this situation, a conditional version of the well-known theorem ofGronwall (also known by the name of Lemma ofBellman) will be derived.

---

Diese Arbeit ist Teil einer am Institut für Angewandte Mathematik der Technischen Hochschule München unter Anleitung von Herrn o. Prof. Dr. rer. nat. habil.J. Heinhold angefertigten Dissertation.     

A New Class of Depth-Size Optimal Parallel Prefix Circuits

Given n values x₁, x₂, ... ,x_n and an associative binary operation o, the prefix problem is to compute x₁ox₂o··· ox_i, 1in. Many combinational circuits for solving the prefix problem, called prefix circuits, have been designed. It has been proved that the size s(D(n)) and the depth d(D(n)) of an n-input prefix circuit D(n) satisfy the inequality d(D(n))+s(D(n))2n–2; thus, a prefix circuit is depth-size optimal if d(D(n))+s(D(n))=2n–2. In this paper, we construct a new depth-size optimal prefix circuit SL(n). In addition, we can build depth-size optimal prefix circuits whose depth can be any integer between d(SL(n)) and n–1. SL(n) has the same maximum fan-out lgn+1 as Snir's SN(n), but the depth of SL(n) is smaller; thus, SL(n) is faster. Compared with another optimal prefix circuit LYD(n), d(LYD(n))+2d(SL(n))d(LYD(n)). However, LYD(n) may have a fan-out of at most 2 lgn–2, and the fan-out of LYD(n) is greater than that of SL(n) for almost all n12. Because an operation node with greater fan-out occupies more chip area and is slower in VLSI implementation, in most cases, SL(n) needs less area and may be faster than LYD(n). Moreover, it is much easier to design SL(n) than LYD(n).     

Über die Konvergenz des Relaxationsverfahrens bei nicht-negativen und diagonaldominanten Matrizen

Zusammenfassung In der folgenden Arbeit werden zunächst die Begriffe Gesamtschrittverfahren, Einzelschrittverfahren und Relaxationsverfahren allgemein formuliert und dann auf allgemeine lineare Gleichungssysteme angewandt. Im Spezialfall einer Matrix mit verschwindender Hauptdiagonale erhält man so die bekanntenJacobi-, Gauss-Seidel- und Relaxationsverfahren. Satz 1 macht eine Aussage über die Konvergenz des Einzelschrittverfahrens bei allgemeinen, nicht-negativen Matrizen. Der Beweis verläuft ähnlich wie in einem bereits 1948 vonStein undRosenberg [2] behandelten Spezialfall. Als Korollar ergibt sich eine Aussage über die Konvergenz des Relaxationsverfahrens bei nicht-negativen Matrizen. Es wird ferner der Satz 2 über die Konvergenz des Relaxationsverfahrens bei diagonaldominanten Matrizen beweisen.

---

Summary In this paper we give a general definition what is meant by total-step-, single-step- and successive relaxation iterative method and we apply these concepts on systems of linear equations. In the special case of a matrix with zero diagonal entries we obtain the well knownJacobi-, Gauss-Seidel- and Relaxation iterative method. Theorem 1 gives conditions for the convergence of the singlestep-iterative method for general, non-negative matrices. The proof is similar to that given byStein andRosenberg in [2] (1948) for a special case. A corollary gives conditions for the convergence of the relaxation-iterative method for non-negative matrices. Further on we prove theorem 2 about the convergence of the relaxation-iterative method with diagonally dominant matrices.

     

Automated Deduction Techniques for the Management of Personalized Documents

This work is about a real-world application of automated deduction. The application is the management of documents (such as mathematical textbooks) as they occur in a readily available tool. In this Slicing Information Technology tool, documents are decomposed (sliced) into small units. A particular application task is to assemble a new document from such units in a selective way, based on the user's current interest and knowledge. It is argued that this task can be naturally expressed through logic, and that automated deduction technology can be exploited for solving it. More precisely, we rely on first-order clausal logic with some default negation principle, and we propose a model computation theorem prover as a suitable deduction mechanism. Beyond solving the task at hand as such, with this work we contribute to the quest for arguments in favor of automated deduction techniques in the real world. Also, we argue why we think that automated deduction techniques are the best choice here.     

Modelling structures in generic space, a condition for adaptiveness of monitoring cognitive agent

The adaptiveness of agents is one of the basic conditions for the autonomy. This paper describes an approach of adaptiveness forMonitoring Cognitive Agents based on the notion of generic spaces. This notion allows the definition of virtual generic processes so that any particular actual process is then a simple configuration of the generic process, that is to say a set of values of parameters. Consequently, generic domain ontology containing the generic knowledge for solving problems concerning the generic process can be developed. This lead to the design of Generic Monitoring Cognitive Agent, a class of agent in which the whole knowledge corpus is generic. In other words, modeling a process within a generic space becomes configuring a generic process and adaptiveness becomes genericity, that is to say independence regarding technology. In this paper, we present an application of this approach on Sachem, a Generic Monitoring Cognitive Agent designed in order to help the operators in operating a blast furnace. Specifically, the NeuroGaz module of Sachem will be used to present the notion of a generic blast furnace. The adaptiveness of Sachem can then be noted through the low cost of the deployment of a Sachem instance on different blast furnaces and the ability of NeuroGaz in solving problem and learning from various top gas instrumentation.     

Surface representation for the graphical display of structured data

In many applications one has a set of discrete points at which some variable such as pressure or velocity is measured. In order to graphically represent and display such data (say, as contours of constant pressure), the discrete data must be represented by a smooth function. This continuous surface can then be evaluated at any point for graphical display. Sometimes data are arbitrarily located except that they occur along non-intersecting lines, an example occurring in wind tunnel tests where data are recorded at plug taps on an aircraft body. An algorithm is developed for this type of structured data problem and illustrated by means of color computer graphics.     

Adding a temporal dimension to a logic system

We introduce a methodology whereby an arbitrary logic system L can be enriched with temporal features to create a new system T(L). The new system is constructed by combining L with a pure propositional temporal logic T (such as linear temporal logic with Since and Until) in a special way. We refer to this method as adding a temporal dimension to L or just temporalising L. We show that the logic system T(L) preserves several properties of the original temporal logic like soundness, completeness, decidability, conservativeness and separation over linear flows of time. We then focus on the temporalisation of first-order logic, and a comparison is make with other first-order approaches to the handling of time.     

A BMC-based formulation for the scheduling problem of hardware systems

Hardware scheduling is a well-known and well-studied problem. This paper defines a new SAT-based formulation of automata-based scheduling and proposes for the first time a completely new resolution algorithm based on SAT solvers and bounded model checking (BMC).The new formulation is specifically suited to control-dominated applications. Alternative executions are modeled as concurrency, where alternative behaviors are followed in parallel. This approach produces single-path scheduling traces instead of standard treelike solutions, thus enabling the use of BMC. This choice, however, creates the problem that resource bounds are treated incorrectly, due to the artificial concurrency modeling alternative behaviors. We then discuss how to take this into account, either by modifying the SAT solver or by adding extra clauses. Thus we are able to exploit SAT-based BMC to find the desired minimum latency schedule.Our method shows significant improvements in terms of both computational efficiency and modeling power, when compared to the BDD-based approach, and in terms of the optimality of the results when compared to heuristic methods.     

Parallelism in Deductive Inference on Graph Structures

Practical realization of the methods of parallel inference on connection graphs and semantic networks in the first-order predicate logic is described. A system of parallel inference with the steamroller test is studied and inference results are analyzed.     

A geometric view of parametric linear programming

We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem () = min{c ^t x¦Ax =b + ¯b,x 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function (). As a consequence, the optimality intervals form a partition of the closed interval {; ¦()¦ < }. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of () is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.This research was partially funded by the United States Navy-Office of Naval Research under Contract N00014-87-K-0202. Its financial support is gratefully acknowledged.     

Proof strategies in linear logic

Linear logic, introduced by J.-Y. Girard, is a refinement of classical logic providing means for controlling the allocation of resources. It has aroused considerable interest from both proof theorists and computer scientists. In this paper we investigate methods for automated theorem proving in propositional linear logic. Both the bottom-up (tableaux) and top-down (resolution) proof strategies are analyzed. Various modifications of sequent rules and efficient search strategies are presented along with the experiments performed with the implemented theorem provers.     

Parallel complexity of logical query programs

We consider the parallel time complexity of logic programs without function symbols, called logical query programs, or Datalog programs. We give a PRAM algorithm for computing the minimum model of a logical query program, and show that for programs with the polynomial fringe property, this algorithm runs in time that is logarithmic in the input size, assuming that concurrent writes are allowed if they are consistent. As a result, the linear and piecewise linear classes of logic programs are inN C. Then we examine several nonlinear classes in which the program has a single recursive rule that is an elementary chain. We show that certain nonlinear programs are related to GSM mappings of a balanced parentheses language, and that this relationship implies the polynomial fringe property; hence such programs are inN C Finally, we describe an approach for demonstrating that certain logical query programs are log space complete forP, and apply it to both elementary single rule programs and nonelementary programs.Supported by NSF Grant IST-84-12791, a grant of IBM Corporation, and ONR contract N00014-85-C-0731.     

Constructing H4, a Fast Depth-Size Optimal Parallel Prefix Circuit

Given n values x ₁, x ₂,...,x _n and an associative binary operation , the prefix problem is to compute x ₁x ₂x _i, 1in. Prefix circuits are combinational circuits for solving the prefix problem. For any n-input prefix circuit D with depth d and size s, if d+s=2n–2, then D is depth-size optimal. In general, a prefix circuit with a small depth is faster than one with a large depth. For prefix circuits with the same depth, a prefix circuit with a smaller fan-out occupies less area and is faster in VLSI implementation. This paper is on constructing parallel prefix circuits that are depth-size optimal with small depth and small fan-out. We construct a depth-size optimal prefix circuit H4 with fan-out 4. It has the smallest depth among all known depth-size optimal prefix circuits with a constant fan-out; furthermore, when n136, its depth is less than, or equal to, those of all known depth-size optimal prefix circuits with unlimited fan-out. A size lower bound of prefix circuits is also derived. Some properties related to depth-size optimality and size optimality are introduced; they are used to prove that H4 is depth-size optimal.     

Human–Machine Interaction in Intelligent Robotic Systems: A Unifying Consideration with Implementation Examples

In this paper, we propose a two-layer sensor fusion scheme for multiple hypotheses multisensor systems. To reflect reality in decision making, uncertain decision regions are introduced in the hypotheses testing process. The entire decision space is partitioned into distinct regions of correct, uncertain and incorrect regions. The first layer of decision is made by each sensor indepedently based on a set of optimal decision rules. The fusion process is performed by treating the fusion center as an additional virtual sensor to the system. This virtual sensor makes decision based on the decisions reached by the set of sensors in the system. The optimal decision rules are derived by minimizing the Bayes risk function. As a consequence, the performance of the system as well as individual sensors can be quantified by the probabilities of correct, incorrect and uncertain decisions. Numerical examples of three hypotheses, two and four sensor systems are presented to illustrate the proposed scheme.     

Iterative Lösung nichtlinearer Gleichungssysteme und Diskretisierungsverfahren bei elliptischen Differentialgleichungen

Zusammenfassung Die für lineare Gleichungssysteme bekannten Sätze über die Konvergenz von Successive overrelaxation methods (SOR) und Alternating direction methods (ADI) werden auf analoge Verfahren bei nichtlinearen Gleichungssystemen übertragen. Dabei können allerdings, wie auch bei anderen Iterationsverfahren für nichtlineare Probleme, nur sogenannte lokale Konvergenz-sätze bewiesen werden. Es wird weiter untersucht, wann es Differenzapproximationen für nichtlineare elliptische Differentialgleichungen gibt, derart, daß die Funktionalmatrix des resultierenden nichtlinearen Gleichungssystems symmetrisch und positiv definit ist. Dann konvergieren SOR für 0<<2 und ADI. Solche Approximationen können zumindest für allgemeinere halblineare Gleichungen hergeleitet werden, wenn die DifferentialgleichungEulersche Gleichung eines Variationsproblems ist. Am Schluß findet sich ein Beispiel.

---

Iterative solutions for systems of non-linear equation and discretisation of elliptic differential equations

Summary The theorems, known for systems of linear equations, on the convergence of Successive overrelaxation methods (SOR) and Alternating direction methods (ADI) are transferred to analogous methods for systems of nonlinear equations. In doing so, only so-called local convergence theorems can be proved, however, as it is the case with other iteration procedures for nonlinear problems. Furthermore, it is examined under what conditions there exist difference approximations for nonlinear elliptic differential equations, such as to the functional matrix of the resulting system of nonlinear equations being symmetric and positive definite. SOR for 0<<2 and ADI are then converging. Such approximations can be derived at least for more general semilinear equations if the differential equation is theEuler equation of a variational problem. Finally, an example is given.

---

---

Herrn Professor Dr.L. Collatz anläßlich seines 60. Geburtstages gewidmet     

The growth of configurations

The transition ruleF of a cellular automaton may sometimes be regarded as a rule of growth of a crystal from a seed. A study is made of the iterates,F,F ² .For certain one-dimensional growth rules, the limiting shapes of the crystals are computed, and an asymptotic formula for the size of the crystal as a function of time is obtained.     

Periodicity and critical circuits in a generalized max-algebra setting

The notions introduced in Braker and Resing (1992), concerning periodicity of 2×2 matrices in a generalized setup, are extended to the case of general square matrices. The asymptotic behaviour of a series of matrices is related to a particular type of circuit, called a generalized critical circuit, which is a circuit that is critical with respect to all the nodes it contains. It is shown that the asymptotic behaviour is determined only by the lengths of some generalized critical circuits, the weights of arcs in these circuits and some critical paths. This formulation is an appealing extension of the concepts of periodicity and critical circuit in the usual max algebra. The term asymptotic may give the impression that the described behaviour is only reached after a long or even infinite transient. However, the periodic regular part may be reached in only a few steps, after which the generalized critical circuits determine the future behaviour. As a corollary we obtain that each aperiodic graph contains at least one generalized critical circuit.     

Metrics for quality and concurrency in object-based systems

This paper defines metrics for object-based systems. A hierarchical, abstract representation of object-based software is presented, and is used to define programming-language-independent metrics formulas. Novel techniques are given for measuring information hiding, cohesion, encapsulation, coupling, object-orientedness, maintainability, and potential concurrency among and within objects. The metrics are useful for guiding design optimization. Additionally, the concurrency metrics are useful for guiding object distribution for execution on concurrent hardware platforms. A toolset that computes several of the metrics is also described.     

Revealing Translators' Knowledge: Statistical Methods in Constructing Practical Translation Lexicons for Language and Speech Processing

Parallel corpora encode extremely valuable linguistic knowledge about paired languages, both in terms of vocabulary and syntax. A professional translation of a text represents a series of linguistic decisions made by the translator in order to convey as faithfully as possible the meaning of the original text and to produce a natural text from the perspective of a native speaker of the target language. The naturalness of a translation implies not only the grammaticality of the translated text, but also style and cultural or social specificity.We describe a program that exploits the knowledge embedded in the parallel corpora and produces a set of translation equivalents (a translation lexicon). The program uses almost no linguistic knowledge, relying on statistical evidence and some simplifying assumptions. Our experiments were conducted on the MULTEXT-EAST multilingual parallel corpus (Orwell's 1984), and the evaluation of the system performance is presented in some detail in terms of precision, recall and processing time. We conclude by briefly mentioning some applications of the automatic extracted lexicons for text and speech processing.