Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms

Details Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms

2011-02-27

arxiv.org/abs/1102.5529v4

Computer Science

Distributed, Parallel, and Cluster Computing

20 pages, 12 figures, long version of a Sirocco'09 paper

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed Computing in Dynamic Networks: Towards a Framework for Automated Analysis of Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-54161