European Institute for Statistics, Probability, Stochastic Operations Research
and their Applications

About | Research | Events | People | Reports | Alumni | ContactHome


June 30 - July 2, 2014

Workshop on


Performance and Control of Large-Scale Networks








This is a multi-faceted three-day workshop, without  any established tradition, although the overall format and scope are broadly similar in spirit to various workshops held in recent years, e.g., a workshop on “Mathematical Modeling and Analysis of Computer Networks”  at ENS in Paris in 2007, a workshop on “Mathematical Modeling and Analysis of Wireless Networks” organized at the Fields Institute in Toronto in 2008, and a workshop on “Network Science” in Maynooth in 2011.


While our workshop is shorter and smaller in size, the thematic and scientific agenda is also closely aligned with the trends of several workshops that were held in the framework of the program on “Stochastic Processes in Communication Sciences” at the Isaac Newton Institute in Cambridge organized by Venkat Anantharam (University of California at Berkeley), Francois Baccelli (ENS, INRIA, and University of Texas at Austin), Sergey Foss (Heriot-Watt University and University of Novosibirsk), and Peter Glynn (Stanford University), in particular the recent five-day workshop on “Modern Probabilistic Techniques for Design, Stability,  Large Deviations, and Performance Analysis of Communication, Social, Energy, and Other Stochastic Systems and Networks” , as well as a five-day workshop on “Asymptotics of Large-Scale Interacting Networks” organized at the Banff Conference Center in early 2013.


The common denominator of all the above-mentioned workshops revolves around mathematical modeling and analysis of a diverse range of networks, e.g., in communications and information dissemination, energy supply, social interactions, and logistics and transportation.  These networks have experienced immense growth in terms of size, scope and technological complexity, and commonly exhibit huge stochastic variation due to fluctuating or uncertain user demands, unpredictable mobility patterns and random failures. Because of their huge size, any kind of centralized control tends to be impractical, and hence these networks critically rely on distributed control mechanisms where individual nodes or users make decisions based on local information.  Such local control algorithms may impact the network performance on a macroscopic level in rather subtle and even counter-intuitive ways, especially in the presence of random fluctuations.  This raises questions how local control algorithms should be designed and what local information can be leveraged in order to optimize the global network performance.
These problems are mathematically highly challenging and are at the heart of the envisioned workshop program.  Many of these challenges fall at the crossroads of applied probability (e.g. interacting-particle models and random graphs), statistics (e.g. measurement-based algorithms), and stochastic optimization (e.g. algorithm design), and are among the hottest topics in the international research community, as testified by the above-mentioned workshops.


CONFERENCE DINNER (Restaurant Piet Hein Eek)




Sem Borst TU Eindhoven
Johan van Leeuwaarden TU Eindhoven




Prof. Thomas Bonald Telecom Paris Tech
Prof. Augustin Chaintreau Columbia University
Prof. Claudio De Persis University of Groningen
Prof. Ken Duffy Hamilton Institute
Prof. David Goldberg Georgia Tech
Prof. Douglas Leith Hamilton Institute
Prof. Peter Marbach University of Toronto
Dr. Laurent Massoulie INRIA/Microsoft Research
Prof. Alexandre Proutiere KTH
Prof. Devravat Shah (cancelled) MIT
Prof. Sanjay Shakkottai University of Texas Austin
Prof. Patrick Thiran EPFL
Prof. Piet Van Mieghem Delft University of Technology
Dr. Milan Vojnovic Microsoft Research
Prof. Jiheng Zhang Hong Kong University of Science and Technology



MONDAY June 30

10.00 - 10.30 Registration    
10.30 - 10.40 Opening Remco van der Hofstad  
10.40 - 11.30   Peter Marbach Social Networks: A Research Vision and some Results
11.30 - 11.50 BREAK    
11.50 - 12.40   Patrick Thiran Population Size and Density Estimation Using Mobile Devices
12.40 - 14.00 LUNCH    
14.00 - 14.50   Sanjay Shakkottai Infection Spread with External Agents
14.50 - 15.40   Piet Van Mieghem SIS epidemics on networks
15.40 - 16.20 BREAK    
16.20 - 17.10   Augustin Chaintreau "Is this news?''


