Presentation Details 

Blanchet, Jose 
Importance Sampling for Heavytailed Systems 
View Abstract
Hide Abstract

A standard technique for designing provably efficient (bounded coefficient of variation) statedependent importance sampling estimators for large deviations problems with heavy tails proceeds as follows: a) propose a good parametric family of importance sampling distributions (good in the sense of at least qualitatively approximating the conditional distribution of the underlying process given the event of interest); b) construct a parametric family of proposed Lyapunov functions to control the second moment of the underlying estimator generated by the family chosen in a), typically this step involves fluid heuristics, which are common in the setting of heavytailed large deviations; c) rigorously verify the Lyapunov criterion by appropriately selecting the parameters in both the family introduced in a) and the candidate function proposed in b). Appropriate parametric families (those for which one can rigorously verify strong efficiency) have so far been derived for regularly varying distributions only. Also, because of the heavytailed assumptions the expected termination time of the algorithms sometimes is infinite. In this talk, we develop parametric families that ensure strong efficiency beyond regular variation. In addition, we show how our techniques can be used to control the termination time of the algorithms without sacrificing efficiency. 
Blaszczyszyn, Bartek 
Stochastic geometry and wireless networks 
View Abstract
Hide Abstract

The aim of this tutorial is to show how stochastic geometry can be used
in a more or less systematic way to analyze some key phenomena that
arise in the context of wireless adhoc networks, namely medium access
and routing. We limit ourselves to simple (yet not simplistic) model of Poisson
mobile adhoc network (MANET) with slotted Aloha and concentrate on
the socalled outage scenario, where a successful transmission
requires a signaltoInterferenceandNoise (SINR) larger than some
threshold. We also assume Rayleigh fading. Starting from a simple
explicit expression for the successful transmission probability we
will show first how various network performance metrics related to the
throughput can be evaluated in the scenario where all the receivers
are located within some fixed distance to the receiver. Then we make a
first step towards a joint analysis of MAC and routing considering a
few more complex scenarios for receiver location, all motivated by the
fact that real routing mechanisms typically select receivers in the
vicinity of the respective emitters.
The analysis of these more adequate models reveals interesting
phenomena related to the local delay in MANETs, namely the number of
times slots required for nodes to transmit a packet to their
prescribed nexthop receivers.
We will show that in most cases, each node has a finitemean geometric
random delay and thus a positive next hop throughput, however, the
spatial (or large population) averaging of these individual finite
meandelays leads to infinite values in several practical cases. In
some cases it exhibits a phase transition, where the spatial average
is finite when certain model parameters are below a threshold and
infinite above.
Finally, we consider a fully crosslayer MAC/routing model, where
there is no predefined route and where the routing scheme tries to
take advantage of the variability of MAC and fading to decide on the
next relay for each packet at each time slot.
An important negative consequence of the previous observation on local
delays is that the mean endtoend delay of a packet delivery in
Poisson MANET scales superlinearly with the distance between source
and destination, or, in other words, the asymptotic velocity of a
typical packet is null, even if this packet is considered as a
priority packet and experiences no queuing in the nodes.
The main positive result, formulated and proved using the framework of
the first passage percolation on a SINR spacetime graph, states that
when adding a periodic node infrastructure of arbitrarily small
intensity to the Poisson MANET makes the endtoend delay scale
linearly with the delivery distance.
The tutorial is based on the book "Stochastic Geometry and Wireless
Networks, Volume II – Applications" by F. Baccelli and
B. Blaszczyszyn, Foundations and Trends in Networking, NoW Publishers,
2009. It is also available at http://hal.inria.fr/inria00403040 
Borst, Sem 
Wireless RandomAccess Networks: Fairness, Performance and Stability 
View Abstract
Hide Abstract

