On optimal management of resources in distributed networks

In a network of processors, a distributed operating system must handle the management of shared resources. In this paper, it is shown how to solve this problem in using the model previously introduced in [1]. This model (interconnection of N Markov chains each representing locally a distributed process) allows us to prove the good functioning properties for some distributed problems such as the mutual exclusion problem and the deadlock problem, We also prove that fairness is a basic notion for setting the model’s parameters and obtain an optimal working of the network.     

On optimization of continuous-time Markov networks in distributed computing

The paper presents a new stochastic model for studying the optimization of functioning rules in distributed computing. In this model a network is represented by a finite number of continuous-time homogeneous Markov processes which are connected by relations between entries of their intensity matrices. Good functioning rules are those optimizing a guide function defined according to the context. Two specific optimization problems are studied: a problem of resource allocation with conflicts between processes, and a problem of access to shared resources. The latter is a linearly constrained nonconvex problem with an objective function which is a sum of ratios of linear functions of special form.     

Constructing disjoint paths on expander graphs

In a typical parallel or distributed computation model processors are connected by a spars interconnection network. To establish open-line communication between pairs of processors that wish to communicate interactively, a set of disjoint paths has to be constructed on the network. Since communication needs vary in time, paths have to be dynamically constructed and destroyed.We study the complexity of constructing disjoint paths between given pairs of vertices on expander interconnection graphs. These graphs have been shown before to possess desirable properties for other communication tasks.We present a sufficient condition for the existence ofKn ^Q edge-disjoint paths connecting any set ofK pairs of vertices on an expander graph, wheren is the number of vertices and<1 is some constant. We then show that the computational problem of constructing these paths lies in the classes Deterministic-P and Random-P C.Furthermore, we show that the set of paths can be constructed in probabilistic polylog time in the parallel-distributed model of computation, in which then participating processors reside in the nodes of the communication graph and all communication is done through edges of the graph. Thus, the disjoint paths are constructed in the very computation model that uses them.Finally, we show how to apply variants of our parallel algorithms to find sets ofvertex-disjoint paths when certain conditions are satisfied.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731.     

A note on testing hypotheses for stationary processes in the frequency domain

In a recent paper, Eichler (2008) [11] considered a class of non- and semiparametric hypotheses in multivariate stationary processes, which are characterized by a functional of the spectral density matrix. The corresponding statistics are obtained using kernel estimates for the spectral distribution and are asymptotically normally distributed under the null hypothesis and local alternatives. In this paper, we derive the asymptotic properties of these test statistics under fixed alternatives. In particular, we also show weak convergence but with a different rate compared to the null hypothesis. We also discuss potential statistical applications of the asymptotic theory by means of a small simulation study.     

Image recovery via total variation minimization and related problems

Summary. We study here a classical image denoising technique introduced by L. Rudin and S. Osher a few years ago, namely the constrained minimization of the total variation (TV) of the image. First, we give results of existence and uniqueness and prove the link between the constrained minimization problem and the minimization of an associated Lagrangian functional. Then we describe a relaxation method for computing the solution, and give a proof of convergence. After this, we explain why the TV-based model is well suited to the recovery of some images and not of others. We eventually propose an alternative approach whose purpose is to handle the minimization of the minimum of several convex functionals. We propose for instance a variant of the original TV minimization problem that handles correctly some situations where TV fails. Received December 21, 1995 / Revised version February 26, 1996     

A combinatorial approach to complexity

We present a problem of construction of certain intersection graphs. If these graphs were explicitly constructed, we would have an explicit construction of Boolean functions of large complexity.     

Authentication schemes from actions on graphs, groups, or rings

We propose a couple of general ways of constructing authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several authentication schemes with long-term private keys where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include the Graph Colorability problem, the Diophantine problem, and many others.     

Distributed near-optimal matching

In this paper, we consider the following distributed bipartite matching problem: LetG=(L,R;E) be a bipartite graph in which boys are partL (left nodes), and girls are partR (right nodes.) There is an edge(l _i ,r _j )E iff boyl _i is interested in girlr _j . Every boyl _i will propose to a girlr _j among all those he is interested in, i.e., his adjacent right nodes in the bipartite graphG. If several boys propose to the same girl, only one of them will be accepted by the girl. We assume that none of the boys communicate with others. This matching problem is typical of distributed computing under incomplete information: Each boy only knows his own preference but none of the others. We first study the one-round matching problem: each boy proposes to at most one girl, so that the total number of girls receiving a proposal is maximized. If the maximum matching isM, then no deterministic algorithm can produce a matching of size not bounded by a constant, but a randomized algorithm achieves — and this is shown optimal by an adversary argument. If we allow many rounds in matching, with the senders learning from their failures, then, for deterministic algorithms, the ratio (of the optimal solution to the solution of the algorithm) is unbounded when the number of rounds is smaller than (G), and becomes bounded (two) at the (G)-th round. In contrast, an extension of the one-round randomized algorithm establishes that there is no such discontinuity in the randomized case. This randomized result is also matched by an upper bound of asymptotically the same order.     

