THURSDAY, April 7, 2011

STOCHASTIC ACTIVITY MONTH

LECTURE DAY

SUMMARY

This is the official opening the first Stochastic Activity Month (SAM) of Eurandom and STAR. The first SAM is devoted to Stochastic Modelling and Analysis of Networks. Examples of networks are computer networks like the internet, communication networks like wireless, adhoc and sensor networks, and biological and social networks.

For organizational reasons, we kindly ask all participants to register online. This will help us organize a perfect Lecture Day! Deadline for registration is April 4.
Please follow the link:

REGISTRATION
(You will be redirected to the TU/e website for the registration form)

SPEAKERS

PROGRAMME

ABSTRACTS

Sergey Foss (Heriot-Watt University)

Poisson Hail on a Hot Ground

We consider a queue where the server is the Euclidean space, and the customers are random closed sets (RACS) of the Euclidean space.
These RACS arrive according to a Poisson rain and each of them has a random service time (in the case of hail falling on the Euclidean
plane, this is the height of the hailstone, whereas the RACS is its footprint). The Euclidean space serves customers at speed 1. The service
discipline is a hard exclusion rule: no two intersecting RACS can be served simultaneously and service is in the First In First Out order: only the hailstones in contact with the ground melt at speed 1, whereas the other ones are queued; a tagged RACS waits until all RACS arrived before it and intersecting it have fully melted before starting its own melting. We give the evolution equations for this queue. We prove that it is stable for a sufficiently small arrival intensity, provided the typical diameter of the RACS and the typical service time have finite exponential moments. We also discuss the percolation properties of the stationary regime of the RACS in the queue.
This is a joint work with Francois Baccelli (INRIA and ENS, Paris)

PRESENTATION

Jesse Goodman

Invasion percolation on networks and trees

Invasion percolation is an exploration process on a graph with edge weights that grows a cluster by adding the boundary edge of minimal weight at each time step. We will outline what is known about this process in the context of trees and tree-like graphs, such as the complete graph, including connections to (standard) percolation, queueing theory, first passage percolation, and the minimal spanning tree.

PRESENTATION

Remco van der Hofstad

Critical behavior in inhomogeneous random graphs

Empirical findings have shown that many real-world networks share fascinating features. Indeed, many real-world networks are small worlds, in the sense that typical distances are much smaller than the size of the network. Further, many real-world networks are scale-free 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 some of the empirical findings of real-world networks, and describe a particular class of random graphs, in which edges are present independently but with unequal edge occupation probabilities that are moderated by appropriate vertex weights. For such models, it is known precisely when there is a giant component, meaning that a positive proportion of the vertices is connected to one another. We discuss what happens at and close to criticality, a problem having strong connections to statistical mechanics. We identify the scaling limit of the connected components ordered by their size. 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 Erdoes-Renyi random graph. When the third moment is infinite, the largest clusters have size to n^{\alpha} for some \alpha\in (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.
[This is joint work with Shankar Bhamidi and Johan van Leeuwaarden.]

Gerard Hooghiemstra

First passage percolation on (random) graphs

Consider a (connected) random graph G with n vertices. Assign to each of the edges an i.i.d. weight. Given two vertices A and B, taken uniformly at random from the n vertices, we de ne the hopcount H_n, and the minimal weight W_n, respectively, as the number of edges and the weight of the path between A and B with minimal total path weight. Our interest is to prove limit theorems for H_n and W_n, and in particular, to investigate the universality of a central limit theorem for H_n. I will try to summarize results in case the base graph G is the complete graph, the Erdös-Rényi graph and the conguration model. The weights are i.i.d. copies of an exponential random variable E, or a power of an exponential random variable.
(joint work with Shankar Bhamidi[UNC] and Remco van der Hofstad[TU/e])

PRESENTATION

Peter van de Ven

Throughput, fairness and stability of random-access networks

Random-access algorithms such as the Carrier-Sense Multiple-Access (CSMA) protocol provide a popular mechanism for distributed medium access control in large-scale wireless networks. Random-access networks may exhibit severe unfairness in throughput, in the sense that some nodes receive consistently higher throughput than others. We study the unfairness in saturated networks, and adapt the random-access CSMA protocol to remove the unfairness completely.
These models primarily pertain to a saturated scenario where nodes always have packets to transmit. In reality however, the buffers may occasionally be empty as packets are randomly generated and transmitted over time. The resulting interplay between the activity states and the buffer contents gives rise to quite complicated queueing dynamics, and even establishing the stability criteria is usually a serious challenge. We explicitly identify the stability conditions in a few relevant scenarios, and illustrate the difficulties arising in other cases.

PRESENTATION

Uri Yechiali

The Totally Asymmetric Inclusion Process (TASIP) or Tandem Network Queues with Batch Service

Inspired by the biological process of gene translation and its modeling as a flow of particles through a tandem array of limited-capacity ‘servers’ - known in biophysics as the Totally Asymmetric Exclusion Process (TASEP), we devise and analyze a new model: the Totally Asymmetric Inclusion Process (TASIP). The TASIP is a system of tandem Markovian queues with batch service. That is, when service is completed at queue k all particles present at that queue move simultaneously to queue k+1. Equations for the time-dependent Probability Generating Function (PGF) of the system-state (occupancy) vector at arbitrary time instants, as well as at ‘event epochs’ (arrival or service completion), are derived. We show that, at steady state, the two PGFs coincide – implying a PASTA-type phenomenon. We explicitly compute the mean of the system-state vector at steady state, and establish a Little-type law. Furthermore, we explicitly compute the PGF of the TASIP’s total load in steady state, and obtain a stochastic decomposition result for the total load. Finally, we show that TASIP models with identical service rates are, under various perspectives, optimal.
Joint work with Shlomi Reuveni, Iddo Eliazar

Last updated 18-07-11,
by PK