public 01:44:51

Ruth Williams : Control of Stochastic Processing Networks

  -   Probability ( 222 Views )

Stochastic processing networks (SPNs) are a significant generalization of conventional queueing networks that allow for flexible scheduling through dynamic sequencing and alternate routing. SPNs arise naturally in a variety of applications in operations management and their control and analysis present challenging mathematical problems. One approach to these problems, via approximate diffusion control problems, has been outlined by J. M. Harrison. Various aspects of this approach have been developed mathematically, including a reduction in dimension of the diffusion control problem. However, other aspects have been less explored, especially, solution of the diffusion control problem, derivation of policies by interpretating such solutions, and limit theorems that establish optimality of such policies in a suitable asymptotic sense. In this talk, for a concrete class of networks called parallel server systems which arise in service network and computer science applications, we explore previously undeveloped aspects of Harrison's scheme and illustrate the use of the approach in obtaining simple control policies that are nearly optimal. Identification of a graphical structure for the network, an invariance principle and properties of local times of reflecting Brownian motion, will feature in our analysis. The talk will conclude with a summary of the current status and description of open problems associated with the further development of control of stochastic processing networks. This talk will draw on aspects of joint work with M. Bramson, M. Reiman, W. Kang and V. Pesic.

public 01:44:53

Shankar Bhamidi : Flows, first passage percolation and random disorder in networks

  -   Probability ( 220 Views )

Consider a connected network and suppose each edge in the network has a random positive edge weight. Understanding the structure and weight of the shortest path between nodes in the network is one of the most fundamental problems studied in modern probability theory and goes under the name first passage percolation. It arises as a fundamental building block in many interacting particle system models such as the spread of epidemics on networks. To a large extent such problems have been only studied in the context of the n-dimensional lattice. In the modern context these problems take on an additional significance with the minimal weight measuring the cost of sending information while the number of edges on the optimal path (hopcount) representing the actual time for messages to get between vertices in the network. Given general models of random graphs with random edge costs, can one develop techniques to analyze asymptotics of functionals of interest which are robust to the model formulation? The aim of this talk is to describe a heuristic based on continuous time branching processes which gives very easily, a wide array of asymptotic results for random network models in terms of the Malthusian rate of growth and the stable age distribution of associated branching process. These techniques allow us to solve not only first passage percolation problems rigorously but also understand functionals such as the degree distribution of shortest path trees, congestion across edges as well as asymptotics for “betweeness centrality” a concept of crucial interest in social networks, in terms of Cox processes and extreme value distributions. These techniques also allow one to exactly solve models of “weak disorder” in the context of the stochastic mean field model of distance, a model of great interest in probabilistic combinatorial optimization.