The average-case analysis of some on-line algorithms for bin packing

In this paper we give tighter bounds than were previously known for the performance of the bin packing algorithms Best Fit and First Fit when the inputs are uniformly distributed on [0, 1]. We also give a general lower bound for the performance of any on-line bin packing algorithm on this distribution. We prove these results by analyzing optimal matchings on points randomly distributed in a unit square. We give a new lower bound for the up-right matching problem. A preliminary version of this paper appeared inProc. 25th IEEE Symposium on Foundations of Computer Science, 193–200. This research was done while the author was at the Massachusetts Institute of Technology Dept. of Mathematics and was supported by a NSF Graduate Fellowship and by Air Force grant OSR-82-0326.     

Disjoint paths in a rectilinear grid

We give a good characterization and a good algorithm for a special case of the integral multicommodity flow problem when the graph is defined by a rectangle on a rectilinear grid. The problem was raised by engineers motivated by some basic questions of constructing printed circuit boards.     

A penalized criterion for variable selection in classification

In this paper, the problem of variable selection in classification is considered. On the basis of recent developments in model selection theory, we provide a criterion based on penalized empirical risk, where the penalization explicitly takes into account the number of variables of the considered models. Moreover, we give an oracle-type inequality that non-asymptotically guarantees the performance of the resulting classification rule. We discuss the optimality of the proposed criterion and present an application of the main result to backward and forward selection procedures.     

An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification*

Given a spanning tree T of some graph G, the problem of minimum spanning tree verification is to decide whether T = MST(G). A celebrated result of Komlós shows that this problem can be solved with a linear number of comparisons. Somewhat unexpectedly, MST verification turns out to be useful in actually computing minimum spanning trees from scratch. It is this application that has led some to wonder whether a more flexible version of MST verification could be used to derive a faster deterministic minimum spanning tree algorithm. In this paper we consider the online MST verification problem in which we are given a sequence of queries of the form “Is e in the MST of T ∪{e}?”, where the tree T is fixed. We prove that there are no linear-time solutions to the online MST verification problem, and in particular, that answering m queries requires Ω(mα(m,n)) time, where α(m,n) is the inverse-Ackermann function and n is the size of the tree. On the other hand, we show that if the weights of T are permuted randomly there is a simple data structure that preprocesses the tree in expected linear time and answers queries in constant time. * A preliminary version of this paper appeared in the proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS 2002), pages 155–163. † This work was supported by Texas Advanced Research Program Grant 003658-0029-1999, NSF Grant CCR-9988160, and an MCD Graduate Fellowship.     

Topological sweep of the complete graph

We present a novel, simple and easily implementable algorithm to report all intersections in an embedding of a complete graph. For graphs with N vertices and complexity K measured as the number of segments of the embedding, the running time of the algorithm is Θ(K+NM), where M is the maximum number of edges cut by any vertical line. Our algorithm handles degeneracies, such as vertical edges or multiply intersecting edges, without requiring numerical perturbations to achieve general position.The algorithm is based on the sweep line technique, one of the most fundamental techniques in computational geometry, where an imaginary line passes through a given set of geometric objects, usually from left to right. The algorithm sweeps the graph using a topological line, borrowing the concept of horizon trees from the topological sweep method [H. Edelsbrunner, L.J. Guibas, Topologically sweeping an arrangement, J. Comput. Syst. Sci. 38 (1989) 165-194; J. Comput. Syst. Sci. 42 (1991) 249-251 (corrigendum)].The novelty in our approach is to control the topological line through the use of the moving wall that separates at any time the graph into two regions: the region of known structure, in front of the moving wall, and the region that may contain intersections generated by edges-that have not yet been registered in the sweep process-behind the wall.Our method has applications to graph drawing and for depth-based statistical analysis, for computing the simplicial depth median for a set of N data points [G. Aloupis, S. Langerman, M. Soss, G. Toussaint, Algorithms for bivariate medians and a Fermat-Torricelli problem for lines, Comp. Geom. Theory Appl. 26 (1) (2003) 69-79].We present the algorithm, its analysis, experimental results and extension of the method to general graphs.     

Representing orders on the plane by translating convex figures

Given a finite collection of disjoint, convex figures on the plane, is it possible to assign to each a single direction of motion so that this collection of figures may be separated, through an arbitrary large distance, by translating each figure one at a time, along its assigned direction? We present a computational model for this separability problem based on the theory of ordered sets.     