Randomaccess algorithms such as the CarrierSense MultipleAccess (CSMA) protocol provide a popular mechanism for distributed medium access control in emerging largescale wireless networks. In the CSMA protocol, each node attempts to access the medium after a certain backoff time, but nodes that sense activity of interfering nodes freeze their backoff timer until the medium is sensed idle. Under suitable assumptions, the joint activity state of the various
nodes may be modelled as a reversible Markov process with a convenient productform stationary distribution. These models yield relatively simple estimates for the longterm throughputs and turn out to be remarkably accurate.
The abovementioned models tend to assume exponential backoff periods and transmission durations, and consider a scenario where buffers are saturated, and nodes always have packets pending for transmission. In reality, backoff periods and transmission times are nonexponential, while the buffers may occasionally be empty as packets are randomly generated and transmitted over time, and nodes may refrain from competition for the medium during these periods. Motivated by these observations, we examine two extensions:
(i) general distributions of transmission times and backoff periods;
(ii) queueing dynamics in scenarios with packet arrivals.
We show that the the stationary distribution of the joint activity state is not only insensitive with respect to the distribution of the transmission times, but also that of the backoff periods, regardless of whether backoffs are frozen or not during activity of neighbouring nodes. In addition, we explicitly identify the stability conditions in a few relevant scenarios, and illustrate the difficulty arising in other cases.
Also, the stationary distribution may not reflect the performance over shorter time intervals, and in particular, longterm fairness may hide severe starvation effects over shorter time periods due to metastability. We will discuss how the shortterm throughput performance is affected by the size and structure of the network topology.
Note: based on joint work with Johan van Leeuwaarden (TU/e), Alexandre Proutiere, (Microsoft), Patrick Thiran (EPFL) and Peter van de Ven (TU/e) 
Busic, Ana 
Stability of the bipartite matching model 
View Abstract
Hide Abstract

We consider the bipartite matching model of customers and servers introduced by Caldentey, Kaplan, and Weiss (Adv. Appl. Probab., 2009). Customers and servers play symmetrical roles. There is a finite set C resp. S, of customer, resp. server, classes. Time is discrete and at each time step, one customer and one server arrive in the system according to a joint probability measure on CxS, independently of the past. Also, at each time step, pairs of matched customer and server, if they exist, depart from the system. Authorized matchings are given by a fixed bipartite graph. A matching policy is chosen, which decides how to match when there are several possibilities. Customers/servers that cannot be matched are stored in a buffer. The evolution of the model can be described by a discrete time Markov chain. We study its stability under various admissible matching policies including: ML (Match the Longest), MS (Match the Shortest), FIFO (match the oldest), priorities. There exist natural necessary conditions for stability (independent of the matching policy) defining the maximal possible stability region. For some bipartite graphs, we prove that the stability region is indeed maximal for any admissible matching policy. For the ML policy, we prove that the stability region is maximal for any bipartite graph. For the MS and priority policies, we exhibit a bipartite graph with a nonmaximal stability region. This is a joint work with Varun Gupta and Jean Mairesse. 
Dhandapani, Yogeshwaran 
Percolation and directionally convex ordering of point processes. 
View Abstract
Hide Abstract

In this talk, we explain the relation between directionally convex ordering of point processes and percolation. Directionally convex ordering has been used to compare point processes with same mean intensities. We will start with a primer on directionally convex ordering of point processes and examples of point processes that are directionally convex ordered. We link directionally convex ordering to percolation as well as clustering by showing that they impact negatively the capacity functionals of their corresponding Boolean models. This is used to show ordering of some new critical radii which act as upper and lower bounds to the usual critical radius for percolation of a point process. The upper bound increases with dcx order while the lower bound decreases.
In the second part, we exploit the fact that many probabilities of additive shotnoise fields of point processes can be bounded by their Laplace transforms. This for sparse point processes (i.e, lesser than Poisson point process in dcx order) can be bounded by the corresponding Laplace transform of Poissondriven shotnoise fields. For a nice class of functionals, one can compute the latter explicitly to ascertain nontriviality of phase transition in various percolation models. We carry out such a program for providing uniform upper and lower bounds (uniform over all sparse point processes) for the critical radius for $k$percolation and percolation in SINR (SignaltoInterferenceNoiseRatio) graphs. 
Dieker, Ton 
Capacity allocation in feedforward queueing networks 
View Abstract
Hide Abstract

Allocation of service capacity ('staffing') at stations in queueing networks is both of fundamental and practical interest. Unfortunately, the problem is mathematically intractable in general and one therefore typically resorts to approximations or computer simulation. This talk describes a joint work with M. Squillante and S. Ghosh (IBM Research) on an algorithm that serves as an approximation for the 'best' capacity allocation rule for feedforward networks. The algorithm can be interpreted as a fixedpoint iteration algorithm, and we are interested in uniqueness of a fixed point and in convergence properties. 
Glynn, Peter 
Lyapunov functions and the analysis of queues 
View Abstract
Hide Abstract

Lyapunov functions are a key tool in the analysis of systems described as Markov processes, and are now widely applied as a means of establishing stability of queueing systems. In this talk, we provide an overview of this methodology and discuss how Lyapunov ideas also arise naturally when bounding equilibrium moments, nonequilibrium expectations, studying smoothness of expectations as function of model parameters, and bounding the variance of importance sampling estimators. 
Goldberg, David 
Performance Bounds for Large Scale Queueing Systems 
View Abstract
Hide Abstract