09.50 - 10.40   Alexandre Proutiere Community Detection via Random and Adaptive Sampling
10.40 - 11.30   Douglas Leith Max Weight Revisited
11.30 - 11.50 BREAK    
11.50 - 12.40   David Goldberg Distributionally robust inventory control when demand is a martingale
12.40 - 13.30 LUNCH    
13.30 - 14.20   Laurent Massoulie Community detection in stochastic block models via spectral methods
14.20 - 15.10   Thomas Bonald Resource sharing in data centers
15.10 - 15.30 BREAK    
15.30 - 16.20   Claudio De Persis Flow control problems in dynamical distribution networks
18.30 - DINNER    


09.50 - 10.40   Jiheng Zhang Managing customer service chat systems with general service and patience time distributions
10.40 - 11.30   Milan Vojnovic Consensus
11.30 - 11.50 BREAK    
11.50 - 12.40   Ken Duffy Quantifying the computational security of multi-user systems
12.40 Closing    



Thomas Bonald

Resource sharing in data centers

The performance of data centers depends on how concurrent jobs share different resource types like CPU and RAM. Recent research has discussed efficiency and fairness requirements and identified a number of desirable scheduling objectives including so-called dominant resource fairness (DRF). We argue that proportional fairness (PF), long recognized as a desirable objective in sharing network bandwidth between ongoing flows, is preferable to DRF. The superiority of PF is manifest under the realistic modelling assumption that the population of jobs in progress is a stochastic process. In random traffic the strategy-proof property of DRF proves unimportant while PF is shown by analysis and simulation to offer a significantly better efficiency-fairness tradeoff.
(joint work with James Roberts;System-X, France).


Augustin Chaintreau

"Is this news?''

Is a critical and difficult question which had always been answered partly by domain experts and partly by a more informal network of opinion leaders. Recently, the rise of social sharing and information diffusion through blogs, micro-blogs, and social networking, opens this curation process for everyone's participation. It is well known that this apparent level playing field is characterized by sharp contrasts: An active minority of information intermediaries generate most traffic and gather most of the followers, while a minority of items receive most of the attention. But what remains unknown is how these two concentration results relate to each other, and how they may interact to offer the audience a layered offering of news with various level of depths.

Here, and for the first time, we study *jointly* the volume and popularity of URLs received and shared by users. We show that users and bloggers obey two filtering laws: (1) a user who receives less content typically receives more popular content and (2) a blogger who is less active typically posts disproportionately popular items. Our observations are remarkably consistent across 11 data sets of different media, topics, and domains and various measures of URL popularity, and it leads us to formulate various hypothesis on the nature of information filtering social media permit.

One hypothesis is that users choices of intermediaries in a social media, who exhibit extremely varied quality of content, naturally encourage bloggers and active users to play the role of an information filter.


Claudio De Persis

Flow control problems in dynamical distribution networks

In this talk, I will illustrate recent results on the problem of output agreement in networks of nonlinear dynamical systems under unknown time-varying external inputs. The key to these results is the use of dynamic diffusive couplings and internal model controllers. For the class of incrementally passive node systems, constructive sufficient conditions for output agreement are presented. The proposed approach
lends itself to solve flow control problems in distribution networks. This feature will be illustrated in two case studies. As a first case study, the internal model approach is used for designing a controller that achieves an optimal routing and inventory balancing in a dynamic transportation network with storage and time-varying supply and demand. As a second case study, I will show that frequency regulators in power
grids have also an interpretation as internal model controllers.


Ken Duffy

Quantifying the computational security of multi-user systems

