Fast Distributed Computation of Distances in Networks

Details Fast Distributed Computation of Distances in Networks Fast Distributed Computation of Distances in Networks

2011-11-25

arxiv.org/abs/1111.6087v1

Computer Science

Distributed, Parallel, and Cluster Computing

12 pages

Scientific paper

This paper presents a distributed algorithm to simultaneously compute the diameter, radius and node eccentricity in all nodes of a synchronous network. Such topological information may be useful as input to configure other algorithms. Previous approaches have been modular, progressing in sequential phases using building blocks such as BFS tree construction, thus incurring longer executions than strictly required. We present an algorithm that, by timely propagation of available estimations, achieves a faster convergence to the correct values. We show local criteria for detecting convergence in each node. The algorithm avoids the creation of BFS trees and simply manipulates sets of node ids and hop counts. For the worst scenario of variable start times, each node i with eccentricity ecc(i) can compute: the node eccentricity in diam(G)+ecc(i)+2 rounds; the diameter in 2*diam(G)+ecc(i)+2 rounds; and the radius in diam(G)+ecc(i)+2*radius(G) rounds.

Affiliated with

Also associated with

No associations

Rating

Fast Distributed Computation of Distances in Networks 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 Fast Distributed Computation of Distances in Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Distributed Computation of Distances in Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-175017