In this talk, we resolve several open questions related to a certain heavy
traffic scaling regime (HalfinWhitt) for parallel server
queues, which has recently been used in the modeling of call centers. In
particular, we derive the asymptotics of the steadystate queue length for a
very general class of service distributions. We also bound the large
deviations behavior of the limiting steadystate queue length, and prove that
the associated critical exponent takes a particularly simple form in certain
cases. For certain initial conditions, we extend our results to the transient
regime. Our main proof technique involves bounding the multiserver queue
between two simpler systems. These systems exhibit an interesting duality, and
yield bounds of a very general nature, which may be useful in answering a range
of questions related to the modeling and optimization of queues. 
Ivanovs, Jevgenijs 
Markovmodulated Brownian motion with two reflecting barriers 
View Abstract
Hide Abstract

We consider a Markovmodulated Brownian motion reflected to stay
in a strip [0,B]. The stationary distribution of this process is
known to have a simple form under some assumptions. We provide a
short probabilistic argument leading to this result and explaining
its simplicity. This argument allows for generalizations
including the distribution of the reflected process at an
independent exponential time. This talk is based on the first part of arXiv:1003.4107 
Kurtz, Tom 
Counting processes, stochastic equations, and asymptotics for stochastic models 
View Abstract
Hide Abstract

Many stochastic models can be represented as solutions of stochastic equations for which Poisson processes or Poisson random measures are the primary inputs. A variety of examples will be given illustrating these equations and how they can be used to study limit theorems for stochastic models. 
Litvak, Nelly 
A Scaling Analysis of a Cat and Mouse Markov Chain 
View Abstract
Hide Abstract

Motivated by an original online pageranking algorithm, starting from an arbitrary Markov
chain on a discrete state space S, a twodimensional Markov chain on the
product space S X S, the cat and mouse Markov chain, is constructed. The first
coordinate of this Markov chain behaves like the original Markov chain and the second
component changes only when both coordinates are equal. The asymptotic properties of this
Markov chain are investigated. A representation of its invariant measure is in particular
obtained. When the state space is infinite it is shown that this Markov chain is in fact
null recurrent if the initial Markov chain is positive recurrent and reversible.
In this context, the scaling properties of the location of the second component, the
mouse, are investigated in various situations: simple random walks in Z and Z^2,
reflected simple random walk in N and also in a continuous time setting. For several
of these processes, a time scaling with rapid growth gives an interesting asymptotic
behavior related to limit results for occupation times and rare events of Markov
processes. 
Momcilovic, Petar 
Linear loss networks 
View Abstract
Hide Abstract

We investigate properties of throughput and cost in linear loss
networks. The maximum throughput of the network with exponential service
times is derived and the arrival process that maximizes throughput, given a
fixed arrival rate, is established. For general service times, an
asymptotically critical loading regime is identified such that the
probability of an arbitrary customer being lost is strictly within (0, 1),
as the network size increases. This regime delivers throughput comparable to
the maximum at a relatively low network cost. We establish the asymptotic
throughput and network cost under this critical loading. Moreover, we
characterize the departure process from such a network. This process
(appropriately scaled) is the (asymptotic) fixed point of the network, i.e.,
the arrival and departure processes have the same statistical description.
Joint work with Mark Squillante and Yoojin Choi. 
Montanari, Andrea 
Message passing algorithms, random convex functions, and the risk of the LASSO 
View Abstract
Hide Abstract

We consider the problem of learning a vector x0
from noisy linear observation. In many contexts
(ranging from model selection to image processing) it is desirable
to construct a sparse estimator. In this case, a popular
approach consists in solving an l_1penalized least squares problem
known as the LASSO or Bassis Pursuit DeNoising (BPDN).
For sequences of matrices of increasing dimensions, with
independent gaussian entries, we prove that the normalized
risk of the LASSO converges to a limit, and we obtain
an explicit expression for
this limit. The proof is based on the analysis of an approximate message passing
(AMP) algorithm, 
Proutiere, Alexandre 
Load balancing via Random Local Search in closed and open systems 
View Abstract
Hide Abstract