Heath–Jarrow–Morton modelling of longevity bonds and the risk minimization of life insurance portfolios

This paper has two parts. In the first, we apply the Heath–Jarrow–Morton (HJM) methodology to the modelling of longevity bond prices. The idea of using the HJM methodology is not new. We can cite Cairns et al. [Cairns A.J., Blake D., Dowd K, 2006. Pricing death: framework for the valuation and the securitization of mortality risk. Astin Bull., 36 (1), 79–120], Miltersen and Persson [Miltersen K.R., Persson S.A., 2005. Is mortality dead? Stochastic force of mortality determined by arbitrage? Working Paper, University of Bergen] and Bauer [Bauer D., 2006. An arbitrage-free family of longevity bonds. Working Paper, Ulm University]. Unfortunately, none of these papers properly defines the prices of the longevity bonds they are supposed to be studying. Accordingly, the main contribution of this section is to describe a coherent theoretical setting in which we can properly define these longevity bond prices. A second objective of this section is to describe a more realistic longevity bonds market model than in previous papers. In particular, we introduce an additional effect of the actual mortality on the longevity bond prices, that does not appear in the literature. We also study multiple term structures of longevity bonds instead of the usual single term structure. In this framework, we derive a no-arbitrage condition for the longevity bond financial market. We also discuss the links between such HJM based models and the intensity models for longevity bonds such as those of Dahl [Dahl M., 2004. Stochastic mortality in life insurance: Market reserves and mortality-linked insurance contracts, Insurance: Math. Econom. 35 (1) 113–136], Biffis [Biffis E., 2005. Affine processes for dynamic mortality and actuarial valuations. Insurance: Math. Econom. 37, 443–468], Luciano and Vigna [Luciano E. and Vigna E., 2005. Non mean reverting affine processes for stochastic mortality. ICER working paper], Schrager [Schrager D.F., 2006. Affine stochastic mortality. Insurance: Math. Econom. 38, 81–97] and Hainaut and Devolder [Hainaut D., Devolder P., 2007. Mortality modelling with Lévy processes. Insurance: Math. Econom. (in press)], and suggest the standard pricing formula of these intensity models could be extended to more general settings.In the second part of this paper, we study the asset allocation problem of pure endowment and annuity portfolios. In order to solve this problem, we study the “risk-minimizing” strategies of such portfolios, when some but not all longevity bonds are available for trading. In this way, we introduce different basis risks.     

A distributed combustion solver for engine simulations on grids

Multi-dimensional models for predictive simulations of modern engines are an example of multi-physics and multi-scale mathematical models, since lots of thermofluiddynamic processes in complex geometrical configurations have to be considered. Typical models involve different submodels, including turbulence, spray and combustion models, with different characteristic time scales. The predictive capability of the complete models depends on the accuracy of the submodels as well as on the reliability of the numerical solution algorithms. In this work we propose a multi-solver approach for reliable and efficient solution of the stiff Ordinary Differential Equation (ODE) systems arising from detailed chemical reaction mechanisms for combustion modeling. Main aim was to obtain high-performance parallel solution of combustion submodels in the overall procedure for simulation of engines on distributed heterogeneous computing platforms. To this aim we interfaced our solver with the CHEMKIN-II package and the KIVA3V-II code and carried out multi-computer simulations of realistic engines. Numerical experiments devoted to test reliability of the simulation results and efficiency of the distributed combustion solver are presented and discussed.     

Lower Bounds For Concurrent Zero Knowledge*

We consider zero knowledge interactive proofs in a richer, more realistic communication environment. In this setting, one may simultaneously engage in many interactive proofs, and these proofs may take place in an asynchronous fashion. It is known that zero-knowledge is not necessarily preserved in such an environment; we show that for a large class of protocols, it cannot be preserved. Any 4 round (computational) zero-knowledge interactive proof (or argument) for a non-trivial language L is not black-box simulatable in the asynchronous setting.* An abridge version of this work has appeared in [24].     

On simulation of tempered stable random variates

Various simulation methods for tempered stable random variates with stability index greater than one are investigated with a view towards practical implementation, in particular cases of very small scale parameter, which correspond to increments of a tempered stable Lévy process with a very short stepsize. Methods under consideration are based on acceptance-rejection sampling, a Gaussian approximation of a small jump component, and infinite shot noise series representations. Numerical results are presented to discuss advantages, limitations and trade-off issues between approximation error and required computing effort. With a given computing budget, an approximative acceptance-rejection sampling technique Baeumer and Meerschaert (2009) [11] is both most efficient and handiest in the case of very small scale parameter and moreover, any desired level of accuracy may be attained with a small amount of additional computing effort.