Cost Action 295


Related Events
Traveling Directions
Local Organization
Alternative Hotels



Table of Contents

Stochastic Analysis of Dynamic Processes, Eli Upfal, Brown University

Algorithmic applications of metric embeddings, R. Ravi, Carnegie Mellon University

Wireless networks: Connectivity, capacity, information theory, protocols, computation, clocks and convergence, P. R. Kumar, University of Illinois, Urbana-Champaign

Introduction to Dynamic Networks: Models, Algorithms, and Analysis

Rajmohan Rajaraman, Northeastern University

This lecture will present an overview of models, algorithms, and analysis techniques for studying dynamic networks.  We will discuss different models motivated by diverse dynamic network problems and applications.  These models include (i) asynchronous network models used in traditional distributed computing, (ii) stochastic models in which the network dynamics are captured by a probabilistic process, (iii) adversarial models in which the dynamics are under the control of an adversary, and (iv) game-theoretic models that have been recently proposed to study networks formed by multiple selfish agents.

We will also present some of the key algorithmic and analytical techniques for dynamic networks by reviewing some concrete problems, a few of which we will cover in more detail.  Example problems are load balancing in dynamic asynchronous networks, object location in P2P systems, topology control and routing in ad hoc wireless networks, multicommodity flows in dynamic networks, evolution of Internet-like graphs, and network creation games.


Stochastic Analysis of Dynamic Processes

Eli Upfal, Brown University

Dynamic processes refer to long term processes that evolve in time, usually in response to a stream of input that is continuously injected to the system. Many important processes in today's computing, in particular network processes, are dynamic. Efficient utilization of dynamic processes such as mobile computing environment or P2P network requires modeling and analysis of the underlying dynamic systems. Analysis of the dynamic processes use different tools than the ones used in standard algorithm analysis since dynamic processes do not terminate but are instead evaluated by their long term (steady state) performance.

The course will cover various approaches for modeling and analyzing dynamic processes. Modeling the dynamic performance as a stochastic process, we apply tools from discrete and continues time Markov processes theory, renewal theory and queuing theory to analyze the long term, steady state, performance of the processes. We will also discuss some non-stochastic approaches including adversarial queuing theory, and game theory techniques.


Algorithmic applications of metric embeddings

R. Ravi, Carnegie Mellon University

Computational problems on graph metrics that employ embeddings between metrics either use the metric as data to a problem, or as a relaxation for an optimization problem or attempt to solve a problem involving metrics. Of these, the use of metric as data and problem on metrics are most relevant for the study of dynamic networks.

In this course, we will discuss basic ideas in the embeddings of metrics into normed spaces; probabilistic approximation of finite metrics by a collection of tree metrics and it applications to
approximation problems; construction of sparse subgraphs preserving distance and weight properties, and applications of these techniques to routing and distance labeling problems in networks. We will attempt to formulate research problems of particular relevance to dynamic networks along the way such as questions regarding the online incremental construction and update of such embeddings in light of dynamic changes in the network structure.


Wireless networks: Connectivity, capacity, information theory, protocols, computation, clocks and convergence

P. R. Kumar, University of Illinois, Urbana-Champaign

At one granularity of analysis, wireless networks can be modeled as random Euclidean graphs. Nodes can be modeled as randomly located in two or three-dimensional space, and connected by edges to neighbors at a certain distance away, or to a certain number of nearest neighbors. One question of interest is whether such graphs are connected. A second question is how to accurately synchronize clocks over multi-hop networks, which is motivated by envisaged time driven computing applications of wireless networks to sense and interact with their physical environment. A third question is how much traffic wireless networks can carry. A fourth question is how to compute over wireless sensor networks.

At another finer level of granularity, one can model wireless networks in an information theoretical setting, and ask the question of how much information they can carry without making prior biases on what the architecture of information transport is. How good is the multi-hop mode of information transfer? What about the unreliability of wireless networks caused by fading? 

Finally, at the coarsest level of granularity, one can address questions related to the possible next stage of the information technology revolution: the convergence of control, with communication and computing. What are the appropriate abstractions and architecture? We describe ongoing efforts in the Convergence Laboratory at the University of Illinois.

The Lectures are organized as follows: 

Lecture 1: Connectivity, capacity and protocols for multi-hop wireless networks
Lecture 2: Convergence of control with communication and computing
Lecture 3: A network information theory for wireless networks; Capacity, scaling laws, and path loss

[Joint work with A. Agarwal, G. Baliga, V. Borkar, M. Cao, A. Giridhar, S. Graham, P. Gupta, V. Kawadia, S. Narayanaswamy, C. Robinson, R. Rozovsky, V. Raghunathan, H. Schuetz, R. Solis, L-L. Xie, F. Xue]


Chair: Pierre Fraigniaud (CNRS and Université Paris-Sud)

Local organizers: Filipe Araújo (Univ. of Coimbra) and Luís Rodrigues (Univ. of Lisboa)

Webmaster: dynamoschool-at-lasige.di.fc.ul.pt