# Workshop Programme

## for period 22 - 26 March 2010

### Stochastic Networks

22 - 26 March 2010

Timetable

Monday 22 March | ||||

08:30-09:25 | Registration | |||

09:25-09:30 | Welcome from Ben Mestel (INI Deputy Director) | |||

Chair: Michael Harrison | ||||

09:30-10:30 | Baccelli, F (INRIA Paris - ENS) |
|||

Capacity and error exponents of stationary point processes with additive displacement noise | Sem 1 | |||

We define and analyze the Shannon-Poltyrev capacity of a stationary point process under a stationary and ergodic additive displacement noise. We give a representation of the error probability within this setting in terms of the Palm probability of the underlying point process. In the Poisson case, we use this representation and large deviation techniques for deriving bounds on the associated error exponents. This also leads to bounds on the error exponents of the channel with stationary and ergodic additive noise and with power constraint. Joint work with Venkat Anantharam. |
||||

10:30-11:00 | Coffee | |||

11:00-12:00 | Reiman, M (Alcatel-Lucent Bell Labs) |
|||

Assemble-to-Order Inventory Systems as Newsvendor Networks | Sem 1 | |||

The assemble-to-order system is a classical model in inventory theory, where multiple components are used to produce multiple products. All components are obtained from an uncapacitated supplier after a deterministic lead time, while demand for the products is random. The optimal control for this system (where the goal is to minimize the long run average inventory + backlog cost) is not known except for very special cases. I will describe an approach to solving this problem using a two-stage stochastic linear program, known as the newsvendor network, which provides a lower bound on achievable cost in the inventory system. I will also describe how to translate the solution of this stochastic program into a control policy for the inventory system in some special cases and introduce our conjecture that these policies are asymptotically optimal as the lead time grows. I will finally describe how state-space collapse and related ideas from heavy traffic theory can be applied to these systems, despite the fact that there are no capacitated resources. The talk is based on joint work with Mustafa Dogru and Qiong Wang. |
||||

12:15-13:30 | Lunch at Wolfson Court (open for lunch from 12:15--13:30) | |||

Chair: Jim Dai | ||||

14:00-15:00 | Zwart, AP (CWI) |
|||

Scheduling and large deviations | Sem 1 | |||

We investigate the impact of a scheduling discipline in preventing large response times in a queueing setting. In particular, for a GI/GI/1 queue it is well known that, in a large deviations setting, FIFO is optimal for light-tailed service times, and service disciplines such as PS (Processor Sharing) and SRPT (Shortest Remaining Processing Time) are optimal for heavy-tailed service times. It is also known that PS and SRPT do not perform well for light-tailed service times, while FIFO does not perform well for heavy-tailed service times. In this talk, we review these results, and answer the natural question whether it is possible to construct a single scheduling discipline that is competitive with FIFO for light-tailed service times and competitive with SRPT for heavy tailed service times. We also investigate how more robust scheduling disciplines can be designed by exploiting partial information on the distributions, such as the system load. |
||||

15:00-15:30 | Tea | |||

15:30-16:30 | Srikant, R (Illinois) |
|||

Scheduling in Wireless Networks | Sem 1 | |||

Optimization and stochastic network theory have been used to successfully design architectures for fair resource allocation in wireless networks. In this talk, we will describe recent progress in extending this framework to design decentralized, low-complexity scheduling algorithms. Open problems in the design of scheduling algorithms to handle flow-level dynamics and per-packet deadlines will also be discussed. |
||||

16:30-17:00 | Break | |||

Chair: Sir David Wallace | ||||

17:00-18:00 | Hajek, B (Illinois) |
|||

Rothschild Visiting Professor - Mathematical analysis of peer to peer communication networks | Sem 1 | |||

Distributed protocols for peer to peer file sharing, streaming video, and video on demand have revolutionised the way the majority of information is conveyed over the Internet. The peers are millions of computers, acting as both clients and servers, downloading and uploading information. Information to be shared is broken into chunks, and the chunks are traded among peers in the network. There can be turnover in the set of chunks of information being collected and/or in the set of peers collecting the information. Coding, in which groups of chunks are combined to form new chunks, can enhance the collection process. The systems are distributed and scalable. The theory for understanding peer to peer systems has lagged far behind our ability to mathematically model, predict, and optimize system performance. In this talk I shall discuss stochastic models, mathematical results, and challenges relating to the performance of peer to peer communication in large networks. |
||||

18:00-19:00 | Welcome Wine Reception | |||

19:00-19:30 | Dinner at Wolfson Court |

Tuesday 23 March | ||||

Chair: A Ganesh | ||||

09:30-10:30 | Anantharam, V (UC, Berkeley) |
|||

Persistence of long-range-dependence under data compression | Sem 1 | |||

