An efficient fault-tolerant decentralized commit protocol for single site failure

To maintain consistency on a distributed database system, a commit protocol is often employed to ensure that either all the sub-transactions of a transaction commit or all abort. Special care needs to be taken to ensure the correct functioning of a commit protocol in the face of node failures during the execution of the protocol. A protocol is said to be fault-tolerant if it properly commits or aborts, even if nodes fail.In this paper, we present a fault tolerant decentralized commit protocol which is message optimal in the absence of failures. Furthermore, the protocol (FTDCP) ensures that all sites can achieve a consistent final decision by at most 4 extra messages in the single site failure situation.     

KT-nearfields of rank 2

Summary Nearfields of rank 2 over their kernel which are not Dickson nearfields have recently been constructed by H. Zassenhaus. Here it is shown that KT-nearfields of rank 2 over their kernels and of characteristic 2 are necessarily Dickson nearfields which are coupled to quadratic field extensions and their Dickson group is isomorphic to ₂. Using results of Gröger one obtains all KT-nearfields of rank 2 over the field of rational numbers.     

Some regularity properties of algorithms and additive functions with respect to them

Summary The paper deals with the behaviour of the so-called algorithms with respect to interval filling sequences A connection is established between the uniquely representable points and the continuity points of the algorithms; also strong continuity properties on monotonic algorithms are proved. Finally the results are applied to additive functions. The theorems extend some former results by the authors, by I. Kátai and by A. Járai.Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth     

Quadratically constrained least squares and quadratic problems

Summary We consider the following problem: Compute a vectorx such that Ax–b₂=min, subject to the constraint x₂=. A new approach to this problem based on Gauss quadrature is given. The method is especially well suited when the dimensions ofA are large and the matrix is sparse.It is also possible to extend this technique to a constrained quadratic form: For a symmetric matrixA we consider the minimization ofx ^T A x–2b ^T x subject to the constraint x₂=.Some numerical examples are given.This work was in part supported by the National Science Foundation under Grant DCR-8412314 and by the National Institute of Standards and Technology under Grant 60NANB9D0908.     

A mixed version of Menger's theorem

An(a, b)-n-fan means a union ofn internally disjoint paths. Menger's theorem states that a graphG has an(a, b)-n-fan if and only ifG isn-connected betweena andb. We show thatG contains edge-disjoint(a, b)-n-fans if and only if for anyk withk0min{n–1, |V(G)|–2} and for any subsetX ofV(G)-{a, b} with cardinalityk, G-X is (n-k)-edge-connected betweena andb.     

Trees in tournaments

Letf(n) be the smallest integer such that every tournament of orderf(n) contains every oriented tree of ordern. Sumner has just conjectures thatf(n)=2n–2, and F. K. Chung has shown thatf(n)(1+o(1))nlog₂ n. Here we show thatf(n)12n andf(n)(4+o(1))n.     

The left-definite Legendre type boundary problem

The left-definite Legendre type boundary problem concerns the study of a fourth-order singular differential expressionM _k [–] in a weighted Sobolev spaceH generated by a Dirichlet inner product. The fourth-order differential equation

An Ω(n 4/3) lower bound on the randomized complexity of graph properties

We improve King's (n ^5/4) lower bound on the randomized decision tree complexity of monotone graph properties to (n ^4/3). The proof follows Yao's approach and improves it in a different direction from King's. At the heart of the proof are a duality argument combined with a new packing lemma for bipartite graphs.The paper was written while the author was a graduate student at the University of Chicago and was completed at M.I.T. The work was supported in part by NSF under GRANT number NSF 5-27561, the Air Force under Contract OSR-86-0076 and by DIMACS (Center for Discret Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648.     

Harmonic maps from compact Kähler manifolds to exceptional hyperbolic spaces

It has been conjectured that a lattice in a noncompact group of real rank one, other than SU(1,n), cannot be isomorphic to the fundamental group of a compact Kähler manifold; moreover, it is known to be true for SO(1,n). In this note it is shown that this conjecture also holds for the case of uniform lattices in F_4(?20), the group of isometries of the Cayley hyperbolic plane. The result is a consequence of a classification theorem for harmonic maps between Kähler and Cayley hyperbolic manifolds.     

On the polynomial τ-functions for the KP hierarchy and the bispectral property

We show that the -functions obtained from Schur polynomials lead to wave functions w(x ₁, x ₂, ... ; k) that possess the following bispectral property: There exists a differential operator B{k,_k}, independent of x ₁ , such that B{k,_k}w = {x ₁}w, where {x ₁} is independent of k. This extends for the KP hierarchy some earlier results of J. J. Duistermaat and F. A. Grünbaum for the rational solutions of KdV and of P. Wright for certain rational solutions of the generalized KdV equations.