Routing complexity of faulty networks

One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This article investigates how big the failure probability can be, before the capability to efficiently find a path in the network is lost. Our main results show tight upper and lower bounds for the failure probability, which permits routing both for the hypercube and for the d‐dimensional mesh. We use tools from percolation theory to show that in the d‐dimensional mesh, once a giant component appears—efficient routing is possible. A different behavior is observed when the hypercube is considered. In the hypercube there is a range of failure probabilities in which short paths exist with high probability, yet finding them must involve querying essentially the entire network. Thus the routing complexity of the hypercube shows an asymptotic phase transition. The critical probability with respect to routing complexity lies in a different location than that of the critical probability with respect to connectivity. Finally we show that an oracle access to links (as opposed to local routing) may reduce significantly the complexity of the routing problem. We demonstrate this fact by providing tight upper and lower bounds for the complexity of routing in the random graph G_n,p. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Elementary Pairs of Primitive Normal Theories

The main objective of the paper is proving that classes of primitive normal, primitive bound, antiadditive, and additive theories are closed under P-expansions. This phenomenon is quite remarkable, for the main structure classes of theories studied within model theory (such as stable, totally transcendental, etc.) do not possess such a property. Furthermore, it is proved that primitive bound theories are P-stable, and we furnish an example of a primitive bound theory with models that are not primitive bound.     

Multilinear enumerative techniques

When S is a finite set and G a finite group acting on S, we consider the problem of rejecting isomorphs in a G-stable subset of S. In previous work we developed a linear algebraic context for this problem by constructing the finite dimensional vector spaceF ^s whereF is a field of characteristic zero. When S is a finite function space, or a finite direct product of finite function spacesF ^s acquires a multilinear structure By various specializations ofG and S and by applications of results which have appeared elsewhere, identities of Sheehan, deBruijn and P61ya are obtained. Furthermore, these same techniques are applied to examples which do not have a clear resolution using the more common formulas     

On Uniform Global Error Bounds for Convex Inequalities

This paper studies the existence of a uniform global error bound when a convex inequality g 0, where g is a closed proper convex function, is perturbed. The perturbation neighborhoods are defined by small arbitrary perturbations of the epigraph of its conjugate function. Under certain conditions, it is shown that for sufficiently small arbitrary perturbations the perturbed system is solvable and there exists a uniform global error bound if and only if g satisfies the Slater condition and the solution set is bounded or its recession function satisfies the Slater condition. The results are used to derive lower bounds on the distance to ill-posedness.     

An Improved Lower Bound for the Multimedian Location Problem

We consider the problem of locating, on a network, n new facilities that interact with m existing facilities. In addition, pairs of new facilities interact. This problem, the multimedian location problem on a network, is known to be NP-hard. We give a new integer programming formulation of this problem, and show that its linear programming relaxation provides a lower bound that is superior to the bound provided by a previously published formulation. We also report results of computational testing with both formulations.     

Directional derivatives of difference functions of nonsmooth max-functions

In this paper, we give an upper estimate for the Clarke-Rockafellar directional derivatives of a function of the form f - g, where f, g are max-functions defined by locally Lipschitz but not necessarily differentiable functions on a closed convex set in a Euclidean space. As an application, we give a sufficient condition for f - g to have an error bound.     

On Banach spaces whose norm-open sets are -sets in the weak topology

We investigate non-separable Banach spaces whose norm-open sets are countable unions of sets closed in the weak topology and a narrower class of Banach spaces with a network for the norm topology which is σ-discrete in the weak topology. In particular, we answer a question of Arhangel'skii exhibiting various examples of non-separable function spaces C(K) with a σ-discrete network for the pointwise topology and (consistently) we answer some questions of Edgar and Oncina concerning Borel structures and Kadec renormings in Banach spaces.     

Symmetry property of the throughput in closed tandem queueing networks with finite buffers

In this paper we consider closed tandem queueing networks with finite buffers and blocking before service. With this type of blocking, a server is allowed to start processing a job only if there is an empty space in the next buffer. It was recently conjectured that the throughput of such networks is symmetrical with respect to the population of the network. That is, the throughput of the network with population N is the same as that with population C − N, where C is the total number of buffer spaces in the network. The main purpose of this paper is to prove this result in the case where the service time distributions are of phase type (PH-distribution). The proof is based on the comparison of the sample paths of the network with populations N and C − N. Finally, we also show that this symmetry property is related to a reversibility property of this class of networks.     

