Search

This paper considers the minimization of a sum of smooth and strongly convex functions dispatched over the nodes of a communication network. Previous works on the subject either focus on synchronous algorithms, which can be heavily slowed down by a few slow nodes (the straggler problem), or consider a model of asynchronous operation (Boyd et al., 2006) in which adjacent nodes communicate at the instants of Poisson point processes. We have two main contributions. 1) We propose CACDM (a Continuously Accelerated Coordinate Dual Method), and for the Poisson model of asynchronous operation, we prove CACDM to converge to optimality at an accelerated convergence rate in the sense of Nesterov et Stich, 2017. In contrast, previously proposed asynchronous algorithms have not been proven to achieve such accelerated rate. While CACDM is based on discrete updates, the proof of its convergence crucially depends on a continuous time analysis. 2) We introduce a new communication scheme based on Loss-Networks, that is programmable in a fully asynchronous and decentralized way, unlike the Poisson model of asynchronous operation that does not capture essential aspects of asynchrony such as non-instantaneous communications and computations. Under this Loss-Network model of asynchrony, we establish for CDM (a Coordinate Dual Method) a rate of convergence in terms of the eigengap of the Laplacian of the graph weighted by local effective delays. We believe this eigengap to be a fundamental bottleneck for convergence rates of asynchronous optimization. Finally, we verify empirically that CACDM enjoys an accelerated convergence rate in the Loss-Network model of asynchrony.

We study one-dimensional resource sharing systems which can be seen as interacting particle systems taking values in ({0,1,…,C} M ) Z . We first get, by coupling techniques, an estimate of their invariant measures. Then, for processes having a reversible measure, we show the uniqueness of the invariant measure and conclude that they are ergodic. As a consequence, we prove that every loss network on Z with calls of bounded length is ergodic.

Loss and closed queueing network models have long been of interest to telephone and computer engineers and becoming increasingly important as models of data transmission networks. This paper describes a uniform approach that has been developed during the last decade for asymptotic analysis of large capacity networks with product form of the stationary probability distribution. Such a distribution has an explicit form up to the normalization constant, or the partition function. The approach is based on representing the partition function as a contour integral in complex space and evaluating the integral using the saddle point method and theory of residues. This paper provides an introduction to the area and a review of recent work.

Esta tesis consiste de dos partes, en cada una estudiamos la estabilidad bajo pequeñasperturbaciones de ciertos modelos probabilísticos en diferentes contextos. En laprimera parte, estudiamos pequeñas perturbaciones aleatorias de un sistema dinámicodeterminístico y mostramos que las mismas son inestables, en el sentido de que los sistemasperturbados tienen un comportamiento cualitativo diferente al del sistema original. Más precisamente, dado p > 1 estudiamos soluciones de la ecuación en derivadas parcialesestocástica ∂tU = ∂xx^2 U + U|U|^p−1 + εW (ver formula en el original)con condiciones de frontera de Dirichlet homogéneas y mostramos que para ε > 0 pequeñoséstas presentan una forma particular de inestabilidad conocida como metaestabilidad. Enla segunda parte nos situamos dentro del contexto de la mecánica estadística, dondeestudiamos la estabilidad de medidas de equilibrio en volumen infinito bajo ciertas perturbacionesdeterminísticas en los parámetros del modelo. Más precisamente, mostramosque las medidas de Gibbs para una cierta clase general de sistemas son continuas conrespecto a cambios en la interacción y/o en la densidad de partículas y, por lo tanto,estables bajo pequeñas perturbaciones de las mismas. También estudiamos bajo quécondiciones ciertas configuraciones típicas de estos sistemas permanecen estables en ellímite de temperatura cero T → 0. La herramienta principal que utilizamos para nuestroestudio es la realización de estas medidas de equilibrio como distribuciones invariantes delas dinámicas introducidas en [16]. Referimos al comienzo de cada una de las partes parauna introducción de mayor profundidad sobre cada uno de los temas. This thesis consists of two separate parts: in each we study the stability under smallperturbations of certain probability models in different contexts. In the first, we studysmall random perturbations of a deterministic dynamical system and show that these areunstable, in the sense that the perturbed systems have a different qualitative behaviorthan that of the original system. More precisely, given p > 1 we study solutions to thestochastic partial differential equation ∂tU = ∂xx^2 U + U|U|^p−1 + εW˙ (see equation in original PDF)with homogeneous Dirichlet boundary conditions and show that for small ε > 0 thesepresent a rather particular form of unstability known as metastability. In the second partwe situate ourselves in the context of statistical mechanics, where we study the stabilityof equilibrium infinite-volume measures under small deterministic perturbations in theparameters of the model. More precisely, we show that Gibbs measures for a generalclass of systems are continuous with respect to changes in the interaction and/or densityof particles and, hence, stable under small perturbations of them. We also study underwhich conditions do certain typical configurations of these systems remain stable in thezero-temperature limit T → 0. The main tool we use for our study is the realization ofthese equilibrium measures as invariant distributions of the dynamics introduced in [16]. We refer to the beginning of each part for a deeper introduction on each of the subjects. Fil: Saglietti, Santiago. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

