text: Besides the complexity in time or in number of messages, a common approach for analyzing distributed algorithms is to look at the assumptions they make on the underlying network. We investigate this question from the perspective of network dynamics. In particular, we ask how a given property on the evolution of the network can be rigorously proven as necessary or sufficient for a given algorithm. The main contribution of this paper is to propose the combination of two existing tools in this direction: local computations by means of graph relabelings, and evolving graphs. Such a combination makes it possible to express fine-grained properties on the network dynamics, then examine what impact those properties have on the execution at a precise, intertwined, level. We illustrate the use of this framework through the analysis of three simple algorithms, then discuss general implications of this work, which include (i) the possibility to compare distributed algorithms on the basis of their topological requirements, (ii) a formal hierarchy of dynamic networks based on these requirements, and (iii) the potential for mechanization induced by our framework, which we believe opens a door towards automated analysis and decision support in dynamic networks.
  @cite_9: New technologies and the deployment of mobile and nomadic services are driving the emergence of complex communications networks, that have a highly dynamic behavior. This naturally engenders new route-discovery problems under changing conditions over these networks. Unfortunately, the temporal variations in the network topology are hard to be effectively captured in a classical graph model. In this paper, we use and extend a recently proposed graph theoretic model, which helps capture the evolving characteristic of such networks, in order to propose and formally analyze least cost journey (the analog of paths in usual graphs) in a class of dynamic networks, where the changes in the topology can be predicted in advance. Cost measures investigated here are hop count (shortest journeys), arrival date (foremost journeys), and time span (fastest journeys).
  @cite_2: Wireless technologies and the deployment of mobile and nomadic services are driving the emergence of complex ad hoc networks that have a highly dynamic behavior. Modeling such dynamics and creating a reference model on which results could be compared and reproduced, was stated as a fundamental issue by a recent NSF workshop on networking. In this article we show how the modeling of time-changes unsettles old questions and allows for new insights into central problems in networking, such as routing metrics, connectivity, and spanning trees. Such modeling is made possible through evolving graphs, a simple combinatorial model that helps capture the behavior or dynamic networks over time.
summary: In a different context, @cite_2 were proposed as a combinatorial model for dynamic networks. The initial purpose of this model was to provide a suitable representation of (FSDNs), in order to compute optimal communication routes such as shortest, fastest and foremost journeys @cite_9 . In such a context, the evolution of the network was known beforehand. In the present work, we use evolving graphs in a very different purpose, which is to express properties on the network dynamics. It is important to keep in mind that the analyzed algorithms are never supposed to know the evolution of the network beforehand.