Almost Integrally Closed Domains

Abstract

A domain R is called almost integrally closed if R is integrally closed in R _P for each nonzero P ∈ Spec(R). Arbitrary quasilocal domains of (Krull) dimension 1 and arbitrary integrally closed domains are examples of almost integrally closed domains. There are no other examples in the contexts of Noetherian, one-dimensional or pseudo-valuation domains, as a consequence of the fact that any almost integrally closed domain that is not integrally closed has at most one height 1 prime ideal. However, a pullback example shows that a non-integrally closed domain that is almost integrally closed need not be semiquasilocal or of dimension at most 1. By analyzing the behavior of the almost integrally closed property for CPI-extensions, we obtain a characterization of the almost integrally closed locally divided domains. Applications are given to the case of G-domains. It also follows that if a divided domain R is not a field, then R is almost integrally closed if and only if some (resp., each) nonzero P ∈ Spec(R) is such that R _P is almost integrally closed and R is integrally closed in R _P .     

Thick subcategories of modules over commutative noetherian rings (with an appendix by Srikanth Iyengar)

For a commutative noetherian ring A, we compare the support of a complex of A-modules with the support of its cohomology. This leads to a classification of all full subcategories of A-modules which are thick (that is, closed under taking kernels, cokernels, and extensions) and closed under taking arbitrary direct sums. In addition, subcategories of A-modules that are closed under taking submodules, extensions, and direct unions are classified via associated prime ideals.     

Unitary designs and codes

A unitary design is a collection of unitary matrices that approximate the entire unitary group, much like a spherical design approximates the entire unit sphere. In this paper, we use irreducible representations of the unitary group to find a general lower bound on the size of a unitary t-design in U(d), for any d and t. We also introduce the notion of a unitary code—a subset of U(d) in which the trace inner product of any pair of matrices is restricted to only a small number of distinct absolute values—and give an upper bound for the size of a code with s inner product values in U(d), for any d and s. These bounds can be strengthened when the particular inner product values that occur in the code or design are known. Finally, we describe some constructions of designs: we give an upper bound on the size of the smallest weighted unitary t-design in U(d), and we catalogue some t-designs that arise from finite groups.      

Generating Random Vectors in (ℤ/<Emphasis Type="Italic">p</Emphasis>ℤ)<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript> via an Affine Random Process

This paper considers some random processes of the form X _n+1=T X _n +B _n (mod p) where B _n and X _n are random variables over (ℤ/pℤ) ^d and T is a fixed d×d integer matrix which is invertible over the complex numbers. For a particular distribution for B _n , this paper improves results of Asci to show that if T has no complex eigenvalues of length 1, then for integers p relatively prime to det (T), order (log p)² steps suffice to make X _n close to uniformly distributed where X ₀ is the zero vector. This paper also shows that if T has a complex eigenvalue which is a root of unity, then order p ^b steps are needed for X _n to get close to uniformly distributed for some positive value b≤2 which may depend on T and X ₀ is the zero vector.     

Some remarks on conjugate closed groups

Let G be a group. In this note we define conjugate closed groups, which are briefly called CC — Groups. These groups form a proper subclass of T — Groups. We prove that if G = Z(G) × H, then G is conjugate closed if and only if H is conjugate closed. We also show that a finite group G is semisimple, conjugate closed and perfect if and only if it is a direct product of non-abelian and simple groups.     

On the Convergence of a Trust-Region Method for Solving Constrained Nonlinear Equations with Degenerate Solutions

This paper presents a trust-region method for solving the constrained nonlinear equation F(x) = 0, x , where R ⁿ is a nonempty and closed convex set, F is defined on the open set containing and is continuously differentiable. The iterates generated by the method are feasible. The method is globally and quadratically convergent under local error bounded assumption on F. The results obtained are extensions of the work of Yamashita Fukushima (Ref. 1) and Fan Yuan (Ref. 2) for unconstrained nonlinear equations. Numerical results show that the new algorithm works quite well.     

Bounds on Codes Derived by Counting Components in Varshamov Graphs