One of the early motivations for current interest in the stochastic networks community in the study of network models involving long-range-dependent stochastic processes was the observation, based on statistical analysis of data, that variable-bit-rate video traffic over networks appears to exhibit long-range-dependent behavior. Such traffic is typically placed on the network after data compression algorithms are used on an underlying video source. It is natural to ask what role the data compression algorithm plays in the resulting long-range-dependent nature of the traffic. Motivated by this question we study the entropy density of an underlying long-range-dependent process as a stochastic process in its own right, focusing on discrete time models. For classes of processes including renewal processes we prove that long-range-dependence of the underlying process implies long-range-dependence of the entropy density process, with the same Hurst exponent. The underlying background in the data compression of stochastic processes, including the fundamental lemma of Barron relating the entropy density to data compression, and existing results for the short-range-dependent case that have the same flavor as our results, such as those due to Kontoyiannis, will also be discussed in this talk. |
||||

10:30-11:00 | Coffee | |||

11:00-12:00 | Graham, C (École Polytechnique) |
|||

Self-adaptive congestion control for multi-class intermittent transmissions in a network | Sem 1 | |||

This study extends a previous Markovian model for permanent transmissions emitting through a network. Numerous connections (or users, customers, ...) are divided into classes by attributes such as routes, traffic characteristics, quality of service requirements, etc. An inactive connection becomes active when it acquires data to transmit, and becomes inactive again after having completed the transmission. Active connections create congestion in the network, and control it in a delocalized way, by each adjusting its output to the resulting delays and losses it incurs, using an Additive Increase, Multiplicative Decrease (AIMD) algorithm similar to TCP. |
||||

12:15-13:30 | Lunch at Wolfson Court (open for lunch from 12:15--13:30) | |||

Chair: Tom Kurtz | ||||

14:00-15:00 | Glynn, P (Stanford) |
|||

Numerical Methods for Stochastic Networks | Sem 1 | |||

This talk will provide an overview of two numerical methods that are relevant to the computational study of stochastic networks. Specifically, we will discuss a simulation-based algorithm that focuses on rare events in the setting of many-server loss networks. We will also discuss a linear programming approach to computing the equilibrium distribution of a Brownian network model. This work is joint with Jose Blanchet, Henry Lam, Denis Saure, and Assaf Zeevi. |
||||

15:00-15:30 | Tea | |||

15:30-16:30 | Anderson, D (Wisconsin-Madison) |
|||

Simulation methods for stochastically modeled chemical reaction networks | Sem 1 | |||

While exact simulation methods exist for discrete-stochastic models of biochemical reaction networks, they are oftentimes too inefficient for use because the number of computations scales linearly with the number of reaction events; thus, approximate algorithms have been developed. However, stochastically modeled reaction networks often have "natural scales" and it is crucial that these be accounted for when developing and analyzing numerical approximation methods. I will show that conducting such a non-standard error analysis leads to fundamentally different conclusions than previous analyses. Another option for approximating discrete-stochastic models of chemical reaction networks is to use a diffusion approximation. However, even in the regimes where such an approximation is preferable to the discrete numerical approximation methods, it is now necessary to approximate the diffusion process. In the second portion of my talk I will show how the special structure of chemical reaction networks can be utilized to develop an efficient and easy to implement method that is second order accurate in the weak sense for such diffusion processes. |
||||

18:30-19:30 | Dinner at Wolfson Court |

Wednesday 24 March | ||||

Chair: Amber Puha | ||||

09:30-10:30 | Williams, R (UC, San Diego) |
|||

A stochastic model of coupled enzymatic degradation | Sem 1 | |||

Joint work with Natalie Cookson, Jeff Hasty, Will Mather, Octavio Mondragon-Palomino and Lev Tsimring A major challenge for systems biology is to deduce the molecular interactions that underly correlations observed between concentrations of different intracellular molecules. While direct explanations such as coupled transcription/translation or direct protein-protein interactions are often considered, potential indirect sources of coupling have received much less attention. In this talk, I will report on an investigation involving both theory and experiment of how correlations can arise generically from a post-translational coupling mechanism involving the processing of multiple protein species by a common enzyme. |
||||

10:30-11:00 | Coffee | |||

11:00-12:00 | Roch, S (UC, Los Angeles) |
|||

Probabilistic Techniques in Mathematical Phylogenetics | Sem 1 | |||

I will discuss recent results on connections between the reconstruction problem on spin systems and two important problems in evolutionary biology: the inference of ancestral molecular sequences and the reconstruction of large phylogenies. |
||||

12:15-13:30 | Lunch at Wolfson Court (open for lunch from 12:15--13:30) | |||

19:30-22:00 | Conference Dinner at Christ's College |

Thursday 25 March | ||||

Chair: Haya Kaspi | ||||

09:30-10:30 | Bramson, M (Minnesota) |
|||

A Positive Recurrent Reflecting Brownian Motion with Divergent Fluid Path | Sem 1 | |||

