Date Added: Jan 2012
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. The authors investigate this question from the perspective of network dynamics. In particular, they 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 re-labelings, 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.