We are interested in improving the Varshamov bound for finite values of length n and minimum distance d. We employ a counting lemma to this end which we find particularly useful in relation to Varshamov graphs. Since a Varshamov graph consists of components corresponding to low weight vectors in the cosets of a code it is a useful tool when trying to improve the estimates involved in the Varshamov bound. We consider how the graph can be iteratively constructed and using our observations are able to achieve a reduction in the over-counting which occurs. This tightens the lower bound for any choice of parameters n, k, d or q and is not dependent on information such as the weight distribution of a code. This work is taken from the author’s thesis [10]     

Proximal Set-Open Topologies on Partial Maps

Let X, Y be T ₁ topological spaces. A partial map from X to Y is a continuous function f whose domain is a subspace D of X and whose codomain is Y. Let P(X, Y) be the set of partial maps with domains in a fixed class D. In analogy with the global case, we introduce on P(X, Y), whatever be the nature of the domain class D, new function space topologies, the proximal set-open topologies, briefly PSOTs, deriving from general networks on X and proximity on Y by replacing inclusion with strong inclusion. The PSOTs include the already known generalized compact-open topology on partial maps with closed domains. When domains are supposed closed, the network α closed and hereditarily closed and the proximity δ on Y Efremovic, then the PSOT attached to α and δ is uniformizable iff α is a Urysohn family in X. This revised version was published online in June 2006 with corrections to the Cover Date.     

Closed Projections and Peak Interpolation for Operator Algebras

The closed one-sided ideals of a C ^*-algebra are exactly the closed subspaces supported by the orthogonal complement of a closed projection. Let A be a (not necessarily selfadjoint) subalgebra of a unital C ^*-algebra B which contains the unit of B. Here we characterize the right ideals of A with left contractive approximate identity as those subspaces of A supported by the orthogonal complement of a closed projection in B ^** which also lies in . Although this seems quite natural, the proof requires a set of new techniques which may be viewed as a noncommutative version of the subject of peak interpolation from the theory of function spaces. Thus, the right ideals with left approximate identity are closely related to a type of peaking phenomena in the algebra. In this direction, we introduce a class of closed projections which generalizes the notion of a peak set in the theory of uniform algebras to the world of operator algebras and operator spaces.     

Indestructibility and stationary reflection

If κ < λ are such that κ is a strong cardinal whose strongness is indestructible under κ ‐strategically closed forcing and λ is weakly compact, then we show that A = {δ < κ | δ is a non‐weakly compact Mahlo cardinal which reflects stationary sets} must be unbounded in κ. This phenomenon, however, need not occur in a universe with relatively few large cardinals. In particular, we show how to construct a model where no cardinal is supercompact up to a Mahlo cardinal in which the least supercompact cardinal κ is also the least strongly compact cardinal, κ 's strongness is indestructible under κ ‐strategically closed forcing, κ 's supercompactness is indestructible under κ ‐directed closed forcing not adding any new subsets of κ, and δ is Mahlo and reflects stationary sets iff δ is weakly compact. In this model, no strong cardinal δ < κ is indestructible under δ ‐strategically closed forcing. It therefore follows that it is relatively consistent for the least strong cardinal κ whose strongness is indestructible under κ ‐strategically closed forcing to be the same as the least supercompact cardinal, which also has its supercompactness indestructible under κ ‐directed closed forcing not adding any new subsets of κ (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Large Closed Queueing Networks in Semi-Markov Environment and Their Application

The paper studies closed queueing networks containing a server station and k client stations. The server station is an infinite server queueing system, and client stations are single-server queueing systems with autonomous service, i.e. every client station serves customers (units) only at random instants generated by a strictly stationary and ergodic sequence of random variables. The total number of units in the network is N. The expected times between departures in client stations are (N μ _j )⁻¹. After a service completion in the server station, a unit is transmitted to the jth client station with probability p _j (j=1,2,…,k), and being processed in the jth client station, the unit returns to the server station. The network is assumed to be in a semi-Markov environment. A semi-Markov environment is defined by a finite or countable infinite Markov chain and by sequences of independent and identically distributed random variables. Then the routing probabilities p _j (j=1,2,…,k) and transmission rates (which are expressed via parameters of the network) depend on a Markov state of the environment. The paper studies the queue-length processes in client stations of this network and is aimed to the analysis of performance measures associated with this network. The questions risen in this paper have immediate relation to quality control of complex telecommunication networks, and the obtained results are expected to lead to the solutions to many practical problems of this area of research.