We analyze the performance of random load resampling and migration strategies in parallel server systems. Clients initially attach to an arbitrary server, but may switch servers independently at random instants of time in an attempt to improve their service rate.
We first analyze the natural Random Local Search (RLS) strategy. Under this strategy, after sampling a new server randomly, clients only switch to it if their service rate is improved. In closed systems, where the client population is fixed, we derive tight estimates of the time it takes under RLS strategy to balance the load across servers. We then study open systems where clients arrive according to a random process and leave the system upon service completion. In this scenario, we analyze how client migrations within the system interact with the system dynamics induced by client arrivals and departures. We compare the loadaware RLS strategy to a loadoblivious strategy in which clients just randomly switch server without accounting for the server loads. Surprisingly, we show that both loadoblivious and loadaware strategies stabilize the system whenever this is at all possible. We further demonstrate, using largesystem asymptotics, that the average client sojourn time under the loadoblivious strategy is not considerably reduced when clients apply smarter loadaware strategies. 
Robert, Philippe 
Probabilistics methods in the analysis of stochastic networks 
View Abstract
Hide Abstract

To follow 
Saberi, Amin 
Game Dynamics, Equilibrium Selection and Network Structure 
View Abstract
Hide Abstract

Coordination games describe social or economic interactions in
which the adoption of a common strategy has higher payoff. They are
classically used to model the spread of conventions, behaviors,
and technologies in societies.
Since the pioneering work of Ellison (1993), specific network
structures have been shown to have dramatic influence on the
convergence of such dynamics. In this talk, I will try to make
these results more precise and use the intuition for designing
effective algorithms. 
Shneer, Seva 
Comparing throughputs and fairness in slotted and nonslotted CSMA 
View Abstract
Hide Abstract

We consider a system consisting of n radios on a line. Each radio acts as a transmitter and a receiver but can not transmit and receive simultaneously. The wellknown CSMA protocol is often used to govern the behaviour of the radios in such a system, and the performance of the system in this case is well understood. We consider a discretetime analogue of the CSMA protocol and in the case of a completely saturated system find exact formulas for the total throughput of the system governed by this algorithm and for individual throughputs of all transmitters. We then compare these throughputs with the throughputs achieved by the classical CSMA protocol. The fairness of the two protocols is also compared. Finally, we discuss bounds for the throughput of a system where the first radio (source) is saturated and messages are relayed by the intermediate radios to the last one (destination). The results are also generalised to the case when the channel used by the radios is such that 2 of them cannot send messages simultaneously if the distance between them is not larger than k, where k is a positive integer.
This is a joint work with Peter van de Ven (EURANDOM and Eindhoven University of Technology) 
Simatos, Florian 
Interacting branching processes and linear filesharing networks 
View Abstract
Hide Abstract

Filesharing networks are distributed systems used to disseminate files among nodes of a communication network. The general simple principle of these systems is that once a node has retrieved a file, it may become a server for this file. In this paper, the capacity of these networks is analyzed with a stochastic model when there is a constant flow of incoming requests for a given file. It is shown that the problem can be solved by analyzing the asymptotic behaviour of a class of interacting branching processes. Several results of independent interest concerning these branching processes are derived and then used to study the filesharing systems.
(Joint work with L. Leskelä and P. Robert) 
Subramanian, Vijay 
Large deviations of maxweight scheduling policies on convex rate regions 
View Abstract
Hide Abstract

We consider a single server discretetime system with K users where the server picks operating points from a compact, convex and coordinate convex set in $Re_+^K$. For this system we analyse the performance of a stablising policy that at any given time picks operating points from the allowed rate region that maximise a weighted sum of rate, where the weights depend upon the workloads of the users. Assuming a large deviations principle (LDP) for the arrival processes in the Skorohod space of functions that are rightcontinuous with lefthand limits we establish an LDP for the workload process using a generalised version of the contraction principle to derive the corresponding rate function. With the LDP result available we then analyse the tail probabilities of the workloads under different buffering scenarios. 
Tassiulas, Leandros 
Stochastic models and algorithms for cooperative information delivery 
View Abstract
Hide Abstract

Recent advances in information and communication theory suggest novel architectures where endtoend information delivery is facilitated through cooperation at various stages during the information transport process. We consider a stochastic dynamic model of information transport in an architecture where various information streams are mixed in an intermediate relay node before delivery. The objective is to increase the efficiency of the system through judicious exploitation of transmission overhearing, inherent in radio broadcast. Other user overheard information is used as a key to extract own information in future transmissions. Algorithms for selecting mixing combinations to increase transport efficiency are considered. They rely on complete information about the state of overheard information. When state information is not readily available but is gradually revealed through feedback, the mixing algorithm should account both for efficient state probing as well as for effective information recovery. System capacity characterization and efficient algorithms are obtained for the limited state information as well. 
van der Hofstad, Remco 
Processes on random graphs: routing and attack vulnerability 
View Abstract
Hide Abstract