Precise conditions are known for positive recurrence of semimartingale reflecting Brownian motion (SRBM) in 2 and 3 dimensions, with the argument in 3 dimensions being more involved than in 2 dimensions. The setting in 4 and more dimensions is more complicated than in 3 dimensions and there are presently no general results. Associated with each SRBM are fluid paths, which are solutions of deterministic equations corresponding to the random equations of the SRBM. A standard result of Dupuis and Williams states that when every fluid path associated with the SRBM is attracted to the origin, the SRBM is positive recurrent. This result was employed by El Kharroubi et al. to give sufficient conditions for positive recurrence in 3 dimensions. In a recent paper with Dai and Harrison, it was shown that the above fluid path behavior is also necessary for positive recurrence of the SRBM. Here, we present a family of examples in 6 dimensions where the SRBM is positive recurrent but for which a linear fluid path diverges to infinity. These examples show, in particular, that the converse of the Dupuis-Williams result does not hold in 6 and more dimensions. They also illustrate the difficulty in formulating conditions for positive recurrence of SRBM in higher dimensions. |
||||

10:30-11:00 | Coffee | |||

11:00-12:00 | Open Problems Session | |||

12:15-13:30 | Lunch at Wolfson Court (open for lunch from 12:15--13:30) | |||

Chair: Sergei Foss | ||||

14:00-15:00 | Lelarge, M (ENS) |
|||

Matchings and rank for random diluted graphs | Sem 1 | |||

We study matchings on a sequence of random graphs that converge locally to trees. Inspired by techniques from random matrix theory, we rigorously prove the validity of the cavity method for the computation of the entropy. At a positive temperature, the cavity equations are interpreted as equations for the local marginals of the Boltzmann Gibbs distribution in the space of matchings on a (possibly) infinite tree. These equations also appear in the computation of the asymptotic rank of the adjacency matrices of the random graphs. We also define a determinantal process on the tree which is the limit at positive temperature of the matchings on the sequence of graphs. (joint work with Charles Bordenave and Justin Salez) |
||||

15:00-15:30 | Tea | |||

15:30-17:00 | Poster Session | |||

18:30-19:30 | Dinner at Wolfson Court |

Friday 26 March | ||||

Chair: Onno Boxma | ||||

09:30-10:30 | Evans, S (UC, Berkeley) |
|||

Go forth and multiply? | Sem 1 | |||

Organisms reproduce in environments that change in both time and space. Even if an individual currently resides in a region that is typically quite favorable, it may be optimal for it to ``not put all its eggs in the one basket'' and disperse some of its offspring to locations that are usually less favorable to cover the possibility that the effect of poor conditions in one place will be fortuitously offset by good conditions in another. I will describe joint work with Peter Ralph and Sebastian Schreiber from Evolution and Ecology at U.C. Davis and Arnab Sen from Statistics at U.C. Berkeley that uses stochastic differential equations to explore the usefulness of such dispersal strategies. |
||||

10:30-11:00 | Coffee | |||

11:00-12:00 | Robert, P (INRIA Paris - Rocquencourt) |
|||

The Evolution of a Spatial Stochastic Network | Sem 1 | |||

The asymptotic behavior of a stochastic network represented by a birth and death processes of particles is analyzed. Births: Particles are created at rate $\l_+$ and their location is independent of the current configuration. Deaths are due to negative particles arriving at rate $\l_-$. The death of a particle occurs when a negative particle arrives in its neighborhood and kills it. Several killing schemes are considered. The arriving locations of positive and negative particles are assumed to have the same distribution. By using a combination of monotonicity properties and invariance relations it is shown that the configurations of particles converge in distribution for several models. The problems of uniqueness of invariant measures and of the existence of accumulation points for the limiting configurations are also investigated. It is shown for several natural models that if $\l_+ |
||||

12:15-13:30 | Lunch at Wolfson Court (open for lunch from 12:15--13:30) | |||

Chair: James Martin | ||||

14:00-15:00 | Ferrari, P (Buenos Aires) |
|||

Slow-to-start traffic models, coalescing Brownian motions and M/M/1 queues | Sem 1 | |||

"Cars" are points in the real line that move to the left and have two possible velocities: 0 or 1. Cars maintain order, so that when a moving car is blocked by a stopped car, it has to stop too. Unblocked cars with zero velocity wait a random time with exponential distribution to adquire velocity one (this is the slow-to-start rule). The initial distribution of cars is a Poisson process of parameter $\l$. There are three regimes: supercritical (\l>1) where cars condensate in a random set of initial positions; critical (\l = 1) when there is condensation but the asymptotic speed of the cars is 1, and subcritical (\l<1) where each car get eventually unblocked. The rescaling of this process in the critical and supercritical regimes is related with coalescing Brownian motions. In the subcritical regime the final relative positions of the cars is given by a Poisson process. In this case the car trajectories can be mapped to the loading process of a M/M/1 queue. Joint work with Leo Rolla, Fredy Caceres and Eugene Pechersky. |
||||

15:00-15:30 | Tea | |||

15:30-16:00 | Kelly, F (Cambridge) |
|||

Closing Perspectives Lecture | Sem 1 | |||

18:30-19:30 | Dinner at Wolfson Court |