Management of a bufferless resource is considered under non-homogeneous demand consisting of one-unit and two-unit requests. Two-unit requests can be served only by a given partition of the resource. Three simple admission policies are evaluated with regard to revenue generation. One policy involves no admission control and two policies involve trunk reservation. A limiting regime in which demand and capacity increase in proportion is considered. It is shown that each policy is asymptotically optimal for a certain range of parameters. Limiting dynamical behavior is obtained via a theory developed by Hunt and Kurtz. The results also point out the remarkable effect of partition constraints.

The Erlang formula is known to be insensitive to the holding time distribution beyond the mean. While calls are generally assumed to arrive as a Poisson process, we prove that it is in fact sufficient that users generate sessions according to a Poisson process, each session being composed of a random, finite number of calls and idle periods. A key role is played by the retrial behavior in case of call blocking. We illustrate the results by a number of examples.

We consider a symmetric tree loss network that supports single-link (unicast) and multi-link (multicast) calls to nearest neighbors and has capacity $C$ on each link. The network operates a control so that the number of multicast calls centered at any node cannot exceed $C_V$ and the number of unicast calls at a link cannot exceed $C_E$, where $C_E$, $C_V\leq C$. We show that uniqueness of Gibbs measures on the infinite tree is equivalent to the convergence of certain recursions of a related map. For the case $C_V=1$ and $C_E=C$, we precisely characterize the phase transition surface and show that the phase transition is always nonmonotone in the arrival rate of the multicast calls. This model is an example of a system with hard constraints that has weights attached to both the edges and nodes of the network and can be viewed as a generalization of the hard core model that arises in statistical mechanics and combinatorics. Some of the results obtained also hold for more general models than just the loss network. The proofs rely on a combination of techniques from probability theory and dynamical systems., Comment: Published at http://dx.doi.org/10.1214/105051606000000303 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We introduce penalty-function-based admission control policies to approximately maximize the expected reward rate in a loss network. These control policies are easy to implement and perform well both in the transient period as well as in steady state. A major advantage of the penalty approach is that it avoids solving the associated dynamic program. However, a disadvantage of this approach is that it requires the capacity requested by individual requests to be sufficiently small compared to total available capacity. We first solve a related deterministic linear program (LP) and then translate an optimal solution of the LP into an admission control policy for the loss network via an exponential penalty function. We show that the penalty policy is a target-tracking policy--it performs well because the optimal solution of the LP is a good target. We demonstrate that the penalty approach can be extended to track arbitrarily defined target sets. Results from preliminary simulation studies are included., Comment: Published at http://dx.doi.org/10.1214/105051604000000936 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Two channel assignment policies are considered for a Kelly type loss network with an additional channel continuity requirement. It is assumed that the channels on any given link have distinct identities, and that a connection should be assigned channels with a common identity on all links of its route. Such constraints arise in circuit switched WDM optical networks and wireless cellular networks. A functional law of large numbers, which was previously developed by Hunt and Kurtz and later refined by Zachary and Ziedins, is adapted to analyze a network with two links and three connection types. Asymptotically exact fluid-type approximations for the network process are obtained and their operating points are characterized. The results lead to asymptotic call blocking rates and point out that in cases of practical interest, random channel assignment has asymptotically the same blocking performance with more sophisticated channel assignment policies.

Loss networks in heavy traffic under Kelly's scaling are analyzed. In the case of a single node and $R$ classes of calls, a degenerate diffusion approximation theorem around the corresponding fluid limit in an $({R-1})$-dimensional hyperplane is proved.

