About | Research | Events | People | Reports | Alumni | Contact | Home
|
June 30 - July 2, 2014 Workshop on
Performance and Control of Large-Scale Networks
SUMMARY 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.
CONFERENCE DINNER (Restaurant Piet Hein Eek)
ORGANISERS
LIST OF INVITED SPEAKERS
MONDAY June 30
TUESDAY July 1
WEDNESDAY July 2
***************************************************************************************************************************************** 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. 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 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. 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. 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. 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. 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. 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 Milan Vojnovic Consensus 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.
PRACTICAL INFORMATION ● VenueEurandom, 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).
● Registration
● AccommodationFor 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.
● TravelFor 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&12The 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 SecretariatUpon 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.
● CancellationShould you need to cancel your participation, please contact Patty Koorn, the Workshop Officer.
● ContactMrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl SPONSORSThe organisers acknowledge the financial support/sponsorship of:
Last updated
09-07-14,
|
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
.jpg)
