Distributed Landmarking
We are posed with a problem when Yuanyuan implemented the distributed landmarking in Planetlab. The distributed landmarking, the mechanism for placing the landmarks themselves at appropriate position in the Cartesian space, is found out to be very slow and incur a large message overhead. A quick analysis of the algorithm immediately showed that the communication complexity of this algorithm is of O(s*n^2), where s is the number of convergence steps and n is the number of landmarks. This presented us with a need of designing a new algorithm for distributed landmarking.
There are two things to be noted from the message complexity of the spring-based distributed landmarking: (a) we need an algorithm that is fast (so that the convegence step is less); (b) probably the algorithm should manage to run by contacting only a subset of landmark nodes.
One simple solution is to collect all the information and run the optimization algorithm locally. That is, all the nodes ping others to find out others' coordinates and ping distances to them. Now all the nodes have an array of ping distances. In the second iteration they exchange the array with every others so that, at the end of the second iteration, every node has (n x n) ping distance matrix and an array of coordinates of all the nodes. Now all the nodes can individually carry out the optimization algorithm to find out the coordinates of the nodes. In this way, computational complexity per node is increased, but the number of message needed is only 2n^2. However, the messages can be huge and the algorithm is not truly distributed (each node doing a part of the total work).
Another approach is to use the PCoord method: in each iteration, a node use only a part of the total landmarks to position itself and this set changes with iteration. The message complexity will be O(s*n*k), where k is the number of nodes contacted each time. Even though this method can reduce the message complexity, there is no guaranttee for that (i.e. s can be arbitarily large).
Therefore, finding a proper distributed landmarking algorithm is still an open problem. Prof suggested an idea of thinking this optimization procedure as reducing the total potential energy stored in the (imagined) spring network. Even though the spring algorithm does approach in this way, it is mostly concerned about reducing local energy than the global energy. I am thinking....
There are two things to be noted from the message complexity of the spring-based distributed landmarking: (a) we need an algorithm that is fast (so that the convegence step is less); (b) probably the algorithm should manage to run by contacting only a subset of landmark nodes.
One simple solution is to collect all the information and run the optimization algorithm locally. That is, all the nodes ping others to find out others' coordinates and ping distances to them. Now all the nodes have an array of ping distances. In the second iteration they exchange the array with every others so that, at the end of the second iteration, every node has (n x n) ping distance matrix and an array of coordinates of all the nodes. Now all the nodes can individually carry out the optimization algorithm to find out the coordinates of the nodes. In this way, computational complexity per node is increased, but the number of message needed is only 2n^2. However, the messages can be huge and the algorithm is not truly distributed (each node doing a part of the total work).
Another approach is to use the PCoord method: in each iteration, a node use only a part of the total landmarks to position itself and this set changes with iteration. The message complexity will be O(s*n*k), where k is the number of nodes contacted each time. Even though this method can reduce the message complexity, there is no guaranttee for that (i.e. s can be arbitarily large).
Therefore, finding a proper distributed landmarking algorithm is still an open problem. Prof suggested an idea of thinking this optimization procedure as reducing the total potential energy stored in the (imagined) spring network. Even though the spring algorithm does approach in this way, it is mostly concerned about reducing local energy than the global energy. I am thinking....
posted by Unknown at
6:00 PM
0 Comments:
Post a Comment
<< Home