The paper studies routing in loss networks in the framework of a non-cooperati- ve game with selfish users. Two solution concepts are considered: the Nash equilibrium, corresponding to the case of a finite number of agents (such as service providers) that take routing decisions, and the Wardrop equilibrium, in which routing decisions are taken by a very large number of individual users. We show that these equilibria do not fall into the standard frameworks of non-cooperative routing games. As a result, we show that uniqueness of equilibria or even of utilizations at equilibria may fail even in the case of simple topology of parallel links. However, we show that some of the problems disappear in the case in which the bandwidth required by of all connections is the same. For the special case of a parallel link topology, we obtain some surprisingly simple way of solving the equilibrium for both cases of Wardrop as well as Nash equilibrium.

We study the fluid limits of loss networks under Kelly's scaling. In the case of heavy traffic for a single node and J classes of calls, we prove a degenerate diffusion approximation theorem around the corresponding fluid limit. After a careful analysis of some reflected random walks in N, we prove that Hunt and Kurtz's conjecture (1994) for the trunk reservation policy is wrong. We conclude with some remarks on the conjecture in the case of an uncontrolled network.

We present a perfect simulation algorithm for measures that are absolutely continuous with respect to some Poisson process and can be obtained as invariant measures of birth-and-death processes. Examples include area- and perimeter-interacting point processes (with stochastic grains), invariant measures of loss networks, and the Ising contour and random cluster models. The algorithm does not involve couplings of the process with different initial conditions and it is not tied up to monotonicity requirements. Furthermore, it directly provides perfect samples of finite windows of the infinite-volume measure, subjected to time and space ``user-impatience bias''. The algorithm is based on a two-step procedure: (i) a perfect-simulation scheme for a (finite and random) relevant portion of a (space-time) marked Poisson processes (free birth-and-death process, free loss networks), and (ii) a ``cleaning'' algorithm that trims out this process according to the interaction rules of the target process. The first step involves the perfect generation of ``ancestors'' of a given object, that is of predecessors that may have an influence on the birth-rate under the target process. The second step, and hence the whole procedure, is feasible if these ``ancestors'' form a finite set with probability one. We present a sufficiency criteria for this condition, based on the absence of infinite clusters for an associated (backwards) oriented percolation model., Revised version after referee of SPA: 39 pages

We present a probabilistic approach for the study of systems with exclusions, in the regime traditionally studied via cluster-expansion methods. In this paper we focus on its application for the gases of Peierls contours found in the study of the Ising model at low temperatures, but most of the results are general. We realize the equilibrium measure as the invariant measure of a loss-network process whose existence is ensured by a subcriticality condition of a dominant branching process. In this regime, the approach yields, besides existence and uniqueness of the measure, properties such as exponential space convergence and mixing, and a central limit theorem. The loss network converges exponentially fast to the equilibrium measure, without metastable traps. This convergence is faster at low temperatures, where it leads to the proof of an asymptotic Poisson distribution of contours. Our results on the mixing properties of the measure are comparable to those obtained with ``duplicated-variables expansion'', used to treat systems with disorder and coupled map lattices. It works in a larger region of validity than usual cluster-expansion formalisms, and it is not tied to the analyticity of the pressure. In fact, it does not lead to any kind of expansion for the latter, and the properties of the equilibrium measure are obtained without resorting to combinatorial or complex analysis techniques., 42 pages. Revised version after the first referee report

1. Introduction. The generic dynamic resource allocation problem involves a number of locations containing resources. The dynamic aspect of the problem is the arrival of consumers, each of which requires a certain amount of service from the resources, and the control variable of the problem is the allocation policy, which species at which location each consumer is to be served. Oftentimes in applications, locations contain nitely many resources, hence the network can get congested and may eventually overow in the sense that consumers may be lost. The purpose of this work is to provide estimates on the network overow time under certain resource allocation policies. In particular we concentrate on three allocation policies, namely optimal repacking (OR), least load routing (LLR), and Bernoulli splitting (BS). The OR policy continuously repacks the consumers in the network so as to minimize the maximum load over the locations. LLR and BS are nonrepacking policies, under which the assignment decisions are irrevocable. The LLR policy assigns each arriving consumer to an admissible location with the least load, whereas the BS policy assigns each arriving consumer to one of the admissible locations randomly and independently, so as to minimize the maximum mean load over the locations. The policies investigated in this paper have been considered by several authors and in various contexts. In particular, Gibbens, Kelly and Turner (1993) considered the LLR policy for dynamic routing in circuit switched networks. Azar, Broder, and Karlin (1992) compared the LLR and the optimal nonrepacking policies based on a worst case analysis, whereas Alanyali and Hajek (1997) compared the three policies based on certain properties implied by uid limit approximations.