|
| |
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]
|
