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_14: We propose and analyze two randomized local election algorithms in an asynchronous anonymous graph.
  @cite_6: In this paper we propose and analyze a randomized algorithm to get rendezvous between neighbours in an anonymous graph. We examine in particular the probability to obtain at least one rendezvous and the expected number of rendezvous. We study the rendezvous number distribution in the cases of chain graphs, rings, and complete graphs. The last part is devoted to the efficiency of the proposed algorithm.
summary: Let us repeat that an algorithm does not specify how the nodes synchronize, how they select each other to perform a common computation step. From the abstraction level of local computations, this underlying synchronization is seen as an implementation choice (dedicated procedures were designed to fit the various models, e.g. local elections @cite_14 and local rendezvous @cite_6 for starwise and pairwise interactions, respectively). A direct consequence is that the execution of an algorithm at this level may not be deterministic. Another consequence is that the characterization of conditions on the dynamics will additionally require assumptions on the synchronization -- we suggest later a generic progression hypothesis that serves this purpose. Note that the three algorithms provided in this paper rely on pairwise interactions, but the concepts and methodology involved apply to local computations in general.