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.
The slides of this lecture are available here: as Powerpoint slides (as pdf file, without animations). The references listing the citations in the tutorial are here.