On the Speed of Information Spreading in Dynamic Networks

There is a growing interest in the study of graphs that evolve over time. Communication networks, peer-to-peer systems, social networks, ad-hoc radio networks and the Internet are only few examples of networks that are intrinsically dynamic. In order to analyse real world phenomena from a mathematical point of view, we have to define abstract models of concrete scenarios. This introduces a natural trade-off: the more a model is realistic, the more it is hard to analyse. Finding the right balance between these two poles is one of the hardest part of the work. In the thesis we study the speed of information spreading in dynamic networks. Our aim is to introduce a general framework where simple communication primitives can be analysed, to achieve a better understanding of the main features of dynamic networks. The thesis provides a revised version of the results presented in [6, 5, 7]. We here give an informal overall description of such results. One of the simplest communication tasks that seems worth studying in dynamic networks is the broadcast problem: one distinguished node of the network (the source node) aims to send a messag