In an elegant one page paper in 1994, the late J. Massey asked the following question: how does one metrize the computational security of a single user system? Assuming the password is chosen stochastically with known statistics and an inquisitor can ask about the veracity of each single string, one at a time, he established that the Shannon entropy of the password source is not the correct measure. Seminal work of E. Arikan 1996 established that as strings to be guessed become long, the specific Renyi entropy with parameter 1/2 governs the average guessing growth rate as a function of string length.
Motivated by distributed storage in the cloud and other network applications, in this talk we expand this question to quantify the computational security of multi-user systems. Amongst other results, we show that if systems have independently chosen passwords, then the specific Shannon entropy of the string source is a tight, universal lower bound on the guesswork growth rate.
This talk is based on work with M. Christiansen (NUIM), F. du Pin Calmon (MIT) and M. Medard (MIT). No background knowledge of information theory will be assumed.


David Goldberg

Distributionally robust inventory control when demand is a martingale

Recently, there has been considerable interest in taking a more robust approach to the stochastic models which arise in inventory control, and the control of supply chain networks more generally.  In the distributionally robust optimization paradigm, one assumes that the joint distribution (over time) of the sequence of future demands belongs to some set of joint distributions, and solves the min-max problem of computing the control policy which is optimal against a worst-case distribution belonging to this set.  Although such models have been analyzed previously, the cost and policy implications of positing different dependency structures remains poorly understood.
In this talk, we combine the framework of distributionally robust optimization with the theory of martingales, and consider the setting in which the sequence of future demands is assumed to belong to the family of martingales with given mean and support.  We explicitly compute the optimal policy and value for this min-max optimization problem, and analyze the stochastic process which results from the two-player game between an optimal decision-maker and worst-case adversary.  We also analyze these quantities in the limit (as the time horizon grows large), and prove that the aforementioned game converges weakly to a non-trivial stochastic process, under an appropriate scaling.  We also compare to the analogous setting in which demand is independent across time periods, and identify several qualitative differences.  Interestingly, we find that the ratio of the optimal cost incurred under the martingale model to that incurred under the independent model converges to 1/2 as the time horizon grows large, when the underlying costs are symmetric.
(joint work with Ph.D. student Linwei Xin at Georgia Tech)

Doug Leith

Max Weight Revisited

Often in optimisation problems the natural decision variables are discrete in nature e.g. the decision may be whether to transmit a packet or not, whether to route a vehicle through a traffic junction etc.  This discrete nature makes the probems inherently non-convex.  Nevertheless, the objective to be maximised may be a long-term average of these discrete decision variables e.g. the rate at which packets are transmitted through a network.  When formulated in terms of these average quantities the optimisation problem may well become convex.   In this talk we explore bridging the gap between these non-convex and convex formulations.   It will turn out that by myopically solving sequences of non-convex optimisations involving discrete decision variables we are in fact solving the convex optimisation in terms of average quantities.   Using this framework we can also establish strong links between discrete queues and fluid multipliers, place max-weight approaches firmly within the context of convex optimisation and obtain interesting generalisations of these approaches.

Peter Marbach

Social Networks: A Research Vision and some Results

Social network are very natural and familiar to us. Everyday, we use our social networks to interact with friends, co-workers, or members of our community. We use social networks for a variety of purposes be it for a friendly chat, getting advise on how to proceed with a project, or discussing what is happening in our community. Given that social networks are so familiar to us, and we use them so frequently in our everyday life, one would expect that we understand them very well. In particular, one would expect that we have a clear understanding of why we form social networks, how we form them, and how we use them. However, this does not seem to be the case. The question that we want to study whether it is possible to create a deeper and formal understanding of social networks by developing mathematical models that accurately describe why and how social networks are formed, and how we use social networks. As part of the talk, we will present results that provide some evidence that this might be indeed possible.

Laurent Massoulié

Community detection in stochastic block models via spectral methods

Community detection consists in identification of groups of similar items within a population. In the context of online social networks, it is a useful primitive for recommending either contacts or news items to users. We will consider a particular generative probabilistic model for the observations, namely the so-called stochastic block model, and generalizations thereof. We will describe spectral transformations and associated clustering schemes for partitioning objects into distinct groups. Exploiting results on the spectrum of random graphs, we will establish consistency of these approaches under suitable assumptions, namely presence of a sufficiently strong signal in the observed data. We will also discuss open questions on phase transitions for cluster detectability in such models when the signal becomes weak. In particular we will introduce a novel spectral method which provably allows detection of communities down to a critical threshold, thereby settling an open conjecture of Decelle, Krzakala, Moore and Zdeborová.