Empirical findings have shown that many realworld networks share
fascinating features. Indeed, many realworld networks are small worlds, in
the sense that typical distances are much smaller than the size of the
network. Further, many realworld networks are scalefree in the sense
that there is a high variability in the number of connections of the elements of
the networks. Therefore, such networks are highly inhomogeneous.
Spurred by these empirical findings, models have been proposed
for such networks. In this talk, we shall discuss empirical findings
of realworld networks, and describe some of the models proposed for them.
In the realworld, we are not only interested in the topology of networks,
but also in processes living on them. Think of routing on the Internet,
the spread of information and disease on social networks, and searching on
the WorldWide Web. In this talk, we discuss two of such processes
in detail.
The first example is firstpassage percolation on random graphs,
which is a simple model for shortestweight routing on complex networks.
We discuss how random edge weight change the structure of shortestweight
paths, and derive precise limiting results for the weight and
number of edges in the shortestweight path between two uniform
vertices. The results show that adding i.i.d. exponential weights
on the edges has a marked effect on the structure of shortestweight paths.
We close this part by discussing various open problems and conjectures.
The second example is percolation on random graph, which is a simple
model for the attack vulnerability of networks. We discuss the connectivity
behavior at and close to the critical value.
Our results show that, for inhomogeneous random graphs with
highly variable vertex degrees, the critical behavior admits
a transition when the third moment of the degrees turns from
finite to infinite. When the third moment is finite,
the largest clusters in a graph of n vertices have size n^{2/3} and
the scaling limit equals that on the ErdoesRenyi random graph.
When the third moment is infinite, the largest clusters have size
to n^{alpha} for some alphain (1/2,2/3), and the scaling
limit is rather different. Similar phase transitions have been shown
to occur for typical distances in such random graphs when
the variance of the degrees turns from finite to infinite.
We finally discuss some of the ingredients used in the proofs, namely
the treelike nature of the random graphs under consideration and
the use of (continuous and discretetime) branching processes.
This is joint work with:
Gerard Hooghiemstra, Shankar Bhamidi, Johan van Leeuwaarden, Piet Van Mieghem, Henri van den Esker
and Dmitri Znamenski. 
Wainwright, Martin 
Graphical models and messagepassing algorithms: Some introductory lectures 
View Abstract
Hide Abstract

ABSTRACT: Graphical models arise from a marriage between graph theory
and probability theory, and have put to fruitful use in a variety of
disciplines, among them statistical physics, image processing,
communication theory, bioinformatics and networking. Graphical models
naturally give rise to local ``messagepassing'' algorithms for
performing various types of distributed computation, which have been
highly influential in these disciplines. In this series of tutorial
lectures, we provide an introduction to this area. We begin with
basics of the field (including Markov properties, HammersleyClifford,
messagepassing on trees, junction tree framework) before moving onto
a selection of more advanced topics (e.g., messagepassing on graphs
with cycles, convergence issues, variational methods, and
linearprogramming relaxations).
A short book on graphical models:
http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJor08_FTML.pdf 
Walton, Neil 
Utility Optimization in Congested Queueing Networks 
View Abstract
Hide Abstract

We consider a multiclass single server queueing network as a
model of a packet switching network. The rates packets are sent into this
network are controlled by queues which act as congestion windows. By
considering a sequence of such congestion windows we allow the network to
become congested. We show the stationary throughput of routes on this
sequence of networks converges to an allocation that maximizes aggregate
utility subject to the network's capacity constraints. To perform this
analysis we require that our utility functions satisfy an exponential
concavity condition. This family of utilities includes weighted
$alpha$fair utilities for $alpha >1$. 
Wischik, Damon 
Queueing theory for switched networks 
View Abstract
Hide Abstract

A switched network consists of a collection of queues, with constraints on which queues may be served simultaneously, plus a policy for choosing which set of queues to serve at a given instant. Switched networks can be used to model diverse communications systems such as Internet routers, bandwidth sharing by TCP, and wireless networks. I will describe these modelling applications. I will also describe several approaches to performance analysis: stability analysis via Lyapunov functions, heavy traffic analysis, overload analysis, and underload analysis using large deviations theory. 
Zhang, Jiheng 
Fluid Models of Manyserver Queues with Abandonment 
View Abstract
Hide Abstract

We study manyserver queues with abandonment in which customers have general service and patience time distributions. The dynamics of the system are modeled using measurevalued processes, to keep track of the residual service and patience times of each customer. Deterministic fluid models are established to provide firstorder approximation for this model. The fluid model solution, which is proved to uniquely exists, serves as the fluid limit of the manyserver queue, as the number of servers becomes large. Based on the fluid model solution, firstorder approximations for various performance quantities are proposed. 