Alexandre Proutiére

Community Detection via Random and Adaptive Sampling

We consider networks consisting of a finite number of non-overlapping communities. To extract these communities, the interaction between pairs of nodes may be sampled from a large available data set, which allows a given node pair to be sampled several times. When a node pair is sampled, the observed outcome is a binary random variable, equal to 1 if nodes interact and to 0 otherwise. The outcome is more likely to be positive if nodes belong to the same communities. For a given budget of node pair samples or observations, we wish to jointly design a sampling strategy (the sequence of sampled node pairs) and a clustering algorithm that recover the hidden communities with the highest possible accuracy. We consider both non-adaptive and adaptive sampling strategies, and for both classes of strategies, we derive fundamental performance limits satisfied by any sampling and clustering algorithm. In particular, we provide necessary conditions for the existence of algorithms recovering the communities accurately as the network size grows large. We also devise simple algorithms that accurately reconstruct the communities when this is at all possible, hence proving that the proposed necessary conditions for accurate community detection are also sufficient. The classical problem of community detection in the stochastic block model can be seen as a particular instance of the problems consider here. But our framework covers more general scenarios where the sequence of sampled node pairs can be designed in an adaptive manner. The paper provides new results for the stochastic block model, and extends the analysis to the case of adaptive sampling.
(joint work with Se-Young Yun (MSR-INRIA)).


Sanjay Shakkottai

Infection Spread with External Agents

We study the effect of external infection sources on phase transitions in epidemic processes. In particular, we consider an epidemic spreading on a network via the SI and SIS/SIR dynamics, which in addition is aided by external agents - sources unconstrained by the graph, but possessing a limited infection rate or virulence. Such a model captures many existing models of externally aided epidemics, and finds use in many settings - epidemiology, marketing and advertising, network robustness, etc. We provide a detailed characterization of the impact of external agents on epidemic thresholds. For networks which are `spatially constrained', we show that the spread of infection with the SI model can be significantly speeded up even by a few such external agents infecting randomly. On the other hand, for the SIS model, we show that any external infection strategy with constant virulence either fails to significantly affect the lifetime of an epidemic, or at best, sustains the epidemic for a lifetime which is polynomial in the number of nodes. However, a random external-infection strategy, with rate increasing linearly in the number of infected nodes, succeeds under some conditions to sustain an exponential epidemic lifetime. We obtain similar sharp thresholds for the SIR model, and discuss the relevance of our results in a variety of settings. Joint work with S. Banerjee, A. Das, A. Gopalan, and A. Chatterjee.

Patrick Thiran

Population Size and Density Estimation Using Mobile Devices

Is it possible to estimate the size of a population by opportunistically using data collected on bluetooth phones? If these phones are equipped with GPS devices, can we also estimate the population density? We conduct an experiment where 10 attendees of an open-air music festival are acting as Bluetooth probes. We then construct a parametric statistical model on the contact patterns to estimate the total number of visible Bluetooth phones in the festival area. By comparing the estimate obtained from the model, with ground truth information provided by probes at the entrances of the festival, we find that the total population can be estimated with a surprisingly low error (1.26% in our experiment), given the small number of agents compared to the area of the festival, to the population size and to the fact that they are regular attendees who move randomly (and not to maximize coverage). We then extend the model to jointly estimate population size and density.
(joint work with Farid M. Naini (EPFL), Olivier Dousse (Nokia) and Martin Vetterli (EPFL)).

Piet Van Mieghem

SIS epidemics on networks

The simple SIS epidemic model, which is a continuous-time Markov process, is discussed for any network. The exact governing equations of the continuous-time Markov SIS model are derived. Then, we explain our
N-Intertwined mean-field approximation (NIMFA). Several extensions and attractive features of NIMFA are presented. A brief comparison between the famous Pastor-Satorras & Vespignani heterogeneous mean-field approximation (HMF) and NIMFA in various network types, benchmarked by the "exact" epsilon-SIS model, shows that NIMFA is overall superior to HMF. Next, we elaborate on non-Markovian SIS epidemics on networks and demonstrate that the metastable state can be computed by NIMFA in this non-Markovian setting as well. Finally, we focus on SIS time-dependent behavior and talk about the average time to absorption, first in the complete graph and then generalized to any network.

ps.: Nympha is Latin for "nymph", a mythological spirit of nature or half-goddess imagined as a beautiful maiden inhabiting rivers, woords or other locations.


Milan Vojnovic


The problem of ranking of a set of alternatives based on preferences held by nodes connected by a network is considered under limited memory per node and limited information communicated between nodes. In particular, for the case of binary alternatives, each node in the network is assumed to prefer one of the two alternatives, and the goal for each node is to correctly identify the alternative that is preferred by majority of nodes. This type of a distributed computation problem has been studied under various names such as consensus, k-selection, majority, median and quantile computation. The model is an abstraction that is of interest in various systems such as distributed peer-to-peer systems, databases, dynamics of opinion formation in social networks, and biological computations.


Jiheng Zhang

Managing customer service chat systems with general service and patience time distributions

We consider customer service chat (CSC) systems where customers can receive real time service from agents using an instant messaging (IM) application over the Internet. A unique feature of these systems is that agents can serve multiple customers simultaneously. The number of customers that an agent is serving, referred to as the level of that agent, determines the rate at which each customer assigned to that agent receives service. Customers are impatient and may abandon the system during service. Our objective is to minimize the number of agents while providing a certain service level, measured in terms of the proportion of customers who abandons the system in the long run. We propose a framework involving measure-valued processes to model the system dynamics. Deterministic fluid models are developed to provide first-order approximations for system performance. In particular, the equilibrium states of the fluid models provide simple approximations for various performance metrics of the system in steady state. Numerical experiments show that these approximations are fairly accurate. The significance of the approximations is that they reveal how general service and patience time distributions impact the system performance, and that they lead to design of optimal control and staffing policies for these systems.





Eurandom, Mathematics and Computer Science Dept, TU Eindhoven,

Den Dolech 2, 5612 AZ  EINDHOVEN,  The Netherlands

Eurandom is located on the campus of Eindhoven University of Technology, in the Metaforum building (4th floor) (about the building). The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).
Accessibility TU/e campus and map.




Registration form



For invited speakers, we will take care of accommodation. Other attendees will have to make their own arrangements.

We have a preferred hotel, which can be booked at special rates. Please email Patty Koorn for instructions on how to make use of this special offer.

For other hotels around the university, please see: Hotels (please note: prices listed are "best available"). 

More hotel options can be found on the webpages of the Tourist Information Eindhoven, Postbus 7, 5600 AA Eindhoven.



For those arriving by plane, there is a convenient direct train connection between Amsterdam Schiphol airport and Eindhoven. This trip will take about one and a half hour. For more detailed information, please consult the NS travel information pages or see Eurandom web page location.

Many low cost carriers also fly to Eindhoven Airport. There is a bus connection to the Eindhoven central railway station from the airport. (Bus route number 401) For details on departure times consult http://www.9292ov.nl

The University  can be reached easily by car from the highways leading to Eindhoven (for details, see our route descriptions or consult our map with highway connections.


      Conference facilities : Conference room, Metaforum Building  MF11&12

The meeting-room is equipped with a data projector, an overhead projector, a projection screen and a blackboard. Please note that speakers and participants making an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick.


      Conference Secretariat

Upon arrival, participants should register with the workshop officer, and collect their name badges. The workshop officer will be present for the duration of the conference, taking care of the administrative aspects and the day-to-day running of the conference: registration, issuing certificates and receipts, etc.



Should you need to cancel your participation, please contact Patty Koorn, the Workshop Officer.



Mrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl



The organisers acknowledge the financial support/sponsorship of:







Last updated 09-07-14,
by PK

 P.O. Box 513, 5600 MB Eindhoven, The Netherlands
tel. +31 40 2478100  
  e-mail: info@eurandom.tue.nl